深圳幻海软件技术有限公司 欢迎您！
更多

数据结构--》深入了解栈和队列，让算法更加高效

2023-06-26

元素 队列 cout
        本文将带你深入了解数据结构栈和队列，这两种基础的线性数据结构在算法中的重要性不言而喻。我们将会详细介绍栈和队列的概念、分类、实现以及应用场景，在理解栈和队列的基础上，还将探讨如何通过栈和队列来高效地解决算

        本文将带你深入了解数据结构栈和队列，这两种基础的线性数据结构在算法中的重要性不言而喻。我们将会详细介绍栈和队列的概念、分类、实现以及应用场景，在理解栈和队列的基础上，还将探讨如何通过栈和队列来高效地解决算法问题。

        无论你是初学者还是进阶者，本文将为你提供简单易懂、实用可行的知识点，帮助你更好地掌握栈和队列，进而提升算法解题的能力，开启数据结构与算法的奇妙之旅。

目录

栈的基本概念

栈的顺序存储与链式存储实现

栈在表达式中的应用

队列的基本概念

队列的顺序和链式实现

栈的基本概念

        栈（Stack）是一种线性数据结构，它的特点是只能在末端（栈顶）进行插入和删除操作，并且访问元素时也是从栈顶开始。栈的行为类似于弹簧被压缩的过程，当一个元素被插入栈中时，它就被压入栈底；而当一个元素被删除时，它就从栈顶弹出。

        由于栈的后进先出（Last-In-First-Out，LIFO）的特性，因此它常用于需要“回溯”的算法实现，例如递归、深度优先搜索等。在计算机科学中，栈也被广泛应用于表达式求值、函数调用、内存管理等方面。

栈可以通过数组或链表来实现。通过数组实现的栈称为顺序栈，而通过链表实现的栈称为链式栈。无论通过何种方式实现，栈的基本操作包括入栈（push）、出栈（pop）、查看栈顶元素（top）以及判断栈是否为空（empty）。

栈的基本操作如下：

InitStack(&S)：初始化栈。构造一个空栈S，分配内存空间。

DestroyStack(&L)：销毁栈。销毁并释放栈S所占用的内存空间。

Push(&S,x)：进栈，若栈S未满，则将x加入使之成为栈顶。

Pop(&S,&x)：出栈，若栈S非空，则弹出栈顶元素，并用x返回。

GetTop(S,&x)：读栈顶元素。若栈S非空，则用x返回栈顶元素

其他常用操作：

StackEmpty(S)：判断一个栈S是否为空。若S为空，则返回true，否则返回false。

栈的常考题型为：

回顾重点，其主要内容整理成如下内容： 

栈的顺序存储与链式存储实现

栈可以通过两种方式来实现：顺序存储和链式存储。

        顺序存储的栈，即顺序栈，通常使用数组来实现。在顺序栈中，栈底在数组的低地址处，栈顶在数组的高地址处。栈顶指针（top）是一个整型变量，它指向当前栈顶元素所在的位置。当栈为空时，top的值为-1。入栈操作就是将元素插入到top位置的后面，然后将top指针向上移动一个位置；出栈操作就是将top指针向下移动一个位置，然后将该位置的元素删除。

  1. const int MAX_SIZE = 100; // 定义栈的最大容量
  2. int stack[MAX_SIZE]; // 定义栈数组
  3. int top = -1; // 初始化栈顶指针为-1，表示栈为空
  4.  
  5. // 入栈操作
  6. void push(int x) {
  7.     if (top == MAX_SIZE - 1) { // 栈满，无法继续插入元素
  8.         cout << "Error: Stack overflow!" << endl;
  9.         return;
  10.     }
  11.     top++; // 栈顶指针上移
  12.     stack[top] = x; // 将元素x插入栈顶位置
  13. }
  14.  
  15. // 出栈操作
  16. void pop() {
  17.     if (top == -1) { // 栈空，无法进行出栈操作
  18.         cout << "Error: Stack underflow!" << endl;
  19.         return;
  20.     }
  21.     top--; // 栈顶指针下移
  22. }
  23.  
  24. // 获取栈顶元素
  25. int getTop() {
  26.     if (top == -1) { // 栈为空，栈顶指针无效
  27.         cout << "Error: Stack is empty!" << endl;
  28.         return -1;
  29.     }
  30.     return stack[top]; // 返回栈顶元素
  31. }
  32.  
  33. // 判断栈是否为空
  34. bool isEmpty() {
  35.     return top == -1; // 栈顶指针为-1时，栈为空
  36. }

