devbox
Li_阴宅
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】栈和队列的实现及应用_栈、队列的实际应用

作者：Li_阴宅 | 2024-07-30 14:42:49

赞

踩

栈、队列的实际应用

需要云服务器等云产品来学习Linux的同学可以移步/-->腾讯云<--/-->阿里云<--/-->华为云<--/官网，轻量型云服务器低至112元/年，新用户首次下单享超低折扣。

一、栈的概念

二、Stack.h

三、Stack.c

1、栈的初始化和销毁

2、栈的进栈、出栈

3、栈的判空、访问栈顶元素、栈内元素个数

四、队列的概念

五、Queue.h

六、Queue.c

1、队列的初始化和销毁

2、队列的入队、出队

3、队列的判空

4、访问队头、队尾数据、统计队列长度

七、力扣中栈和队列OJ题

1、有效的括号

2、用队列实现栈

3、用栈实现队列

4、设计循环队列

栈和队列是一种数据结构，只规定了性质，并没有规定实现方式。

本文以顺序结构实现栈，链表方式实现队列。

一、栈的概念

栈：是一种特殊的线性表，其只允许在栈顶进行插入和删除元素操作。

栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈\压栈\入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

二、Stack.h

  1. #pragma once
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <assert.h>
  5. #include <stdbool.h>
  6. typedef int STDataType;
  7. typedef struct stack
  8. {
  9. 	STDataType* arr;
  10. 	int top;//数组元素个数（top-1为最后一个元素的下标）就是顺序表的size
  11. 	int capacity;//总容量
  12. }ST;
  13. void StackInit(ST* ps);//初始化
  14. void StackDestroy(ST* ps);//销毁
  15. void StackPush(ST* ps, STDataType x);//压栈
  16. void StackPop(ST* ps);//出栈
  17. bool StackEmpty(ST* ps);//判断栈是不是为空
  18. STDataType StackTop(ST* ps);//访问栈顶元素
  19. int StackSize(ST* ps);//数组元素个数

以顺序结构实现栈，本质上仍是一个顺序表，只是这个顺序表加上了栈先进后出的规则。

数组的头是栈底，数组尾是栈顶。栈主要的压栈、出栈、访问栈顶等接口非常契合顺序表的尾插、尾删、随机访问的特点。

三、Stack.c

1、栈的初始化和销毁

  1. void StackInit(ST* ps)//初始化
  2. {
  3. 	assert(ps);
  4. 	ps->arr = NULL;
  5. 	ps->top = ps->capacity = 0;
  6. }
  7. void StackDestroy(ST* ps)//销毁
  8. {
  9. 	assert(ps);
  10. 	free(ps->arr);
  11. 	ps->arr = NULL;
  12. 	ps->top = ps->capacity = 0;
  13. }

和顺序表的初始化、销毁方式一样

2、栈的进栈、出栈

  1. void StackPush(ST* ps, STDataType x)//进栈
  2. {
  3. 	assert(ps);
  4. 	//判断扩容
  5. 	if (ps->top == ps->capacity)
  6. 	{
  7. 		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
  8. 		STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
  9. 		if (tmp == NULL)
  10. 		{
  11. 			perror("realloc fail:\n");
  12. 			exit(-1);
  13. 		}
  14. 		ps->arr = tmp;
  15. 		ps->capacity = newCapacity;
  16. 	}
  17. 	ps->arr[ps->top] = x;
  18. 	ps->top++;
  19. }
  20. void StackPop(ST* ps)//出栈
  21. {
  22. 	assert(ps);
  23. 	assert(!StackEmpty(ps));
  24. 	ps->top--;
  25. }

进栈需要判断栈的空间，空间不够则需要扩容

出栈时，先判空，再将top--即可

3、栈的判空、访问栈顶元素、栈内元素个数

  1. bool StackEmpty(ST* ps)//判断栈是不是为空
  2. {
  3. 	assert(ps);
  4. 	return ps->top == 0;
  5. }
  6. STDataType StackTop(ST* ps)//访问栈顶元素
  7. {
  8. 	assert(ps);
  9. 	assert(!StackEmpty(ps));
  10. 	return ps->arr[ps->top - 1];
  11. }
  12. int StackSize(ST* ps)//数组元素个数
  13. {
  14. 	assert(ps);
  15. 	return ps->top;
  16. }

注意访问栈顶元素这个接口，要先判断栈是不是空。

四、队列的概念

队列：一端进行插入数据操作，另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)的特点。

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

队列参照现实生活中的排队

