• 栈和队列基础

    栈和队列也是一种数据结构，和顺序表、链表一样，属于线性表，也就是说它们的逻辑结构是线性的。

    栈基础知识介绍

     看了上面的图示，是不是感觉栈和顺序表有点类似，都是挨着挨着往进存数据，但不同的是顺序表可以在任意位置插入和删除数据（虽然效率不同），但是栈只能在固定的一端进行该操作。

    进行插入和删除的一端叫栈顶，另一端叫栈底。栈中的元素都遵循先进后出的原则。因为先进栈的在栈底，后进栈的在栈顶，所以出去的时候顺序就和入栈时相反了。（如图所示）

    压栈 \ 入栈：往栈顶插入数据；  出栈：删除栈顶数据。

    注意这里说的栈是数据结构，不要和操作系统内存区域划分中的栈搞混了。

    经常有人将系统中的栈和数据结构中的栈搞混，下面我来简单区分一下两者。

     操作系统中的栈里面放的是局部变量和函数形参等东西，而数据结构说的栈是储存在堆上的，因为它是动态开辟的数据。   在写递归调用、斐波那契数等函数时，有时会发生栈溢出的现象，是因为栈的空间较小，所以我们一般将其改成迭代的方式，或用栈将其改为循环解决。

    栈的实现

    栈一般用数组来实现，但空间节省要求高时用链表。

    有人可能会问为什么不都用链表？链表不仅能节省空间，而且不用扩容，不是更好吗？

    单次来说，链表效率确实比顺序表高一点，但是整体而言，顺序表的性能效率甚至要高于链表，这涉及CPU高速缓存命中率了。最关键的是顺序表可以用下标来访问，但是链表不行。因此这里最好用数组。

    栈的实现代码与之前顺序表的很相似，而且它更为简单，因为栈遵循先进后出的原则，只能从栈顶插入删除数据，所以不存在头插头删和指定位置插入删除的操作。

    代码如下：

    1. //Stack.h（头文件）
    2.  
    3. #pragma once
    4.  
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10.  
    11. typedef int STDataType;
    12. typedef struct stack
    13. {
    14. 	STDataType* a;
    15. 	int top;
    16. 	int capacity;
    17. }ST;
    18.  
    19. void StackInit(ST* ps);
    20. void StackDestory(ST* ps);
    21.  
    22. void StackPush(ST* ps, STDataType x);
    23. void StackPop(ST* ps);
    24.  
    25. bool StackEmpty(ST* ps);
    26. STDataType StackTop(ST* ps);
    27. int StackSize(ST* ps);
    1. //Stack.c （栈实现接口）
    2.  
    3. #include"stack.h"
    4.  
    5. void StackInit(ST* ps)
    6. {
    7. 	assert(ps);
    8. 	ps->a = NULL;
    9. 	ps->top = ps->capacity = 0;
    10. }
    11.  
    12. void StackDestory(ST* ps)
    13. {
    14. 	assert(ps);
    15. 	free(ps->a);
    16. 	ps->a = NULL;
    17. 	ps->top = ps->capacity = 0;
    18. }
    19.  
    20. void StackPush(ST* ps, STDataType x)
    21. {
    22. 	assert(ps);
    23. 	if (ps->top == ps->capacity)
    24. 	{
    25. 		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    26. 		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
    27. 		if (tmp == NULL)
    28. 		{
    29. 			perror("malloc fail");
    30. 			exit(-1);
    31. 		}
    32. 		ps->a = tmp;
    33. 		ps->capacity = newcapacity;
    34. 	}
    35. 	ps->a[ps->top] = x;
    36. 	ps->top++;
    37. }
    38.  
    39. bool StackEmpty(ST* ps)
    40. {
    41. 	assert(ps);
    42. 	return ps->top == 0;
    43. }
    44.  
    45. void StackPop(ST* ps)
    46. {
    47. 	assert(ps);
    48. 	assert(!StackEmpty(ps));
    49. 	ps->top--;
    50. }
    51.  
    52. STDataType StackTop(ST* ps)
    53. {
    54. 	assert(ps);
    55. 	assert(!StackEmpty(ps));
    56. 	return ps->a[ps->top - 1];
    57. }
    58.  
    59. int StackSize(ST* ps)
    60. {
    61. 	assert(ps);
    62. 	return ps->top;
    63. }
    1. //test.c （测试函数）
    2.  
    3. #include"stack.h"
    4.  
    5. void Test1()
    6. {
    7. 	ST S;
    8. 	StackInit(&S);
    9.  
    10. 	StackPush(&S, 1);
    11. 	StackPush(&S, 2);
    12. 	StackPush(&S, 3);
    13.  
    14. 	STDataType top = StackTop(&S);
    15. 	int num = StackSize(&S);
    16.  
    17. 	printf("%d ", StackTop(&S));
    18. 	StackPop(&S);
    19.  
    20. 	StackPush(&S, 4);
    21. 	StackPush(&S, 5);
    22.  
    23. 	while (!StackEmpty(&S))
    24. 	{
    25. 		printf("%d ", StackTop(&S));
    26. 		StackPop(&S);
    27. 	}
    28. 	printf("\n");
    29.  
    30. 	StackDestory(&S);
    31. }
    32.  
    33. int main()
    34. {
    35. 	Test1();
    36. 	return 0;
    37. }

    栈的相关应用（编程题）

    来看一道编程题了解一下栈在实际中的作用。

    力扣https://leetcode.cn/problems/valid-parentheses/submissions/

     这道题用刚刚所讲的栈的有关知识就可以轻松解决。

    首先左右括号的匹配不仅仅是数个数，类似示例3这种类型不匹配的也是false。

    解题思路：1、先写一个栈的实现函数，将其初始化。 2、用循环来遍历字符串中的每个字符，

    如果是左括号 ： ' { '  ' ( '  ' [ '  就StackPush插入到栈顶，如果是右括号，就将栈顶字符弹出比较，如果匹配就删除栈顶字符并继续循环，直到结束或return false，不匹配直接return false。最后销毁。  3、大体思路是这样的，但还有很多细节上面没有考虑：如果字符串中没有右括号，就会不进入匹配条件，导致最后return true。需要在结尾判断栈是否为空，是return true，不是return false。

    代码如下：（栈的实现上面写了，加到前面即可）

    1. bool isValid(char * s){
    2.     ST P;
    3.     StackInit(&P);
    4.     while(*s)
    5.     {
    6.         if(*s == '{' || *s == '[' || *s == '(')
    7.         {
    8.             StackPush(&P,*s);
    9.         }
    10.         else
    11.         {
    12.             if(StackEmpty(&P))
    13.             {
    14.                 StackDestory(&P);
    15.                 return false;
    16.             }
    17.             char top = StackTop(&P);
    18.             StackPop(&P);
    19.             if(*s != '}' && top == '{' ||
    20.                *s != ']' && top == '[' ||
    21.                *s != ')' && top == '(')
    22.                return false;
    23.         }
    24.         ++s;
    25.     }
    26.     bool flag = StackEmpty(&P);
    27.     StackDestory(&P);
    28.     return flag;
    29. }

    队列基础知识讲解

    队列也是一种线性表，与栈只能在一端插入删除数据不同，队列是在一端插入数据，在另一端删除数据，遵循先进先出的原则。

    队列的先进先出其实蛮符合我们的理解的，先来的先处理比较符合我们日常的逻辑。

    所以队列的现实场景就可以用作抽号机系统。

    队列的实现

    队列的实现我们用链表，因为要在头部删除数据需要挪动数据，这就是比较麻烦的问题了，所以我们用链表实现。

    这里我们用单链表实现，稍微节省一点空间。

    代码如下：

    1. //Queue.h
    2.  
    3. #pragma once
    4.  
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10.  
    11. typedef int QDataType;
    12. typedef struct QueueNode
    13. {
    14. 	struct QueueNode* next;
    15. 	QDataType data;
    16. }QNode;
    17.  
    18. typedef struct Queue
    19. {
    20. 	QNode* head;
    21. 	QNode* tail;
    22. }Queue;
    23.  
    24. void QueueInit(Queue* p);
    25. void QueueDestory(Queue* p);
    26. void QueuePush(Queue* p, QDataType x);
    27. void QueuePop(Queue* p);
    28. QDataType QueueFront(Queue* p);
    29. QDataType QueueBack(Queue* p);
    30. bool QueueEmpty(Queue* p);
    31. int QueueSize(Queue* p);
    1. //Queue.c
    2.  
    3. #include"Queue.h"
    4.  
    5. void QueueInit(Queue* p)
    6. {
    7. 	assert(p);
    8. 	p->head = p->tail = NULL;
    9. }
    10.  
    11. void QueueDestory(Queue* p)
    12. {
    13. 	assert(p);
    14. 	QNode* cur = p->head;
    15. 	while (cur)
    16. 	{
    17. 		QNode* del = cur;
    18. 		cur = cur->next;
    19. 		free(del);
    20. 	}
    21. 	p->head = p->tail = NULL;
    22. }
    23.  
    24. void QueuePush(Queue* p, QDataType x)
    25. {
    26. 	assert(p);
    27. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
    28. 	if (newnode == NULL)
    29. 	{
    30. 		perror("malloc fail");
    31. 		exit(-1);
    32. 	}
    33. 	else
    34. 	{
    35. 		newnode->next = NULL;
    36. 		newnode->data = x;
    37. 	}
    38. 	if (p->tail == NULL)
    39. 	{
    40. 		p->head = p->tail = newnode;
    41. 	}
    42. 	else
    43. 	{
    44. 		p->tail->next = newnode;
    45. 		p->tail = p->tail->next;
    46. 	}
    47. }
    48.  
    49. void QueuePop(Queue* p)
    50. {
    51. 	assert(p);
    52. 	assert(!QueueEmpty(p));
    53. 	if (p->head->next == NULL)
    54. 	{
    55. 		free(p->head);
    56. 		p->head = p->tail = NULL;
    57. 	}
    58.     else
    59.     {
    60.     	QNode* del = p->head;
    61. 	    p->head = p->head->next;
    62. 	    free(del);
    63.     }
    64. }
    65.  
    66. QDataType QueueFront(Queue* p)
    67. {
    68. 	assert(p);
    69. 	assert(!QueueEmpty(p));
    70. 	return p->head->data;
    71. }
    72. QDataType QueueBack(Queue* p)
    73. {
    74. 	assert(p);
    75. 	assert(!QueueEmpty(p));
    76. 	return p->tail->data;
    77. }
    78.  
    79. bool QueueEmpty(Queue* p)
    80. {
    81. 	assert(p);
    82. 	return p->head == NULL;
    83. }
    84. int QueueSize(Queue* p)
    85. {
    86. 	assert(p);
    87. 	int count = 0;
    88. 	QNode* cur = p->head;
    89. 	while (cur)
    90. 	{
    91. 		count++;
    92. 		cur = cur->next;
    93. 	}
    94. 	return count;
    95. }
    1. //test.c
    2.  
    3. void Test2()
    4. {
    5. 	Queue S;
    6. 	QueueInit(&S);
    7. 	QueuePush(&S, 1);
    8. 	QueuePush(&S, 2);
    9. 	QueuePush(&S, 3);
    10. 	QueuePush(&S, 4);
    11.  
    12. 	QueuePop(&S);
    13.  
    14. 	QDataType front = QueueFront(&S);
    15. 	QDataType back = QueueBack(&S);
    16. 	int num = QueueSize(&S);
    17. 	QueueDestory(&S);
    18. }

    栈和队列相关笔试题

    CSDNicon-default.png?t=M666https://mp.csdn.net/mp_blog/creation/editor/126172201?spm=1000.2115.3001.4503

     这道题要用两个队列实现栈，思路其实很简单，栈和队列处理数据的方式是相反的，栈是一端处理，先进后出；队列是两端处理，先进先出。

    要想实现队列到栈的处理数据方式，就要用两个队列倒数据。用一个队列存储数据，另一个队列为空，需要取出或删除数据（对于栈来说是栈顶）就要将非空队列的数据倒入空队列，将非空队列的最后一个数据取出或删除即可。

     代码如下：（先将之前写的队列实现函数放在OJ前面）

    1. typedef struct {
    2.     Queue q1;
    3.     Queue q2;
    4. } MyStack;
    5.  
    6.  
    7. MyStack* myStackCreate() {
    8.     MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
    9.     QueueInit(&obj->q1);
    10.     QueueInit(&obj->q2);
    11.     return obj;
    12. }
    13.  
    14. void myStackPush(MyStack* obj, int x) {
    15.     if(!QueueEmpty(&obj->q1))
    16.     {
    17.         QueuePush(&obj->q1,x);
    18.     }
    19.     else
    20.     {
    21.         QueuePush(&obj->q2,x);
    22.     }
    23. }
    24.  
    25. int myStackPop(MyStack* obj) {
    26.     Queue* empty = &obj->q1;
    27.     Queue* nonempty = &obj->q2;
    28.     if(!QueueEmpty(&obj->q1))
    29.     {
    30.         empty = &obj->q2;
    31.         nonempty = &obj->q1;
    32.     }
    33.  
    34.     while(QueueSize(nonempty) > 1)
    35.     {
    36.         QueuePush(empty,QueueFront(nonempty));
    37.         QueuePop(nonempty);
    38.     }
    39.     int top = QueueFront(nonempty);
    40.     QueuePop(nonempty);
    41.     return top;
    42. }
    43.  
    44. int myStackTop(MyStack* obj) {
    45.      if(!QueueEmpty(&obj->q1))
    46.     {
    47.        return QueueBack(&obj->q1);
    48.     }
    49.     else
    50.     {
    51.         return QueueBack(&obj->q2);
    52.     }
    53.  
    54. }
    55.  
    56. bool myStackEmpty(MyStack* obj) {
    57.     return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
    58. }
    59.  
    60. void myStackFree(MyStack* obj) {
    61.     QueueDestory(&obj->q1);
    62.     QueueDestory(&obj->q2);
    63.  
    64.     free(obj);
    65.     obj = NULL;
    66. }

    力扣icon-default.png?t=M666https://leetcode.cn/problems/implement-queue-using-stacks/

     这道题和上一道刚好相反，是用两个栈实现队列。

    大体思路是一致的，就是倒数据的顺序改变一下。

     创建两个栈，push栈用来接收插入数据，pop栈用来取出或删除数据（栈中数据先进后出，push到pop中顺序逆置了）

    代码如下：（栈的实现函数写在OJ前面）

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

    力扣icon-default.png?t=M666https://leetcode.cn/problems/design-circular-queue/

     设计一个循环队列，从逻辑结构上来说是环状的。

     

     但物理结构还是线性表，还是队列。

    这道题的关键在于判断队列的空与满，什么时候空，什么时候满。

    给两个指针front与back，front指向头的位置（下标为0），尾指针back指向最后一个位置，这样设计就有一个缺陷。因为back始终是front的后一个，按上面设计的话，back在下标为0的位置时，front下标是-1，就会带来诸多不便和问题。

    所以将back设计为最后一个位置的后一个。但是这样也还是有问题，因为是循环队列，back到最后一个位置时就跳回下标为0的位置了。此时就不好判断队列为空还是为满了，因为front == back 时，不能判断back是到最后一个位置了（队列满了）还是队列为空。

    此时有两种解决思路：

    一、增加一个size变量，用来记录队列中元素个数。这样就可以解决上面front==back的问题。

    二、增加一个空间（可以存储数据），比如有5个元素，那就开6个空间，剩一个当作最后一个，也就是back的位置。

    最后一个问题是用链表还是用数组，都可以，但是这里还是用数组更好一点，链表在细节处理上会有诸多问题。

    代码如下：

    1. typedef struct {
    2.     int* a;
    3.     int front;
    4.     int back;
    5.     int N;//空间的大小
    6. } MyCircularQueue;
    7.  
    8.  
    9. MyCircularQueue* myCircularQueueCreate(int k) {
    10.     MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    11.     obj->a = (int*)malloc(sizeof(int)*(k+1));
    12.     obj->front = obj->back = 0;
    13.     obj->N = k+1;
    14.     return obj;
    15. }
    16.  
    17. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    18.     return obj->front == obj->back;
    19. }
    20.  
    21. bool myCircularQueueIsFull(MyCircularQueue* obj) {
    22.     return obj->front == ( (obj->back+1) % obj->N);
    23. }
    24.  
    25. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    26.     if(!myCircularQueueIsFull(obj))
    27.     {
    28.         obj->a[obj->back] = value;
    29.         obj->back++;
    30.         //控制back到尾后回到下标为0的位置
    31.         obj->back %= obj->N;
    32.         return true;
    33.     }
    34.     else
    35.     {
    36.         return false;
    37.     }
    38. }
    39.  
    40. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    41.     if(myCircularQueueIsEmpty(obj))
    42.     return false;
    43.     else
    44.     {
    45.         obj->front++;
    46.         //控制front到尾后回到下标为0的位置
    47.         obj->front %= obj->N;
    48.         return true;
    49.     }
    50. }
    51.  
    52. int myCircularQueueFront(MyCircularQueue* obj) {
    53.         if(myCircularQueueIsEmpty(obj))
    54.         return -1;
    55.         else
    56.         return obj->a[obj->front];
    57. }
    58.  
    59. int myCircularQueueRear(MyCircularQueue* obj) {
    60.     if(myCircularQueueIsEmpty(obj))
    61.     return -1;
    62.     //else if(obj->back == 0)
    63.     //{
    64.         //return obj->a[obj->N-1];
    65.     //}
    66.     //else
    67.     //{
    68.         //return obj->a[obj->back-1];
    69.     //}
    70.     else
    71.     {
    72.         return obj->a[(obj->back-1+obj->N) % obj->N];
    73.     }
    74. }
    75.  
    76. void myCircularQueueFree(MyCircularQueue* obj) {
    77.     free(obj->a);
    78.     free(obj);
    79. }

    栈和队列的基础讲解就到这里啦，感谢大家！！！

  • 相关阅读:
    云信产业集团受邀出席2022大健康论坛暨人民康养大会
    flink-sql所有表连接器-1.14
    基于单片机的指纹门禁设计
    药物化合物信息查询系统（精选常用的5个）
    鲸探发布点评：9月8日发售《汝阳黄河巨龙》数字藏品
    前端传String字符串 后端使用enun枚举类出现错误
    子集(c++题解)
    kaptcha验证码组件用法
    虚拟机Centos7 clone 模拟多服务器 nacos集群部署，以及踩坑
    【刷题记录14】Java工程师丨腾讯面试真题（2）
  • 原文地址：https://blog.csdn.net/SAKURAjinx/article/details/126172201