栈的顺序存储还有一种共享栈的方式。共享栈是一种特殊的顺序栈，它可以同时存储两个栈。具体来说，共享栈有两个栈顶指针，分别指向两个栈的栈顶元素。它们从两端向中间生长，当它们相遇时就表示栈满了。共享栈常用于两个栈需要共用一段连续的存储空间的情况，例如某些操作系统的内核栈和用户栈都共用一个物理内存区域。下面是使用 C++ 实现共享栈的完整代码示例：

  1. #include <iostream>
  2. using namespace std;
  3.  
  4. const int MAX_SIZE = 100; // 定义栈的最大容量
  5.  
  6. int stack[MAX_SIZE]; // 定义存储栈元素的数组
  7. int top1 = -1; // 定义第一个栈的栈顶指针，初始值为-1
  8. int top2 = MAX_SIZE; // 定义第二个栈的栈顶指针，初始值为MAX_SIZE
  9.  
  10. // 向第一个栈中插入元素
  11. void pushStack1(int x) {
  12.     if (top1 + 1 == top2) { // 共享栈已满
  13.         cout << "Error: Stack overflow!" << endl;
  14.         return;
  15.     }
  16.     top1++; // 第一个栈的栈顶指针上移
  17.     stack[top1] = x; // 在第一个栈中插入元素
  18. }
  19.  
  20. // 向第二个栈中插入元素
  21. void pushStack2(int x) {
  22.     if (top1 + 1 == top2) { // 共享栈已满
  23.         cout << "Error: Stack overflow!" << endl;
  24.         return;
  25.     }
  26.     top2--; // 第二个栈的栈顶指针下移
  27.     stack[top2] = x; // 在第二个栈中插入元素
  28. }
  29.  
  30. // 从第一个栈中删除元素
  31. void popStack1() {
  32.     if (top1 == -1) { // 第一个栈为空
  33.         cout << "Error: Stack underflow!" << endl;
  34.         return;
  35.     }
  36.     top1--; // 第一个栈的栈顶指针下移
  37. }
  38.  
  39. // 从第二个栈中删除元素
  40. void popStack2() {
  41.     if (top2 == MAX_SIZE) { // 第二个栈为空
  42.         cout << "Error: Stack underflow!" << endl;
  43.         return;
  44.     }
  45.     top2++; // 第二个栈的栈顶指针上移
  46. }
  47.  
  48. // 获取第一个栈的栈顶元素
  49. int getTop1() {
  50.     if (top1 == -1) { // 第一个栈为空，栈顶指针无效
  51.         cout << "Error: Stack is empty!" << endl;
  52.         return -1;
  53.     }
  54.     return stack[top1]; // 返回第一个栈的栈顶元素
  55. }
  56.  
  57. // 获取第二个栈的栈顶元素
  58. int getTop2() {
  59.     if (top2 == MAX_SIZE) { // 第二个栈为空，栈顶指针无效
  60.         cout << "Error: Stack is empty!" << endl;
  61.         return -1;
  62.     }
  63.     return stack[top2]; // 返回第二个栈的栈顶元素
  64. }
  65.  
  66. // 判断第一个栈是否为空
  67. bool isEmpty1() {
  68.     return top1 == -1; // 第一个栈的栈顶指针为-1时，栈为空
  69. }
  70.  
  71. // 判断第二个栈是否为空
  72. bool isEmpty2() {
  73.     return top2 == MAX_SIZE; // 第二个栈的栈顶指针为MAX_SIZE时，栈为空
  74. }
  75.  
  76. int main() {
  77.     pushStack1(1);
  78.     pushStack1(2);
  79.     pushStack2(3);
  80.     pushStack2(4);
  81.  
  82.     cout << "Top of Stack 1: " << getTop1() << endl;
  83.     cout << "Top of Stack 2: " << getTop2() << endl;
  84.  
  85.     popStack1();
  86.     popStack2();
  87.  
  88.     cout << "Top of Stack 1: " << getTop1() << endl;
  89.     cout << "Top of Stack 2: " << getTop2() << endl;
  90.  
  91.     return 0;
  92. }

在主函数中，我们演示了如何使用 pushStack1()、pushStack2()、popStack1()、popStack2()、getTop1() 和 getTop2() 等操作来对共享栈进行插入、删除和获取元素等操作，并输出了两个栈的栈顶元素。

回顾重点，其主要内容整理成如下内容：  