五、Queue.h

  1. #pragma once
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <assert.h>
  5. #include <stdbool.h>
  6. typedef int QDataType;
  7. typedef struct QueueNode
  8. {
  9. 	struct QueueNode* next;
  10. 	QDataType data;
  11. }QNode;
  12. typedef struct Queue
  13. {
  14. 	QNode* head;
  15. 	QNode* tail;
  16. 	int size;//加个size，方便统计长度
  17. }Queue;
  18. void QueueInit(Queue* pq);//初始化
  19. void QueueDestroy(Queue* pq);//销毁
  20. void QueuePush(Queue* pq,QDataType x);//入队（尾插）
  21. bool QueueEmpty(Queue* pq);//判断队列是否为空
  22. void QueuePop(Queue* pq);//出队（头删）
  23. int QueueSize(Queue* pq);//统计队列长度
  24. QDataType QueueFront(Queue* pq);//访问队头数据
  25. QDataType QueueBack(Queue* pq);//访问队尾数据

因为顺序结构不适合头删，这里使用单链表来实现队列。

结构体QNode用于模拟单链表，结构体Queue中存放了单链表的头、尾指针、链表节点个数。使用Queue来操纵单链表。

单链表的头head是队头（头删出数据），tail是队尾（尾插录数据）

六、Queue.c

1、队列的初始化和销毁

  1. void QueueInit(Queue* pq)//初始化
  2. {
  3. 	assert(pq);
  4. 	pq->head = pq->tail = NULL;
  5. 	pq->size = 0;
  6. }
  7. void QueueDestroy(Queue* pq)//销毁
  8. {
  9. 	assert(pq);
  10. 	QNode* cur = pq->head;
  11.     //逐个销毁释放空间
  12. 	while (cur)
  13. 	{
  14. 		QNode* del = cur;
  15. 		cur = cur->next;
  16. 		free(del);
  17. 	}
  18. 	pq->head = pq->tail = NULL;
  19. }

和单链表的销毁方式一样，注意销毁时需要逐个节点销毁。

2、队列的入队、出队

  1. void QueuePush(Queue* pq, QDataType x)//入队,尾插
  2. {
  3. 	assert(pq);
  4.     //创建一个新节点
  5. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
  6. 	if (newnode == NULL)
  7. 	{
  8. 		perror("malloc fail:\n");
  9. 		exit(-1);
  10. 	}
  11. 	newnode->data = x;
  12. 	newnode->next = NULL;
  13.     //队列为空时的尾插和不为空的尾插
  14. 	if (QueueEmpty(pq))
  15. 		pq->head=pq->tail = newnode;
  16. 	else
  17. 	{
  18. 		pq->tail->next = newnode;
  19. 		pq->tail = newnode;
  20. 	}
  21. 	pq->size++;
  22. }
  23. void QueuePop(Queue* pq)//出队（头删）
  24. {
  25. 	assert(pq);
  26. 	assert(!QueueEmpty(pq));
  27. 	QNode* next = pq->head->next;
  28. 	free(pq->head);
  29. 	pq->head = next;
  30. 	pq->size--;
  31. }

入队：尾插一个节点

出队：头删一个节点

3、队列的判空

  1. bool QueueEmpty(Queue* pq)//判断队列是否为空
  2. {
  3. 	assert(pq);
  4. 	return pq->head == NULL;
  5. }

4、访问队头、队尾数据、统计队列长度

  1. int QueueSize(Queue* pq)//统计队列长度
  2. {
  3. 	assert(pq);
  4. 	return pq->size;
  5. }
  6. QDataType QueueFront(Queue* pq)//访问队头数据
  7. {
  8. 	assert(pq);
  9. 	assert(!QueueEmpty(pq));
  10. 	return pq->head->data;
  11. }
  12. QDataType QueueBack(Queue* pq)//访问队尾数据
  13. {
  14. 	assert(pq);
  15. 	assert(!QueueEmpty(pq));
  16. 	return pq->tail->data;
  17. }

访问接口，注意先判空。

七、力扣中栈和队列OJ题

1、有效的括号

使用队列来解决，创建一个栈，碰到左括号将其进栈，碰到右括号则访问栈顶元素，不相符则为false，迭代比较相符则为true

  1. bool isValid(char * s){
  2.     ST st;
  3.     StackInit(&st);
  4.     while(*s)
  5.     {
  6.         if(*s=='('||*s=='{'||*s=='[')
  7.         {
  8.             StackPush(&st,*s);//压栈
  9.         }
  10.         else//比较时的情况
  11.         {
  12.             if(StackEmpty(&st))
  13.                 return false;  
  14.             else if(StackTop(&st)=='('&&*s!=')')//访问栈顶元素
  15.             {
  16.                 return false;
  17.             }
  18.             else if(StackTop(&st)=='{'&&*s!='}')
  19.             {
  20.                 return false;
  21.             }
  22.             else if(StackTop(&st)=='['&&*s!=']')
  23.             {
  24.                 return false;
  25.             }
  26.             StackPop(&st);
  27.         }
  28.         ++s;
  29.     }
  30.     if(!StackEmpty(&st))
  31.         return false;
  32.     StackDestroy(&st);
  33.     return true;
  34. }

