✅<1>主页:我的代码爱吃辣
📃<2>知识讲解:数据结构——栈,队列。
🔥<3>创作者:我的代码爱吃辣
☂️<4>开发环境:Visual Studio 2022
🏡<5>系统环境:windows 10
💬<6>前言:今天来学习一下,数据结构中的栈和队列的实现和应用。
目录
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈,出数据也在栈顶。
栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。因为栈即插入和删除(入栈和出战栈)都是在线性表的尾部进行操作,数组的尾部的插如和删除的时间复杂度都是 O(1) ,而如果是链式结构,去实现栈结构,针对尾插和尾删的时间复杂度都是 O(n) ,而双向循环带头的链表,虽然可以解决这个问题,但是.......
我们将栈的实现分为以下各个部分:
1.栈的定义 (StactInit)
- typedef int STDateType; //数据类型
- typedef struct Stact
- {
- STDateType* date; //数组
- int capacity; //栈的容量
- int top; //栈内数据的个数
- }ST;
-
- ST* StactInit()
- {
- ST* Stact = (ST*)malloc(sizeof(ST)); //创建栈的结构
- //栈的结构初始化
- Stact->capacity = 4;
- Stact->top = 0;
- Stact->date = (STDateType*)malloc(sizeof(STDateType)*Stact->capacity);
- //返回栈
- return Stact;
- }
2.栈的销毁 (StactDestroy)
- void StactDestory(ST* Stact)
- {
- assert(Stact);
- //先释放数组申请的空间
- free(Stact->date);
- Stact->date = NULL;
- Stact->capacity = 0;
- Stact->top = 0;
- //在释放栈的结构体空间
- free(Stact);
- }
3.栈的StactPushBank操作 (入栈)
- void StactPushBank(ST* Stact, STDateType x)
- {
- //断言Stact,当进行Push时,栈结构必须存在(Stact!=NULL),
- //如果不存也就是栈是空(Stact==NULL),那Push的操作就是非法的
- assert(Stact);
- //每次对栈的底层是数组,所以每次都要检查是否需要扩容
- if (Stact->capacity == Stact->top)
- {
- STDateType* tmp = (STDateType*)realloc(Stact->date, Stact->capacity * 2);
- if (tmp==NULL)
- {
- perror("realloc");
- exit(-1);
- }
- Stact->date = tmp;
- Stact->capacity *= 2;
- }
- //将x入栈,数组的栈内数据的个数加一
- Stact->date[Stact->top++] = x;
- }
4.栈的StactPopBank操作 (出栈)
- void StactPopBank(ST* Stact)
- {
- assert(Stact);
- //当栈已经空了,还去出栈就是非法了
- assert(!StactEmpty(Stact));
-
- Stact->top--;
- }
5.栈的 StactTop (得到栈顶元素)
- STDateType StactTop(ST* Stact)
- {
- assert(Stact);
- //当栈已经空了,无法获取栈顶元素
- assert(!StactEmpty(Stact));
-
- return Stact->date[Stact->top - 1];
- }
6.栈的StactSize (元素个数)
- int StactSize(ST* Stact)
- {
- assert(Stact);
-
- return Stact->top;
- }
7.栈的判空 (StactEmpty)
- bool StactEmpty(ST* stact)
- {
- assert(stact);
- //当栈内数据个数为0时,栈为空
- return stact->top == 0;
- }
测试:
- void Print(ST* Stact)
- {
- assert(Stact);
- for (int i = 0; i < Stact->top; i++)
- {
- printf("%d ", Stact->date[i]);
- }
- printf("\n");
- }
- int main()
- {
- ST* Stact= StactInit();
- StactPushBank(Stact, 100);
- StactPushBank(Stact, 200);
- StactPushBank(Stact, 300);
- StactPushBank(Stact, 400);
- Print(Stact);
- printf("StactSize:%d\n",StactSize(Stact));
- //Pop一次
- StactPopBank(Stact);
- Print(Stact);
- printf("StactSize:%d\n", StactSize(Stact));
- StactDestory(Stact);
- return 0;
- }
(1)例题
若进栈序列为 1,2,3,4 ,进栈过程中可以出栈,则下列不可能的一个出栈序列是()
A 1,4,3,2
B 2,3,4,1
C 3,1,4,2
D 3,4,2,1
答案:C
分析:选项A,1进1出,2进3进4进,4出3出2出,所以出栈顺序1,4,3,2,选项A正确。
选项B,1进2进,2出,3进3出,4进,4出1出,所以出栈顺序2,3,4,1,选项B正确。
选项C,1进2进3进,3出,此时想要出2,就必须先出栈1,所以选项C错误。
选项D,1进2进3进,3出,4进,4出2出1出,所以出栈顺序3,4,2,1,选项D正确。
(2)例题
LeetCode ———— 20. 有效的括号
题目描述:
思路分析:
遇到左括号就进栈,遇到右括号就出栈,将出栈的左括号与右括号进行匹配,如果匹配成功就继续,如果匹配失败就返回false。
- //栈结构
- typedef char STDateType;
- typedef struct Stact
- {
- STDateType* date;
- int capacity;
- int top;
- }ST;
-
- ST* StactInit();
-
- void StactPushBank(ST* Stact, STDateType x);
-
- int StactSize(ST* Stact);
-
- void StactDestory(ST* Stact);
-
- void StactPopBank(ST* Stact);
-
- STDateType StactTop(ST* Stact);
-
- bool StactEmpty(ST* stact);
-
-
- ST* StactInit()
- {
- ST* Stact = (ST*)malloc(sizeof(ST));
- Stact->capacity = 4;
- Stact->top = 0;
- Stact->date = (STDateType*)malloc(sizeof(STDateType) * Stact->capacity);
- return Stact;
- }
-
- void StactPushBank(ST* Stact, STDateType x)
- {
- assert(Stact);
- if (Stact->capacity == Stact->top)
- {
- STDateType* tmp = (STDateType*)realloc(Stact->date, Stact->capacity * 2);
- if (tmp == NULL)
- {
- perror("realloc");
- exit(-1);
- }
- Stact->date = tmp;
- Stact->capacity *= 2;
- }
- Stact->date[Stact->top++] = x;
- }
-
- bool StactEmpty(ST* stact)
- {
- assert(stact);
- return stact->top == 0;
- }
-
- STDateType StactTop(ST* Stact)
- {
- assert(Stact);
- assert(!StactEmpty(Stact));
- return Stact->date[Stact->top - 1];
- }
-
- void StactPopBank(ST* Stact)
- {
- assert(Stact);
- assert(!StactEmpty(Stact));
- Stact->top--;
- }
-
- void StactDestory(ST* Stact)
- {
- assert(Stact);
- free(Stact->date);
- Stact->date = NULL;
- Stact->capacity = 0;
- Stact->top = 0;
- free(Stact);
- }
-
- int StactSize(ST* Stact)
- {
- assert(Stact);
- return Stact->top;
- }
-
- bool isValid(char* s) {
- //创建栈
- ST* stact = StactInit();
- while (*s)
- {
- //遇到左括号进栈
- if (*s == '(' || *s == '{' || *s == '[')
- {
- StactPushBank(stact, *s);
- s++;
- }
- else
- { //遇到右括号出栈,如果出栈的括号时,
- //栈中已经空,此时括号匹配已经失败
- if (StactEmpty(stact))
- {
- StactDestory(stact);
- return false;
- }
- //如果栈不为空,出栈的左括号,与遇到的右括号匹配
- //如果匹配成功就,继续向后走,匹配失败就返回false
- char ch = StactTop(stact);
- StactPopBank(stact);
- if ((ch == '(' && *s == ')') ||
- (ch == '[' && *s == ']') ||
- ch == '{' && *s == '}')
- {
- s++;
- }
- else
- {
- StactDestory(stact);
- return false;
- }
- }
- }
- //当括号匹配匹配完时,如果栈中还有括号,
- //也就意味着匹配失败。
- if (!StactEmpty(stact))
- {
- StactDestory(stact);
- return false;
- }
- StactDestory(stact);
- return true;
- }
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头。
队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低。
1.队列的定义——QueueInit
由于队列是,队尾入数据,队头出数据,为了方便数据的入队,我们除了队头指针,还会设计一个队尾指针。
- typedef int QUDateType;
- typedef struct QueueNode
- {
- QUDateType date;
- struct QueueNode* next;
- }QueueNode;
-
- typedef struct Queue
- {
- QueueNode* head;
- QueueNode* tail;
- int size;
- }Queue;
-
- void QueueInit(Queue* pque)
- {
- assert(pque);
- pque->head = NULL;
- pque->tail = NULL;
- pque->size = 0;
- }
- int main()
- {
- Queue Q;
- QueueInit(&Q);
-
- return 0;
- }
2.入队操作——QueuePush
- void QueuePush(Queue* pque,QUDateType x)
- {
- //断言队列结构,当进行入队操作时,队列结构一定不能为空
- assert(pque);
- //申请空间
- QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
- if (newnode == NULL)
- {
- perror("malloc");
- exit(-1);
- }
- //赋值
- newnode->date = x;
- newnode->next = NULL;
- //如果队列为空,此时入队的就是第一个数据,也将是队列的头尾数据
- if (pque->head == NULL)
- {
- pque->head = pque->tail = newnode;
- }
- //如果队列不为空,就将数据连接到队尾巴后面
- else
- {
- pque->tail->next = newnode;
- pque->tail = newnode;
- }
- //队列中数据个数加一
- pque->size++;
- }
3.队列销毁——QueueDestroy
- void QueueDestroy(Queue* pque)
- {
- assert(pque);
- QueueNode* cur = pque->head;
- while (cur)
- {
- QueueNode* nextnode = cur->next;
- free(cur);
- cur = nextnode;
- }
- pque->head = pque->tail = NULL;
- }
4.得到对头数据——QueueFront
- QUDateType QueueFront(Queue*pque)
- {
- assert(pque);
- assert(!QueueEmpty(pque));
- return pque->head->date;
- }
5.队列判空——QueueEmpty
- bool QueueEmpty(Queue* pque)
- {
- assert(pque);
- return pque->head == NULL && pque->tail == NULL;
- }
6.删除对头数据——QueuePop
- void QueuePop(Queue* pque)
- {
- assert(pque); //队列结构不能为空
- assert(!QueueEmpty(pque)); //删除数据时队列不能为空
- //队列中只有一个数据的时候
- if (pque->head->next == NULL)
- {
- free(pque->head);
- pque->tail = pque->head = NULL;
- }
- //队列中数据个数大于1
- else
- {
- QueueNode* popnode = pque->head;
- pque->head = pque->head->next;
- free(popnode);
- }
- //数据个数减一
- pque->size--;
- }
7.得到队尾数据——QueueBack
- QUDateType QueueBack(Queue* pque)
- {
- assert(pque);
- assert(!QueueEmpty(pque));
- return pque->tail->date;
- }
8.得到队列中数据个数——QueueSize
-
- int QueueSize(Queue* pque)
- {
- assert(pque);
- return pque->size;
- }
测试:
- int main()
- {
- Queue Q;
- QueueInit(&Q);
- //插如100 .200 300 ,400 ,
- QueuePush(&Q, 100);
- QueuePush(&Q, 200);
- QueuePush(&Q, 300);
- QueuePush(&Q, 400);
-
- //输出队头数据
- printf("%d ", QueueFront(&Q));
- //输出队尾数据
- printf("%d ", QueueBack(&Q));
- //输出队列数据个数
- printf("%d \n", QueueSize(&Q));
- //输出队列中的数据
- while (!QueueEmpty(&Q))
- {
- printf("%d ", Q.head->date);
- QueuePop(&Q);
- }
- //队列销毁
- QueueDestroy(&Q);
-
- return 0;
- }
LeetCode——225. 用队列实现栈
题目描述:
思路:
每次入队数据都需要从不为空的队列进,这样可以保证
Push:进栈,对应到两个队列的操作就是,入不为空的队列。
Top:得到栈顶数据,对应到两个队列的操作就是,得到两个队列中不为空的队列的队尾数据。
Pop:删除栈顶数据,对应的两个队列的操作就是,删除不为空队列的队尾数据元素,但是由于队列结构的原因,要想删除队尾数据,就要先删除队尾前面的数据,所以我们可以先将队尾前面的数据放到另外一个空队列,再将队尾数据删除。
Empty:判断栈是否为空,对应的两个队列的操作就是,只有两个队列都已经没有数据时,栈才为空。
代码:
- //队列结构
- typedef int QUDateType;
- typedef struct QueueNode
- {
- QUDateType date;
- struct QueueNode* next;
- }QueueNode;
-
- typedef struct Queue
- {
- QueueNode* head;
- QueueNode* tail;
- int size;
- }Queue;
-
- void QueueInit(Queue* pque)
- {
- assert(pque);
- pque->head = NULL;
- pque->tail = NULL;
- pque->size = 0;
- }
- //进队列
- void QueuePush(Queue* pque,QUDateType x)
- {
- assert(pque);
- QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
- if (newnode == NULL)
- {
- perror("malloc");
- exit(-1);
- }
- newnode->date = x;
- newnode->next = NULL;
- if (pque->head == NULL)
- {
- pque->head = pque->tail = newnode;
- }
- else
- {
- pque->tail->next = newnode;
- pque->tail = newnode;
- }
- pque->size++;
- }
- //队列为空
- bool QueueEmpty(Queue* pque)
- {
- assert(pque);
-
- return pque->head == NULL && pque->tail == NULL;
- }
- //得到对头数据
- QUDateType QueueFront(Queue*pque)
- {
- assert(pque);
- assert(!QueueEmpty(pque));
- return pque->head->date;
- }
- //得到队尾数据
- QUDateType QueueBack(Queue* pque)
- {
- assert(pque);
- assert(!QueueEmpty(pque));
- return pque->tail->date;
- }
- //队列数据个数
- int QueueSize(Queue* pque)
- {
- assert(pque);
- return pque->size;
- }
- //删除队头数据
- void QueuePop(Queue* pque)
- {
- assert(pque);
- assert(!QueueEmpty(pque));
- //队列中只有一个数据的时候
- if (pque->head->next == NULL)
- {
- free(pque->head);
- pque->tail = pque->head = NULL;
- }
- else
- {
- QueueNode* popnode = pque->head;
- pque->head = pque->head->next;
- free(popnode);
- }
- pque->size--;
- }
- //队列销毁
- void QueueDestroy(Queue* pque)
- {
- assert(pque);
- QueueNode* cur = pque->head;
- while (cur)
- {
- QueueNode* nextnode = cur->next;
- free(cur);
- cur = nextnode;
- }
- pque->head = pque->tail = NULL;
- }
- //封装两个队列
- typedef struct {
- Queue q1;
- Queue q2;
- } MyStack;
-
- //创建栈
- MyStack* myStackCreate() {
- MyStack*Q=(MyStack*)malloc(sizeof(MyStack));
- QueueInit(&Q->q1);
- QueueInit(&Q->q2);
- return Q;
- }
-
- //将元素 x 压入栈顶。
- void myStackPush(MyStack* obj, int x) {
- //找到空队列与非空队列
- QueueNode*empty=&obj->q1;
- QueueNode*noempty=&obj->q2;
- if(!QueueEmpty(&obj->q1))
- {
- empty=&obj->q2;
- noempty=&obj->q1;
- }
- //将数据入空队列
- QueuePush(noempty,x);
- }
- //删除栈顶数据
- int myStackPop(MyStack* obj) {
- assert(obj);
- //找到空队列与非空队列
- QueueNode*empty=&obj->q1;
- QueueNode*noempty=&obj->q2;
- if(!QueueEmpty(&obj->q1))
- {
- empty=&obj->q2;
- noempty=&obj->q1;
- }
- //将非空队列只留一个数据,其他的全部出队到空队列
- while(QueueSize(noempty)>1)
- {
- QueuePush(empty,QueueFront(noempty));
- QueuePop(noempty);
- }
- //返回非空队列的最后一个数据
- int ret=QueueFront(noempty);
- QueuePop(noempty);
- return ret;
- }
- //返回栈顶数据
- int myStackTop(MyStack* obj) {
- assert(obj);
- QueueNode*empty=&obj->q1;
- QueueNode*noempty=&obj->q2;
- if(!QueueEmpty(&obj->q1))
- {
- empty=&obj->q2;
- noempty=&obj->q1;
- }
- return QueueBack(noempty);
- }
- //栈判空
- bool myStackEmpty(MyStack* obj) {
- assert(obj);
- return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
- }
- //销毁栈
- void myStackFree(MyStack* obj) {
- assert(obj);
- QueueDestroy(&obj->q1);
- QueueDestroy(&obj->q2);
- free(obj);
- }
测试:
2.LeetCode——622. 设计循环队列
题目描述:
思路:在设计循环队列的时候,我们可以使用数组,或者链表都是可以的,这里我们就使用数组来实现循环队列。
1.MyCircularQueue(结构)
- typedef struct {
-
- int *date;
- //最后一个数据的下一个坐标
- int tail;
- //头指针
- int head;
- 循环队列的容量
- int k;
- } MyCircularQueue;
2.MyCircularQueue(k)(创建)
在设计循环队列的时候,我们设计队列的容量时多开一个容量,目的是为了更好的分清队空和队满,队空和队满的时候,头尾坐标都会指在同一位置上。
- MyCircularQueue* myCircularQueueCreate(int k) {
- MyCircularQueue*Q=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
- Q->date=(int *)malloc(sizeof(int)*(k+1));
- Q->tail=0;
- Q->head=0;
- Q->k=k;
- return Q;
- }
3.myCircularQueueEnQueue(入队)
- bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
- //先判断队列是否已经满了
- if(myCircularQueueIsFull(obj))
- {
- return false;
- }
- //断言判断队列结构
- assert(obj);
- //在队尾出数据
- obj->date[obj->tail++]=value;
- //当数据尾部已经在数组的最后了,此时在进入数据后,
- //数据尾巴下标时刻保持在数据尾部的后一个下标的,
- //就要回到数组的头部位置。
- if(obj->tail==(obj->k)+1)
- {
- obj->tail=0;
- }
- return true;
- }
4.Front
(获取对头数据)
-
- int myCircularQueueFront(MyCircularQueue* obj) {
- assert(obj);
- //队列不为空,才可以获得数据
- if(myCircularQueueIsEmpty(obj))
- {
- return -1;
- }
- return obj->date[obj->head];
- }
5.deQueue(删除对头数据)
- bool myCircularQueueDeQueue(MyCircularQueue* obj) {
- assert(obj);
- //队列不能为空
- if(myCircularQueueIsEmpty(obj))
- {
- return false;
- }
- //如果head不在数组的尾部,直接head++
- obj->head++;
- //如果head,在数组的最后一个位置,此时head++以后需要循环到数组第一个位置
- if(obj->head==obj->k+1)
- {
- obj->head=0;
- }
- return true;
- }
6.Rear(获得队尾数据)
-
- int myCircularQueueRear(MyCircularQueue* obj) {
- assert(obj);
- //首先队列不能为空
- if(myCircularQueueIsEmpty(obj))
- {
- return -1;
- }
- //当数据尾在数组开头处,最后一个数据在数组的尾部
- //此时k就是数组的最后一个数据的下标
- if(obj->tail-1<0)
- {
- return obj->date[obj->k];
- }
- //如果数据尾部在数组中间或者是在数组尾部,数据尾部就是date[tail-1].
- return obj->date[obj->tail-1];
- }
7.isEmpty(判断队列是否为空)
- bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
- assert(obj);
- //头尾相等就是空。
- return obj->tail==obj->head;
- }
8.isFull(判断队列是否满)
- bool myCircularQueueIsFull(MyCircularQueue* obj) {
- assert(obj);
- //当tail在数组的最后一个位置时,head在数组第一个位置。
- //tail不在数据的最后。
- return (obj->tail+1)%(obj->k+1)==obj->head;
- }
9. 销毁队列
-
- void myCircularQueueFree(MyCircularQueue* obj) {
- assert(obj);
- free(obj->date);
- free(obj);
- }
代码:
- typedef struct {
- int *date;
- int tail;
- int head;
- int k;
- } MyCircularQueue;
-
- bool myCircularQueueIsEmpty(MyCircularQueue* obj);
- bool myCircularQueueIsFull(MyCircularQueue* obj);
-
- MyCircularQueue* myCircularQueueCreate(int k) {
- MyCircularQueue*Q=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
- Q->date=(int *)malloc(sizeof(int)*(k+1));
- Q->tail=0;
- Q->head=0;
- Q->k=k;
- return Q;
- }
-
- bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
-
- if(myCircularQueueIsFull(obj))
- {
- return false;
- }
- assert(obj);
- obj->date[obj->tail++]=value;
- if(obj->tail==(obj->k)+1)
- {
- obj->tail=0;
- }
- return true;
- }
-
- bool myCircularQueueDeQueue(MyCircularQueue* obj) {
- assert(obj);
- if(myCircularQueueIsEmpty(obj))
- {
- return false;
- }
- obj->head++;
- if(obj->head==obj->k+1)
- {
- obj->head=0;
- }
- return true;
- }
-
- int myCircularQueueFront(MyCircularQueue* obj) {
- assert(obj);
- if(myCircularQueueIsEmpty(obj))
- {
- return -1;
- }
- return obj->date[obj->head];
- }
-
- int myCircularQueueRear(MyCircularQueue* obj) {
- assert(obj);
- if(myCircularQueueIsEmpty(obj))
- {
- return -1;
- }
- if(obj->tail-1<0)
- {
- return obj->date[obj->k];
- }
- return obj->date[obj->tail-1];
- }
-
- bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
- assert(obj);
- return obj->tail==obj->head;
- }
-
- bool myCircularQueueIsFull(MyCircularQueue* obj) {
- assert(obj);
- return (obj->tail+1)%(obj->k+1)==obj->head;
- }
-
- void myCircularQueueFree(MyCircularQueue* obj) {
- assert(obj);
- free(obj->date);
- free(obj);
- }
测试: