• 栈和队列(栈和队列的实现、两个队列实现栈、两个栈实现一个队列等经典例题)

    ꧁ 大家好，我是 兔7 ，一位努力学习C++的博主~ ꧂

    ☙ 如果文章知识点有错误的地方，请指正！和大家一起学习，一起进步❧

    🚀 如有不懂，可以随时向我提问，我会全力讲解~💬

    🔥 如果感觉博主的文章还不错的话，希望大家关注、点赞、收藏三连支持一下博主哦~！👀

    🔥 你们的支持是我创作的动力！⛅

    🧸 我相信现在的努力的艰辛，都是为以后的美好最好的见证！⭐

    🧸 人的心态决定姿态！⭐

    🚀 本文章CSDN首发！✍

    目录

    0. 前言

    1. 栈

    1.1 栈的概念及结构

    1.2 栈的实现

    Stack.h

    Stack.c

    2. 队列

    2.1 队列的概念及结构

    2.2队列的实现

    Queue.h

    Queue.c

    3. 栈和队列面试题

    0. 前言

            此博客为博主以后复习的资料，所以大家放心学习，总结的很全面，每段代码都给大家发了出来，大家如果有疑问可以尝试去调试。

            大家一定要认真看图，图里的文字都是精华，好多的细节都在图中展示、写出来了，所以大家一定要仔细哦~

            感谢大家对我的支持，感谢大家的喜欢， 兔7 祝大家在学习的路上一路顺利，生活的路上顺心顺意~！

    1. 栈

    1.1 栈的概念及结构

    栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

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

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

    1.2 栈的实现

            栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的 代价比较小。

    Stack.h

    1. #pragma once
    2.  
    3.  
    4. #include 
    5. #include 
    6. #include 
    7. #include 
    8.  
    9. typedef int STDataType;
    10.  
    11. typedef struct Stack
    12. {
    13. 	STDataType* a;
    14. 	int top;
    15. 	int capacity;
    16. }Stack;
    17.  
    18.  
    19. void StackInit(Stack* ps);
    20.  
    21. void StackDestroy(Stack* ps);
    22.  
    23. void StackPush(Stack* ps, STDataType x);
    24.  
    25. void StackPop(Stack* ps);
    26.  
    27. STDataType StackTop(Stack* ps);
    28.  
    29. bool IsEmpty(Stack* ps);
    30.  
    31. int Size(Stack* ps);

    Stack.c

    1. #include "Stack.h"
    2.  
    3.  
    4. void StackInit(Stack* ps)
    5. {
    6. 	assert(ps);
    7.  
    8. 	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
    9. 	ps->top = 0;
    10. 	ps->capacity = 4;
    11. }
    12.  
    13. void StackDestroy(Stack* ps)
    14. {
    15. 	assert(ps);
    16.  
    17. 	free(ps->a);
    18. 	ps->a = NULL;
    19. 	ps->top = 0;
    20. 	ps->capacity = 0;
    21. }
    22.  
    23. bool IsEmpty(Stack* ps)
    24. {
    25. 	assert(ps);
    26. 	return ps->top == 0;
    27. }
    28.  
    29.  
    30. void StackPush(Stack* ps, STDataType x)
    31. {
    32. 	assert(ps);
    33.  
    34. 	if (ps->top == ps->capacity)
    35. 	{
    36. 		int newcapacity = ps->capacity * 2;
    37. 		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
    38. 		if (tmp == NULL)
    39. 		{
    40. 			perror("StackPush error");
    41. 			exit(-1);
    42. 		}
    43. 		ps->a = tmp;
    44. 		ps->capacity = newcapacity;
    45. 	}
    46.  
    47. 	ps->a[ps->top] = x;
    48. 	ps->top++;
    49. }
    50.  
    51. void StackPop(Stack* ps)
    52. {
    53. 	assert(ps);
    54. 	assert(!IsEmpty(ps));
    55.  
    56. 	ps->top--;
    57. }
    58.  
    59. STDataType StackTop(Stack* ps)
    60. {
    61. 	assert(ps);
    62. 	assert(IsEmpty(ps));
    63.  
    64. 	return ps->a[ps->top - 1];
    65. }
    66.  
    67.  
    68. int Size(Stack* ps)
    69. {
    70. 	return ps->top;
    71. }
    72.  
    73.  
    74. void Print(Stack* ps)
    75. {
    76. 	assert(ps);
    77.  
    78. 	int top = ps->top - 1;
    79. 	while (top >= 0)
    80. 	{
    81. 		printf("%d ", ps->a[top--]);
    82. 	}
    83. 	printf("\n");
    84. }

    2. 队列

    2.1 队列的概念及结构

            队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头

    2.2队列的实现

            队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

    Queue.h

    1. #pragma once
    2.  
    3.  
    4. #include 
    5. #include 
    6. #include 
    7.  
    8. typedef int QDataType;
    9. typedef struct QueueNode
    10. {
    11. 	struct QueueNode* next;
    12. 	QDataType data;
    13. }QueueNode;
    14.  
    15.  
    16. typedef struct Queue
    17. {
    18. 	QueueNode* head;
    19. 	QueueNode* tail;
    20. }Queue;
    21.  
    22.  
    23. void QueueInit(Queue* pq);
    24.  
    25. void QueueDestroy(Queue* pq);
    26.  
    27. void QueuePush(Queue* pq, QDataType x);
    28.  
    29. void QueuePop(Queue* pq);
    30.  
    31. QDataType QueueFront(Queue* pq);
    32.  
    33. QDataType QueueBack(Queue* pq);
    34.  
    35. int Size(Queue* pq);
    36.  
    37. int QueueEmpty(Queue* pq);
    38.  
    39. void Print(Queue* pq);

    Queue.c

    1. #include "Queue.h"
    2.  
    3.  
    4. void QueueInit(Queue* pq)
    5. {
    6. 	assert(pq);
    7.  
    8. 	pq->head = pq->tail = NULL;
    9. }
    10.  
    11. void QueueDestroy(Queue* pq)
    12. {
    13. 	assert(pq);
    14.  
    15. 	QueueNode* cur = pq->head;
    16. 	while (cur)
    17. 	{
    18. 		QueueNode* del = cur;
    19. 		cur = cur->next;
    20. 		free(del);
    21. 	}
    22. 	pq->head = pq->tail = NULL;
    23. }
    24.  
    25. void QueuePush(Queue* pq, QDataType x)
    26. {
    27. 	assert(pq);
    28.  
    29. 	QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    30. 	if (newNode == NULL)
    31. 	{
    32. 		perror("QueuePush error");
    33. 		exit(-1);
    34. 	}
    35. 	newNode->data = x;
    36. 	newNode->next = NULL;
    37.  
    38. 	if (pq->tail == NULL)
    39. 	{
    40. 		pq->head = pq->tail = newNode;
    41. 	}
    42. 	else
    43. 	{
    44. 		pq->tail->next = newNode;
    45. 		pq->tail = newNode;
    46. 	}
    47. }
    48.  
    49. void QueuePop(Queue* pq)
    50. {
    51. 	assert(pq);
    52. 	assert(!QueueEmpty(pq));
    53.  
    54. 	if (pq->head->next == NULL)
    55. 	{
    56. 		free(pq->head);
    57. 		pq->head = pq->tail = NULL;
    58. 	}
    59. 	else
    60. 	{
    61. 		QueueNode* del = pq->head;
    62. 		pq->head = del->next;;
    63. 		free(del);
    64. 	}
    65. }
    66.  
    67. QDataType QueueFront(Queue* pq)
    68. {
    69. 	assert(pq);
    70. 	assert(!QueueEmpty(pq));
    71.  
    72. 	return pq->head->data;
    73. }
    74.  
    75. QDataType QueueBack(Queue* pq)
    76. {
    77. 	assert(pq);
    78.  
    79. 	return pq->tail->data;
    80. }
    81.  
    82. int Size(Queue* pq)
    83. {
    84. 	assert(pq);
    85.  
    86. 	int n = 0;
    87. 	QueueNode* cur = pq->head;
    88. 	while (cur)
    89. 	{
    90. 		n++;
    91. 		cur = cur->next;
    92. 	}
    93. 	return n;
    94. }
    95.  
    96. int QueueEmpty(Queue* pq)
    97. {
    98. 	assert(pq);
    99.  
    100. 	return (pq->head == pq->tail) && (pq->head == NULL) && (pq->tail == NULL);
    101. }
    102.  
    103.  
    104. void Print(Queue* pq)
    105. {
    106. 	QueueNode* cur = pq->head;
    107. 	while (cur)
    108. 	{
    109. 		printf("%d ", cur->data);
    110. 		cur = cur->next;
    111. 	}
    112. 	printf("\n");
    113. }

            实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型 时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。

    3. 栈和队列面试题

    20. 有效的括号

            先找左括号，找到左括号入栈。如果有左括号，再找到右括号就将左括号出栈。如果是右括号的一种，栈顶的是左括号的另外一种，那么就有问题。

    1. class Solution {
    2. public:
    3.     bool isValid(string s) {
    4.         stack<char> st;
    5.         for(auto ch : s)
    6.         {
    7.             if(ch == '{' || ch == '[' || ch == '(')
    8.             {
    9.                 st.push(ch);
    10.             }
    11.             else
    12.             {
    13.                 if(st.empty())
    14.                 {
    15.                     return false;
    16.                 }
    17.                 if((ch == '}' && st.top() == '{')
    18.                 || (ch == ']' && st.top() == '[')
    19.                 || (ch == ')' && st.top() == '('))
    20.                 {
    21.                     st.pop();
    22.                 }
    23.                 else
    24.                 {
    25.                     return false;
    26.                 }
    27.             }
    28.         }
    29.         return st.empty();
    30.     }
    31. };

    225. 用队列实现栈

     

            以此类推，当pop的时候将除了最后一个数据从队列里出队列，进入另一个队列中，然后出队列，这就用队列实现了栈的功能。

            具体代码实现如下：

    1. class MyStack {
    2. public:
    3.     MyStack() {
    4.     }
    5.     
    6.     void push(int x) {
    7.         if(q1.empty())
    8.             q2.push(x);
    9.         else
    10.             q1.push(x);
    11.     }
    12.     
    13.     int pop() {
    14.         // 让q1是空，q2不是空
    15.         if(q2.empty())
    16.         {
    17.             queue<int> tmp = q1;
    18.             q1 = q2;
    19.             q2 = tmp;
    20.         }
    21.         while(q2.size() > 1)
    22.         {
    23.             q1.push(q2.front());
    24.             q2.pop();
    25.         }
    26.         int del = q2.front();
    27.         q2.pop();
    28.         return del;
    29.     }
    30.     
    31.     int top() {
    32.         if(q1.empty())
    33.             return q2.back();
    34.         else
    35.             return q1.back();
    36.     }
    37.     
    38.     bool empty() {
    39.         return q1.empty() && q2.empty();
    40.     }
    41. private:
    42.     queue<int> q1;
    43.     queue<int> q2;
    44. };
    45.  
    46. /**
    47.  * Your MyStack object will be instantiated and called as such:
    48.  * MyStack* obj = new MyStack();
    49.  * obj->push(x);
    50.  * int param_2 = obj->pop();
    51.  * int param_3 = obj->top();
    52.  * bool param_4 = obj->empty();
    53.  */

    232. 用栈实现队列

            这里上面的是用来出队列的，下面的是用来入队列的，上面的出栈到最后一个，然后将最后一个pop掉，然后再从入队列的入到出队列的中，如此往复就用栈实现了队列。

            具体代码实现如下：

    1. class MyQueue {
    2. public:
    3.     MyQueue() {
    4.     }
    5.     
    6.     void push(int x) {
    7.         s1.push(x);
    8.     }
    9.     
    10.     int pop() {
    11.         while(s1.size() > 1)
    12.         {
    13.             s2.push(s1.top());
    14.             s1.pop();
    15.         }
    16.         int tmp = s1.top();
    17.         s1.pop();
    18.         while(s2.size())
    19.         {
    20.             s1.push(s2.top());
    21.             s2.pop();
    22.         }
    23.         return tmp;
    24.     }
    25.     
    26.     int peek() {
    27.         while(s1.size())
    28.         {
    29.             s2.push(s1.top());
    30.             s1.pop();
    31.         }
    32.         int tmp = s2.top();
    33.         while(s2.size())
    34.         {
    35.             s1.push(s2.top());
    36.             s2.pop();
    37.         }
    38.         return tmp;
    39.     }
    40.     
    41.     bool empty() {
    42.         return s1.empty() && s1.empty();
    43.     }
    44. private:
    45.     stack<int> s1;
    46.     stack<int> s2;
    47. };
    48.  
    49. /**
    50.  * Your MyQueue object will be instantiated and called as such:
    51.  * MyQueue* obj = new MyQueue();
    52.  * obj->push(x);
    53.  * int param_2 = obj->pop();
    54.  * int param_3 = obj->peek();
    55.  * bool param_4 = obj->empty();
    56.  */

    622. 设计循环队列

            我这里设置的循环队列是通过数组来实现的，通过多开一个空间，来进行判断队列的空和满，也就是数组的头和尾是一个位置就是空，尾的下一个位置是头就是满，当然这里需要通过取模来完成，其中有一些细节需要完善，然后push的时候就是头到下一个位置，pop的时候就是尾巴向前走一个位置。

            具体的实现看下面的代码，当然这里的代码是我写的思路，当然也会有其它思路。

    1. class MyCircularQueue {
    2. public:
    3.     MyCircularQueue(int k) {
    4.         n = k;
    5.         a = (int*)malloc(sizeof(int) * (k + 1));
    6.         head = tail = 0;
    7.     }
    8.     
    9.     bool enQueue(int value) {
    10.         if(isFull())
    11.             return false;
    12.         a[tail] = value;
    13.         tail++;
    14.         if(tail >= n)
    15.             tail %= (n+1);
    16.         return true;
    17.     }
    18.     
    19.     bool deQueue() {
    20.         if(isEmpty())
    21.             return false;
    22.         head++;
    23.         if(head >= n)
    24.             head %= (n+1);
    25.         return true;
    26.     }
    27.     
    28.     int Front() {
    29.         if(head == tail)
    30.             return -1;
    31.         return a[head];
    32.     }
    33.     
    34.     int Rear() {
    35.         if(head == tail)
    36.             return -1;
    37.         int T = tail - 1;
    38.         if(T < 0)
    39.             T = n;
    40.         return a[T];
    41.     }
    42.     
    43.     bool isEmpty() {
    44.         return head == tail;
    45.     }
    46.     
    47.     bool isFull() {
    48.         return head == (tail+1)%(n+1);
    49.     }
    50. private:
    51.     int* a;
    52.     int n;//个数
    53.     int head;
    54.     int tail;
    55. };
    56.  
    57. /**
    58.  * Your MyCircularQueue object will be instantiated and called as such:
    59.  * MyCircularQueue* obj = new MyCircularQueue(k);
    60.  * bool param_1 = obj->enQueue(value);
    61.  * bool param_2 = obj->deQueue();
    62.  * int param_3 = obj->Front();
    63.  * int param_4 = obj->Rear();
    64.  * bool param_5 = obj->isEmpty();
    65.  * bool param_6 = obj->isFull();
    66.  */

            如上就是 栈和队列 的所有知识，如果大家喜欢看此文章并且有收获，可以支持下 兔7 ，给 兔7 三连加关注，你的关注是对我最大的鼓励，也是我的创作动力~！

            再次感谢大家观看，感谢大家支持！

  • 相关阅读:
    Git统计提交代码量
    滴滴可观测平台 Metrics 指标实时计算如何实现了又准又省？
    给 Helm 提一个 PR，重温开源项目参与过程
    在CentOS7下安装Oracle11教程
    线性表的应用 —— 静态链表
    单核与多核CPU的区别与联系-结合ESP32浅谈
    七个用于云原生世界的Java框架
    NumPy 切片和索引
    百度首个江苏智算中心落地 携手盐城共建200P算力规模
    IDEA乱码问题解决
  • 原文地址：https://blog.csdn.net/weixin_69725192/article/details/126449709