栈的链式存储实现方式是使用链表来存储栈中的元素。栈顶指针 Top 指向链表的头节点，每插入一个元素就在链表的头部插入一个节点，每删除一个元素就删除链表头部的节点，这样就实现了栈的先进后出的特性。 以下是使用 C++ 语言实现的栈链式存储的完整代码：

  1. #include <iostream>
  2. using namespace std;
  3.  
  4. // 定义链表的节点结构体
  5. struct Node {
  6.     int data; // 节点中存储的数据
  7.     Node* next; // 指向下一个节点的指针
  8. };
  9.  
  10. // 定义链表的头指针和栈顶指针
  11. Node* head = NULL;
  12. Node* top = NULL;
  13.  
  14. // 向栈中插入元素
  15. void push(int x) {
  16.     Node* newNode = new Node; // 创建新节点
  17.     newNode->data = x; // 将元素值赋给新节点的 data 域
  18.     newNode->next = top; // 新节点的 next 指向当前栈顶节点
  19.     top = newNode; // 更新栈顶指针
  20. }
  21.  
  22. // 从栈中删除元素
  23. void pop() {
  24.     if (top == NULL) { // 栈为空，无法删除
  25.         cout << "Error: Stack is empty!" << endl;
  26.         return;
  27.     }
  28.     Node* temp = top; // 暂存当前栈顶节点的地址
  29.     top = top->next; // 更新栈顶指针
  30.     delete temp; // 释放暂存节点内存空间
  31. }
  32.  
  33. // 获取栈顶元素
  34. int getTop() {
  35.     if (top == NULL) { // 栈为空，栈顶指针无效
  36.         cout << "Error: Stack is empty!" << endl;
  37.         return -1;
  38.     }
  39.     return top->data; // 返回栈顶节点的 data 域
  40. }
  41.  
  42. // 判断栈是否为空
  43. bool isEmpty() {
  44.     return top == NULL; // 栈顶指针为空时，栈为空
  45. }
  46.  
  47. int main() {
  48.     push(1);
  49.     push(2);
  50.     push(3);
  51.  
  52.     cout << "Top of Stack: " << getTop() << endl;
  53.  
  54.     pop();
  55.     pop();
  56.  
  57.     cout << "Top of Stack: " << getTop() << endl;
  58.  
  59.     return 0;
  60. }

在主函数中，我们演示了如何使用 push()、pop() 和 getTop() 等操作来对栈进行插入、删除和获取元素等操作，并输出了栈顶元素。 

栈在表达式中的应用

栈在表达式中的应用非常广泛，可以用来进行中缀表达式的转换、计算后缀表达式等操作。中缀表达式是指形如 a+b 或 (a+b)*c-d/(e+f) 这样的表达式，其中运算符位于两个操作数的中间。但是在计算机中，通常采用后缀表达式（也叫逆波兰表达式）来表示算术表达式，即把运算符放在操作数后面，例如 a b + c * d /。

队列的基本概念

        队列是一种线性数据结构，具有先进先出（FIFO）的特点。与栈不同，队列只允许在队尾插入元素，在队头删除元素。队列通常用于需要按照时间顺序处理事物的场合，例如多任务并发处理或者打印机缓存任务等，它们按照顺序依次加入队列，并按照先进先出的顺序进行处理。

队列的基本操作如下：

InitQueue(&Q)：初始化队列，构造一个空队列Q。

DestroyQueue(&Q)：销毁队列。销毁并释放队列Q所占用的内存空间。

EnQueue(&Q,x)：入队，若队列Q未满，将x加入，使之成为新的队尾。

DeQueue(&Q,&x)：出队，若队列Q非空，删除对头元素，并用x返回。

GetHead(Q,&x)：读队头元素，若队列Q非空，则将队头元素赋值给x。

回顾重点，其主要内容整理成如下内容：  

队列的顺序和链式实现

队列可以用数组或链表等数据结构实现，分别称为顺序队列和链式队列。