注：上述代码还需要将栈的实现的代码拷贝一份上去。

2、用队列实现栈

入栈：选择非空队列进行入栈

出栈：队列中只留一个元素，将其他元素Pop至另一个队列，再对那个遗留的元素执行出队列操作即可模拟出栈动作

  1. typedef struct {
  2.     Queue q1;
  3.     Queue q2;
  4. } MyStack;
  5. MyStack* myStackCreate() {
  6.     MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
  7.     QueueInit(&obj->q1);
  8.     QueueInit(&obj->q2);
  9.     return obj;
  10. }
  11.  
  12. void myStackPush(MyStack* obj, int x) {
  13.     if(!QueueEmpty(&obj->q1))
  14.     {
  15.         QueuePush(&obj->q1,x);//入队,尾插
  16.     }
  17.     else
  18.     {
  19.         QueuePush(&obj->q2,x);//入队,尾插
  20.     }
  21. }
  22.  
  23. int myStackPop(MyStack* obj) {
  24.     Queue* empty=&obj->q1;
  25.     Queue* unEmpty=&obj->q2;
  26.     if(QueueEmpty(&obj->q2))
  27.     {
  28.         empty=&obj->q2;
  29.         unEmpty=&obj->q1;
  30.     }
  31.     while(QueueSize(unEmpty)>1)//将非空元素导入到空队列，留下最后一个
  32.     {
  33.         QueuePush(empty,QueueFront(unEmpty));//入队,尾插
  34.         QueuePop(unEmpty);//出队（头删）
  35.     }
  36.     int top=QueueFront(unEmpty);
  37.     QueuePop(unEmpty);//出队（头删）
  38.     return top;
  39. }
  40.  
  41. int myStackTop(MyStack* obj) {
  42.     if(!QueueEmpty(&obj->q1))
  43.     {
  44.         return QueueBack(&obj->q1);//访问队尾数据
  45.     }
  46.     else
  47.     {
  48.         return QueueBack(&obj->q2);//访问队尾数据
  49.     }
  50. }
  51.  
  52. bool myStackEmpty(MyStack* obj) {
  53.     return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
  54. }
  55.  
  56. void myStackFree(MyStack* obj) {
  57.     QueueDestroy(&obj->q1);//销毁
  58.     QueueDestroy(&obj->q2);//销毁
  59.     free(obj);
  60. }

注：上述代码还需要将队列的实现的代码拷贝一份上去。

3、用栈实现队列

现在有两个栈，第一个栈用于入栈、出栈至第二个栈的操作，第二个栈仅用于出栈操作。

入栈：在第一个栈中压入数据

出栈：如果第二个栈为空，则第一个栈中 数据全部出栈至第二个栈，由第二个栈专门执行出栈操作。等第二个栈再次为空，再次执行上述动作

  1. MyQueue* myQueueCreate() {
  2.     MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
  3.     StackInit(&obj->st1);
  4.     StackInit(&obj->st2);
  5.     return obj;
  6. }
  7.  
  8. void myQueuePush(MyQueue* obj, int x) {
  9.     StackPush(&obj->st1, x);//压栈
  10. }
  11.  
  12. int myQueuePop(MyQueue* obj) {
  13.     if(StackEmpty(&obj->st2))
  14.     {
  15.         while(!StackEmpty(&obj->st1))
  16.         {
  17.             StackPush(&obj->st2, StackTop(&obj->st1));//压栈
  18.             StackPop(&obj->st1);
  19.         }
  20.     }
  21.     int val=StackTop(&obj->st2);
  22.     StackPop(&obj->st2);
  23.     return val;
  24. }
  25.  
  26. int myQueuePeek(MyQueue* obj) {
  27.     if(StackEmpty(&obj->st2))
  28.     {
  29.         while(!StackEmpty(&obj->st1))
  30.         {
  31.             StackPush(&obj->st2, StackTop(&obj->st1));//压栈
  32.             StackPop(&obj->st1);
  33.         }
  34.     }
  35.     return StackTop(&obj->st2);
  36. }
  37.  
  38. bool myQueueEmpty(MyQueue* obj) {
  39.     return StackEmpty(&obj->st1)&&StackEmpty(&obj->st2);
  40. }
  41.  
  42. void myQueueFree(MyQueue* obj) {
  43.     StackDestroy(&obj->st1);
  44.     StackDestroy(&obj->st2);
  45.     free(obj);
  46. }

注：上述代码还需要将栈的实现的代码拷贝一份上去。

