做网站难度大吗,创意 国外 网站,WordPress书籍插件,小榄网站建设公司目录
前言
一、栈
二、栈的实现
三、栈的循环遍历演示
四、栈的算法题
//
一、队列
二、队列的实现
三、使用演示
四、队列的算法题
总结 前言 本文完整实现了栈和队列的数据结构#xff0c;以及栈和队列的一些经典算法题#xff0c;让我们更加清楚了解这两种数据…
目录
前言
一、栈
二、栈的实现
三、栈的循环遍历演示
四、栈的算法题
//
一、队列
二、队列的实现
三、使用演示
四、队列的算法题
总结 前言 本文完整实现了栈和队列的数据结构以及栈和队列的一些经典算法题让我们更加清楚了解这两种数据结构特点并熟悉运用。 一、栈 栈⼀种特殊的线性表其只允许在固定的一端进行插⼊和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLastInFirstOut的原则。 栈的特点 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。
出栈栈的删除操作叫做出栈。出数据也在栈顶。 因为栈的特殊结构所以对它的循环遍历也比较特殊。 栈 底层结构选型 栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些。原因如下 首先数组搭配栈顶下标top可以很方便找到栈顶元素。当然使用链表也可以链表采用带头单向不循环链表采用头插和头删也能实现栈的基本操作而且时间复杂度都是O(1)不采用链表是因为栈的入栈和出栈操作频繁链表需要不断开辟或者释放空间而数组也采用动态开辟使用2倍扩容能有效降低申请空间的频率。其次链表结构每个节点都需要有一个指针变量指针占用4/8字节可能比储存的数据都大会占用大量空间而数组开辟的空间仅用于存储数据。连续性空间比不连续空间访问速度快 二、栈的实现
1.栈的结构声明
使用数组作为底层结构 typedef int STDataType; //定义栈结构 typedef struct Stack { STDataType* arr; int capacity;//栈的空间大小 int top;//栈顶 }ST; 与顺序表基本相同只有第三个成员变量含义不同。本质都是表示有效元素个数。 2.Stack.h头文件
#pragma once
#include stdio.h
#include stdlib.h
#include stdbool.h
#include assert.htypedef int STDataType;
//定义栈结构
typedef struct Stack
{STDataType* arr;int capacity;//栈的空间大小int top;//栈顶
}ST;//初始化
void STInit(ST* ps);//销毁
void STDesTroy(ST* ps);//入栈
void StackPush(ST* ps, STDataType x);//判空
bool StackEmpty(ST* ps);//出栈
void StackPop(ST* ps);//取栈顶元素
STDataType StackTop(ST* ps);//获取栈中有效元素个数
int STSize(ST* ps);
栈的基本操作函数有
栈的初始化栈的销毁入栈增加元素出栈删除元素判空判断栈是否为空栈取栈顶元素但不用出栈获取栈中的元素个数 3.Stack.c 定义文件
注意看注释与顺序表很像
#include Stack.h//初始化
void STInit(ST* ps)
{assert(ps);//全初始化为空ps-arr NULL;ps-capacity ps-top 0;
}//销毁
void STDesTroy(ST* ps)
{assert(ps);//判断arrif (ps-arr){free(ps-arr);}//销毁后置空ps-arr NULL;ps-capacity ps-top 0;
}//入栈
void StackPush(ST* ps, STDataType x)
{assert(ps);//判断空间是否充足if (ps-top ps-capacity){//使用三目操作符根据容量是否为0来选择如何给定新容量大小int newCapacity ps-capacity 0 ? 4 : 2 * ps-capacity;//1.如果容量为0赋值4 2.如果容量不为零进行二倍扩容//申请新空间STDataType* tmp (STDataType*)realloc(ps-arr, newCapacity * sizeof(STDataType));if (tmp NULL){perror(realloc fail!);exit(1);}//修改参数ps-arr tmp;ps-capacity newCapacity;}//空间充足ps-arr[ps-top] x;
}//判空
bool StackEmpty(ST* ps)
{assert(ps);return ps-top 0;
}//出栈
void StackPop(ST* ps)
{assert(ps);//判断栈容量是否为空assert(!StackEmpty(ps));//直接让栈顶下移一位即可--ps-top;
}//取栈顶元素
STDataType StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));//判空//直接返回栈顶元素return ps-arr[ps-top - 1];
}//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps-top;
}
函数解析
STInit函数栈的初始化需要传入栈的地址将其 arr 初始化为空指针capacity、top初始化为0。assert是断言一般的操作栈不能为空STDesTroy函数栈的销毁传入栈的地址栈的 arr 空间是由 realloc 申请的因此需要free 释放释放时应先判断 arr 是否申请了空间。释放后将栈的成员置空。StackPush函数入栈传入栈的地址和需要添加的元素。入栈之前需要先判断栈空间是否充足通过栈结构的成员变量 capacity容量 和 top栈顶 是否相等来判断栈是否满了。因为我们初始化时并没有开辟空间所以第一次入栈这里一定是需要开辟空间的因此我们使用3目操作符对新容量大小进行赋值如果容量为0那么就是第一次开辟空间赋值4。如果不为0那么就进行2倍扩容。随后使用 realloc 开辟空间判断成功开辟后将新空间地址赋值给栈成员 arr将新容量大小赋值给栈成员 capacity。StackEmpty函数判空传入栈的地址如果栈顶下标都为0那么栈就为空。StackPop函数出栈传入栈的地址出栈需要判断栈是否为空用写好的上一个函数判断即可出栈操作只需要将栈顶下标减1因为每次入栈也是在栈顶下次入栈就会覆盖旧数据StackTop函数取栈顶元素传入栈的地址先判断栈是否为空然后直接返回栈顶元素即可。注意top的下标是下一个入栈的位置因此栈顶元素需要-1。STSize函数获取栈中有效元素个数直接返回栈顶下标即可。 三、栈的循环遍历演示
#include Stack.hvoid StackTest1()
{//创建一个栈ST st;//初始化STInit(st);//压入4个数据StackPush(st, 1);StackPush(st, 2);StackPush(st, 3);StackPush(st, 4);//循环遍历while (!StackEmpty(st))//栈顶元素为空才停止{//取栈顶元素并打印printf(%d , StackTop(st));//出栈StackPop(st);}//销毁STDesTroy(st);
}int main()
{StackTest1();return 0;
}
运行结果 解析
为什么只能这样遍历栈答因为这样才符合栈的特性栈是不支持随机访问的它只能从栈顶开始访问。如果想访问下一个数据那么上一个数据必须出栈才行。 四、栈的算法题
题目出处
20. 有效的括号 - 力扣LeetCode 题目解析
首先题目意思是判断一组括号是否符合语法规定比如{ [] }当然题目中并没有规定括号优先级问题所以小括号也能包住大括号我们发现如果一开始是左括号一旦遇到右括号那么这个右括号如果是正确的那么它一定和最近的左括号匹配如何使用栈的特性来解决栈是“先进后出”如果我们让左括号先进栈遇到右括号时先取栈顶元素与右括号匹配如果匹配我们让左括号出栈。如此循环左括号进栈右括号判断一旦匹配失败就说明括号字符串不符合规定。如图 题解
bool isValid(char* s)
{//创建一个栈ST st;STInit(st);//新建一个指针char* ps s;//循环遍历while (*ps ! \0){if (*ps ( || *ps [ || *ps {){//入栈StackPush(st, *ps);}else{//假如栈中无数据一开始就是右括号if (StackEmpty(st)){//直接销毁栈并返回否STDesTroy(st);return false;}//如果栈中有数据,先取栈顶元素然后与右括号进行判断char ch StackTop(st);if (*ps ) ch (|| *ps ] ch [|| *ps } ch {){//匹配正确,出栈StackPop(st);}else{//匹配失败STDesTroy(st);return false;}}ps;}//如果栈中还有数据证明左括号多了if (!StackEmpty(st)){STDesTroy(st);return false;}//一切正常STDesTroy(st);return true;
}
注意答题时需要将栈的完整代码也加上去 /// 一、队列 概念只允许在⼀端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out)特性 特性“先进先出” 或者 “后进后出”
入队列进行插入操作的一端称为队尾
出队列进行删除操作的一端称为队头 与栈的异同
不同栈是一端进行进出数据操作队列是两端一端进数据一端出数据相同都是在端点操作 队列 底层结构选型 队列也可以数组和链表的结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低。 二、队列的实现 1.队列的结构声明
typedef int QDatatype;//定义队列节点的类型结构
typedef struct QueueNode
{QDatatype data;struct QueueNode* next;
}QueueNode;//定义队列
typedef struct Queue
{QueueNode* phead;QueueNode* ptail;int size; //保存队列有效元素个数
}Queue;
队列的结构比较特殊
因为队列采用单链表作为底层结构因此需要定义队列的存储数据类型也就是定义每个数据的节点类型。所以第一个结构体只是定义队列的元素类型第二个结构体才是队列队列仅需要两个指针一个指针指向对头一个指针指向队尾。因为这两指针类型都是元素节点的类型所以要先定义元素类型队列中的 size 成员是储存队列有效元素个数因为如果想知道队列的元素个数循环遍历队列效率低因此队列多加一个成员变量储存元素个数。 2.Queue.h头文件
#pragma once
#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.htypedef int QDatatype;//定义队列节点的类型结构
typedef struct QueueNode
{QDatatype data;struct QueueNode* next;
}QueueNode;//定义队列
typedef struct Queue
{QueueNode* phead;QueueNode* ptail;int size; //保存队列有效元素个数
}Queue;//初始化
void QueueInit(Queue* pq);//入队列
void QueuePush(Queue* pq, QDatatype x);//判空
bool QueueEmpty(Queue* pq);//出队列
void QueuePop(Queue* pq);//取队头数据
QDatatype QueueFront(Queue* pq);//取队尾数据
QDatatype QueueBack(Queue* pq);//队列有效元素个数
int QueueSize(Queue* pq);//销毁
void QueueDesTroy(Queue* pq);
队列的常用操作
队列的初始化入队插入元素出队删除元素判空判断队列是否为空取对头元素取队尾元素获取队列有效元素个数队列的销毁 3.Queue.c定义文件
#include Queue.h//初始化
void QueueInit(Queue* pq)
{assert(pq);//初始化为空指针和0pq-phead pq-ptail NULL;pq-size 0;
}//入队列
void QueuePush(Queue* pq, QDatatype x)
{assert(pq);//申请新节点QueueNode* newnode (QueueNode*)malloc(sizeof(QueueNode));if (newnode NULL){perror(malloc fail!);exit(1);}//赋值初始化newnode-data x;newnode-next NULL;if (pq-phead NULL){//如果队列为空pq-phead pq-ptail newnode;}else{//栈不为空pq-ptail-next newnode;pq-ptail pq-ptail-next;}//元素个数加一pq-size;
}//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-phead NULL pq-ptail NULL;
}//出队列
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//如果队列只有一个节点要避免ptail成为野指针if (pq-phead pq-ptail){free(pq-phead);pq-phead pq-ptail NULL;}else{//直接删除第一个节点QueueNode* next pq-phead-next;free(pq-phead);pq-phead next;}//元素个数减一pq-size--;
}//取队头数据
QDatatype QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-phead-data;
}//取队尾数据
QDatatype QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-ptail-data;
}//队列有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}//销毁
void QueueDesTroy(Queue* pq)
{assert(pq);//这一句判空可要可不要写上的话在一些算法题中可能会报错//assert(!QueueEmpty(pq));QueueNode* pcur pq-phead;while (pcur){QueueNode* next pcur-next;free(pcur);pcur next;}pq-phead pq-ptail NULL;pq-size 0;
}
函数解析
QueueInit函数队列的初始化传入队列的地址将其头指针和尾指针都初始化为NULLsize 初始化为0。QueuePush函数入队传入队列的地址和需要插入的数据首先申请新节点将需要出入的数据赋值给新节点并将其 next 指针初始化为空。然后从队尾插入队列在插入队列之前需要先判断队列是否为空可以将判空函数提前因为如果队列为空那么它的头尾指针都应是新节点如果队列不为空那么从队尾插入先将队尾指针的 next 指针指向新节点然后更新队尾指针为新节点最后不要忘了让 size。QueueEmpty函数判空直接返回头指针与空指针的判断结果判不判断尾节点都行QueuePop函数出队出队列需要先判空另外还需要注意如果队列只有一个元素那么尾指针和头指针都需要变为空指针。如果队列元素多于一个元素那么只改变头指针即可先保存头指针的 next 节点然后释放头指针节点再跟新头指针最后记得让 size--。QueueFront函数取对头元素有头指针存在判空后直接返回头指针指向的节点数据QueueBack函数取队尾元素同理返回尾指针指向的节点数据即可QueueSize函数获取队列有效元素个数返回队列结构成员 size 即可QueueDesTroy函数队列的销毁判空可不写先保存头指针然后循环遍历释放各节点如果不判空这里不受影响因为空队列那么头指针也为空就不会进入循环最后将指针和 size 都置空或置0。 三、使用演示
#include Queue.hvoid QueueTest1()
{//创建队列Queue q;//初始化QueueInit(q);//入队QueuePush(q, 1);QueuePush(q, 2);QueuePush(q, 3);QueuePush(q, 4);//循环出队列并打印while (!QueueEmpty(q)){//取队头元素printf(%d , QueueFront(q));//出队列QueuePop(q);}//销毁QueueDesTroy(q);
}int main()
{QueueTest1();return 0;
}
运行结果 注意将销毁队列中的判空注释掉不然会报错 四、队列的算法题 1.双队列实现栈
题目出处225. 用队列实现栈 - 力扣LeetCode 题目解析
题目是让我们使用两个队列来实现栈满足栈的“先进后出”实现6种基本操作如何实现队列的特性是“先进先出”一端进数据一端出数据那么假如我们将数据 1、2、3 插入队列1我们需要出栈那么只能出数据3而队列只能在对头出数据因此我们先将数据 1、2 出队列并插入队列2此时队列2中为数据 1、2队列1中数据为 3。此时我们再将队列1中的3出队列此时就完成了出栈的操作。所以我们使用将数据在两个队列中来回导的方法实现栈的操作方法。那么这里面的关键就是每一次操作后只有一个队列中有数据另一个队列为空。入栈操作我们往不为空的队列中插入数据。出栈操作找到不为空的队列把不为空队列中的 size-1 个数据导到空队列中最后将不为空队列中的最后一个数据出队列注意取栈顶元素操作不能模仿出栈操作因为取栈顶元素不会出栈来回导会造成两个队列都不为空的情况
题解
注意在答题时需将队列的完整代码写上去
typedef struct
{//栈结构使用两个队列Queue q1;Queue q2;
} MyStack;//初始化
MyStack* myStackCreate()
{动态开辟栈的空间MyStack* pst (MyStack*)malloc(sizeof(MyStack));//两个队列使用队列初始化函数完成初始化QueueInit(pst-q1);QueueInit(pst-q2);return pst;
}//入栈
void myStackPush(MyStack* obj, int x)
{//往不为空的队列中入数据if (!QueueEmpty(obj-q1)){QueuePush(obj-q1, x);}else{QueuePush(obj-q2, x);}
}//出栈
int myStackPop(MyStack* obj)
{//首先找不为空的队列Queue* empQ obj-q1;Queue* noneQ obj-q2;if (!QueueEmpty(obj-q1)){empQ obj-q2;noneQ obj-q1;}//将不为空的队列中的size-1个数据导入到空队列while (QueueSize(noneQ) 1){int Front QueueFront(noneQ);QueuePush(empQ, Front);QueuePop(noneQ);}//非空队列剩下的一个数据就是需出栈的数据int pop QueueFront(noneQ);QueuePop(noneQ);return pop;
}//取栈顶元素
int myStackTop(MyStack* obj)
{//找到不为空的队列返回队尾元素即可if (!QueueEmpty(obj-q1)){return QueueBack(obj-q1);}else{return QueueBack(obj-q2);}
}//判空
bool myStackEmpty(MyStack* obj)
{return QueueEmpty(obj-q1) QueueEmpty(obj-q2);
}//销毁
void myStackFree(MyStack* obj)
{QueueDesTroy(obj-q1);QueueDesTroy(obj-q2);free(obj);obj NULL;
} 2.双栈实现队列
题目出处232. 用栈实现队列 - 力扣LeetCode 题目解析
与上一题相反这题需要使用两个栈来实现队列结构有了上一题的经验这一题同样也是使用来回导数据的方式。如我们现在需要入队数据 1、2、3我们将其插入栈1中栈是“先进后出”当我们需要出队时我们直接将栈1的数据出栈并插入栈2此时栈2中的数据为 3、2、1而栈顶元素 1 就是我们需要出队的数据也就是对头元素。接下来如果我们还需要出队那么直接让栈2元素出栈即可如果需要入队元素直接插入到栈1因此与上一题不同的是这次我们不用保证有一个容器为空我们让栈1专门存放入队元素让栈2专门用来出对。这样也就符合了队列的“先进先出”特性
题解
typedef struct
{ST pushST;//用于入队ST popST;//用于出队
} MyQueue;//初始化
MyQueue* myQueueCreate()
{MyQueue* pq (MyQueue*)malloc(sizeof(MyQueue));//调用栈自己的初始化函数STInit(pq-popST);STInit(pq-pushST);return pq;
}//入队
void myQueuePush(MyQueue* obj, int x)
{//直接往push栈中插入元素StackPush(obj-pushST, x);
}//出队
int myQueuePop(MyQueue* obj)
{//先判断pop栈是否为空if (StackEmpty(obj-popST)){//为空导数据while (!StackEmpty(obj-pushST)){//将push栈中元素全导入pop栈StackPush(obj-popST, StackTop(obj-pushST));StackPop(obj-pushST);}}//先储存出队元素出栈后返回int pop StackTop(obj-popST);StackPop(obj-popST);return pop;
}//取对头元素
int myQueuePeek(MyQueue* obj)
{//前面与出队操作一致if (StackEmpty(obj-popST)){//导数据while (!StackEmpty(obj-pushST)){StackPush(obj-popST, StackTop(obj-pushST));StackPop(obj-pushST);}}//最后不用出栈直接返回栈顶元素return StackTop(obj-popST);
}//判空
bool myQueueEmpty(MyQueue* obj)
{return StackEmpty(obj-popST) StackEmpty(obj-pushST);
}//销毁
void myQueueFree(MyQueue* obj)
{STDesTroy(obj-popST);STDesTroy(obj-pushST);free(obj);obj NULL;
}3.设计循环队列
题目出处622. 设计循环队列 - 力扣LeetCode 题目解析·
题目是让我们设计一个循环队列那么什么是循环队列根据题目我们了解循环队列依旧遵循“先进先出”特性结构上是队列的尾指针与头指针相连并且重要的是循环队列的空间的固定的。如何设计呢既然循环队列空间是一定的那我们可以采取数组作为底层结构当然链表也行不过数组更为方便能一次性开辟完空间。除了底层结构我们知道队列是有两个指针指向队头和对尾的那么我们就可以设置两个下标 front 和 rear 来分别指向循环队列的对头和队尾。循环队列还有插入和删除操作执行这两个操作时我们需要判断循环队列是否满了或者空了那么我们怎么判断呢假如我们将 front 和 rear 都初始化为0那么当它俩相等时我们可以确定队列为空可是队列满了它们俩也相等。怎么解决这个问题呢直接说结论吧我们选择多开辟一个空间也就是数组的最后一位最后一个空间不存储数据当 rear 走到这个位置时那么此时循环队列就满了而 front 和 rear 下标也就不相同。这样就可以通过下标来区分循环队列是空是满。满了的公式由 rear1 等于 front 的下标推导因为循环队列中下标走到头了后需要回到对头所以使用取余来更新计算下标推出以下公式能够判断队列状态后我们就可以进行入队和出队操作了。入队操作首先根据公式判断队列是否满了满了直接返回 false没满在 rear 处插入数据然后 rear 往后走一位这时候就需要注意了rear 不能越界走到数组末尾了如果队列还有空间需要更新 rear 的下标所以 rear rear % (capacit1)保证下标循环走动出队操作需要先判空判空后如果队列不为空直接让 front使原数据无效即可这里front 的下标同样不能越界需要通过取余来保证其在队列中循环走动front % capacity1获取对头和对尾元素中对头元素获取简单判空后直接返回 front 下标位置处的数据即可而队尾就有所不同判空后不能直接返回 rear 下标处的数据因为 rear 下标指向的是下一个元素插入的位置取队尾元素时需减1因此有一种特殊情况即当 rear 刚好处于下标为0处的位置这时候返回队尾元素 3 时不能直接返回 rear-1 处下标的元素而是另外创建一个 prev 指针让其指向 rear-1 处的下标并判断如果 rear 刚好处于下标为0的位置时让 prev 等于 capacity 也就是下标为5的位置。
题解
typedef struct
{int* arr;int front;int rear;int capacity;
} MyCircularQueue;//初始化
MyCircularQueue* myCircularQueueCreate(int k)
{MyCircularQueue* pst (MyCircularQueue*)malloc(sizeof(MyCircularQueue));pst-arr (int*)malloc(sizeof(int) * (k 1));pst-front pst-rear 0;pst-capacity k;return pst;
}//判断队列是否满了
bool myCircularQueueIsFull(MyCircularQueue* obj)
{return (obj-rear 1) % (obj-capacity 1) obj-front;
}//插入数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{//如果队列满了if (myCircularQueueIsFull(obj)){return false;}//没满obj-arr[obj-rear] value;obj-rear % obj-capacity 1;return true;
}//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{return obj-front obj-rear;
}//删除数据
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{//如果队列为空if (myCircularQueueIsEmpty(obj)){return false;}//不为空obj-front;obj-front % obj-capacity 1;return true;
}//获取对头元素
int myCircularQueueFront(MyCircularQueue* obj)
{if (myCircularQueueIsEmpty(obj)){return -1;}return obj-arr[obj-front];
}//获取队尾元素
int myCircularQueueRear(MyCircularQueue* obj)
{if (myCircularQueueIsEmpty(obj)){return -1;}int prev obj-rear - 1;if (obj-rear 0){prev obj-capacity;}return obj-arr[prev];
}//销毁
void myCircularQueueFree(MyCircularQueue* obj)
{free(obj-arr);free(obj);obj NULL;
}
扩展计算循环队列有效元素个数
公式循环队列有效元素个数 ( rear - front capacity 1 ) % ( capacity 1 ) 总结 以上就是本文的全部内容感谢支持