顺序队列是基于数组的实现，使用一个数组来存储队列中的元素，使用头尾指针分别指向队列的头部和尾部。新元素插入到队列尾部，旧元素从队列头部删除，每次插入或删除元素后需要更新头尾指针。缺点是当队列元素个数达到数组容量时，需要进行数据搬移，时间复杂度为 O(n)。以下是一个 C++ 语言实现的顺序队列的简单示例代码：

  1. #include <iostream>
  2. using namespace std;
  3.  
  4. const int MAXSIZE = 100; // 队列的最大容量
  5. int queue[MAXSIZE]; // 用数组实现队列
  6. int head = 0, tail = 0; // 头尾指针
  7.  
  8. // 向队列尾部插入元素
  9. void enqueue(int x) {
  10.     if (tail == MAXSIZE) { // 队列已满
  11.         cout << "Error: Queue is full!" << endl;
  12.         return;
  13.     }
  14.     queue[tail++] = x; // 将新元素添加到队列尾部，同时更新尾指针
  15. }
  16.  
  17. // 从队列头部删除元素
  18. void dequeue() {
  19.     if (head == tail) { // 队列为空
  20.         cout << "Error: Queue is empty!" << endl;
  21.         return;
  22.     }
  23.     head++; // 更新头指针，删除队首元素
  24. }
  25.  
  26. // 获取队头元素
  27. int getFront() {
  28.     if (head == tail) { // 队列为空
  29.         cout << "Error: Queue is empty!" << endl;
  30.         return -1;
  31.     }
  32.     return queue[head]; // 返回队首元素
  33. }
  34.  
  35. // 判断队列是否为空
  36. bool isEmpty() {
  37.     return head == tail; // 头尾指针相等时，队列为空
  38. }
  39.  
  40. int main() {
  41.     enqueue(1);
  42.     enqueue(2);
  43.     enqueue(3);
  44.  
  45.     cout << "Front of Queue: " << getFront() << endl;
  46.  
  47.     dequeue();
  48.     dequeue();
  49.  
  50.     cout << "Front of Queue: " << getFront() << endl;
  51.  
  52.     return 0;
  53. }

需要注意的是，在顺序队列中，每次删除元素时并没有真正将元素从数组中移除，而是单纯地将头指针向后移动。因此，当头指针后面有很多无用元素时，需要调整数组内部的元素位置，以节省内存空间。

回顾重点，其主要内容整理成如下内容：  

链式队列是基于链表的实现，使用一个链表来存储队列中的元素，使用头指针指向队首节点，尾指针指向队尾节点。新元素插入到链表尾部，旧元素从链表头部删除，每次插入或删除元素只需操作指针即可，无需进行数据搬移。链式队列相对于顺序队列的优点是没有容量限制，但由于链表需要额外的指针存储，空间开销较大一些。 以下是一个 C++ 语言实现的顺序队列的简单示例代码：

  1. #include <iostream>
  2. using namespace std;
  3.  
  4. struct Node {
  5.     int data;
  6.     Node* next;
  7. };
  8.  
  9. Node* head = NULL; // 头指针指向队列头部
  10. Node* tail = NULL; // 尾指针指向队列尾部
  11.  
  12. // 向队列尾部插入元素
  13. void enqueue(int x) {
  14.     Node* newNode = new Node;
  15.     newNode->data = x;
  16.     newNode->next = NULL;
  17.  
  18.     if (tail == NULL) { // 队列为空
  19.         head = tail = newNode;
  20.         return;
  21.     }
  22.     tail->next = newNode; // 将新节点添加到队列尾部
  23.     tail = newNode; // 更新尾指针
  24. }
  25.  
  26. // 从队列头部删除元素
  27. void dequeue() {
  28.     if (head == NULL) { // 队列为空
  29.         cout << "Error: Queue is empty!" << endl;
  30.         return;
  31.     }
  32.     Node* temp = head;
  33.     head = head->next; // 更新头指针
  34.     if (head == NULL) { // 如果队列中只有一个元素，删除后需要更新尾指针
  35.         tail = NULL;
  36.     }
  37.     delete temp;
  38. }
  39.  
  40. // 获取队头元素
  41. int getFront() {
  42.     if (head == NULL) { // 队列为空
  43.         cout << "Error: Queue is empty!" << endl;
  44.         return -1;
  45.     }
  46.     return head->data;
  47. }
  48.  
  49. // 判断队列是否为空
  50. bool isEmpty() {
  51.     return head == NULL; // 头指针为空时，队列为空
  52. }
  53.  
  54. int main() {
  55.     enqueue(1);
  56.     enqueue(2);
  57.     enqueue(3);
  58.  
  59.     cout << "Front of Queue: " << getFront() << endl;
  60.  
  61.     dequeue();
  62.     dequeue();
  63.  
  64.     cout << "Front of Queue: " << getFront() << endl;
  65.  
  66.     return 0;
  67. }

需要注意的是，在链式队列中，每次删除元素时需要注意特殊情况，比如队列中只有一个元素的情况。还需要注意内存泄漏问题，每次删除元素后需要释放对应节点的内存空间。 

回顾重点，其主要内容整理成如下内容：  

双端队列的介绍：双端队列（deque）是一种可以在队列两端进行插入和删除操作的数据结构。它可以被看作是两个栈拼接而成，因此常常被称为“双端栈”。

回顾重点，其主要内容整理成如下内容：  

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览48445 人正在系统学习中
学习分享/商务合作/技术交流
微信名片
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