4、设计循环队列

  1. typedef struct {
  2.     int* arr;
  3.     int front;//记录首
  4.     int tail;//记录尾的下一个
  5.     int capacity;//用于处理边界问题的一个变量
  6. } MyCircularQueue;
  7. MyCircularQueue* myCircularQueueCreate(int k) {
  8.     MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
  9.     obj->arr=(int*)malloc(sizeof(int)*(k+1));
  10.     obj->front=obj->tail=0;
  11.     obj->capacity=k+1;//这里一定要写成k+1，写成k的话,后续处理边界问题要额外考虑分支情况
  12.     return obj;
  13. }
  14. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
  15.     return obj->front==obj->tail;
  16. }
  17.  
  18. bool myCircularQueueIsFull(MyCircularQueue* obj) {
  19.     return (obj->tail+1)%(obj->capacity)==obj->front;
  20. }
  21. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
  22.     if(myCircularQueueIsFull(obj))
  23.         return false;
  24.     obj->arr[obj->tail]=value;
  25.     obj->tail++;
  26.     obj->tail%=obj->capacity;
  27.     return true;
  28. }
  29.  
  30. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
  31.     if(myCircularQueueIsEmpty(obj))
  32.         return false;
  33.     obj->front++;
  34.     obj->front%=obj->capacity;
  35.     return true;
  36. }
  37.  
  38. int myCircularQueueFront(MyCircularQueue* obj) {
  39.     if(myCircularQueueIsEmpty(obj))
  40.         return -1;
  41.     return obj->arr[obj->front];
  42. }
  43.  
  44. int myCircularQueueRear(MyCircularQueue* obj) {
  45.     if(myCircularQueueIsEmpty(obj))
  46.         return -1;
  47.     return obj->arr[(obj->tail-1+obj->capacity)%obj->capacity];
  48. }
  49. void myCircularQueueFree(MyCircularQueue* obj) {
  50.     free(obj->arr);
  51.     obj->arr=NULL;
  52.     free(obj);
  53. }

因为循环队列无法区分队列为空和为满的情况，因为为空和未满，首位下标是一样的。

所以这道题有两种解法，计数确定栈空栈满，或者多开辟一个空间。本题采用后者。

可选的数据结构也有两种，顺序和链表。本题采用顺序。

上表为队列满的情况，无法再执行插入。运用顺序表，本题的难点在于如何处理tail和front在数组尾部的情况。

强烈建议在初始化的接口中将capacity定义为k+1，因为入队出队接口中%capacity后，可以同时满足正常和极端位置下的情况。（详见代码，一读就懂，后续读者可以逝一下将capacity定义为k，感受下区别）

capacity定义为k时的代码如下：

  1. typedef struct {
  2.     int* arr;
  3.     int front;//记录首
  4.     int tail;//记录尾的下一个
  5.     int capacity;//总容量
  6. } MyCircularQueue;
  7.  
  8.  
  9. MyCircularQueue* myCircularQueueCreate(int k) {
  10.     MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
  11.     obj->arr=(int*)malloc(sizeof(int)*(k+1));
  12.     obj->front=obj->tail=0;
  13.     obj->capacity=k;
  14.     return obj;
  15. }
  16. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
  17.     return obj->front==obj->tail;
  18. }
  19.  
  20. bool myCircularQueueIsFull(MyCircularQueue* obj) {
  21.     return (obj->tail+1)%(obj->capacity+1)==obj->front;
  22. }
  23. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
  24.     if(myCircularQueueIsFull(obj))
  25.         return false;
  26.     obj->arr[obj->tail]=value;
  27.     obj->tail++;
  28.     if(obj->tail>obj->capacity)
  29.         obj->tail=obj->tail%obj->capacity-1;
  30.     return true;
  31. }
  32.  
  33. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
  34.     if(myCircularQueueIsEmpty(obj))
  35.         return false;
  36.     obj->front++;
  37.     if(obj->front>obj->capacity)
  38.         obj->front=obj->front%obj->capacity-1;
  39.     return true;
  40. }
  41.  
  42. int myCircularQueueFront(MyCircularQueue* obj) {
  43.     if(myCircularQueueIsEmpty(obj))
  44.         return -1;
  45.     return obj->arr[obj->front];
  46. }
  47.  
  48. int myCircularQueueRear(MyCircularQueue* obj) {
  49.     if(myCircularQueueIsEmpty(obj))
  50.         return -1;
  51.     if(obj->tail!=0)
  52.         return obj->arr[(obj->tail-1+obj->capacity)%obj->capacity];
  53.     return obj->arr[obj->capacity];
  54. }
  55. void myCircularQueueFree(MyCircularQueue* obj) {
  56.     free(obj->arr);
  57.     obj->arr=NULL;
  58.     free(obj);
  59. }

主要区别就是入队出队代码，常规情况和边界情况不能统一。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Li_阴宅/article/detail/904137
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号