堆栈是一种线性数据结构，它遵循执行操作的特定顺序。顺序可能是 LIFO（后进先出）或 FILO（先进后出）。
在栈中主要进行以下三个基本操作：
- Push： 在堆栈中添加一个项目。如果堆栈已满，则称其为溢出条件。
- Pop： 从堆栈中移除一个项目。这些项目以它们被推送的相反顺序弹出。如果堆栈为空，则称其为下溢条件。
- Peek 或 Top： 返回堆栈的顶部元素。
- isEmpty： 如果堆栈为空则返回true，否则返回false。
如何实际理解堆栈？
有许多现实生活中的堆栈示例。考虑一下在食堂里盘子叠在一起的简单例子。位于顶部的板是第一个被移除的板，即已放置在最底部位置的板在堆叠中保留的时间最长。所以，可以简单的看出遵循LIFO/FILO的顺序。
堆栈操作的时间复杂度：
push()、pop()、isEmpty() 和 peek() 都需要 O(1) 时间。我们不会在任何这些操作中运行任何循环。
堆栈的应用：
- 符号的平衡
- 中缀到后缀/前缀的转换
- 许多地方的重做-撤消功能，如文本编辑器、WPS、Photoshop。
- Web 浏览器中的前进和后退功能
- 用于许多算法，如河内塔、树遍历、库存跨度问题、直方图问题。
- 回溯是算法设计技术之一。回溯的一些例子是 Knight-Tour 问题、N-Queen 问题、在迷宫中找到自己的方式，以及所有这些问题中的类似游戏的国际象棋或跳棋问题，如果这种方式效率低下，我们会回到以前的问题状态并进入另一条路径。为了从当前状态返回，我们需要为此目的存储先前的状态，我们需要一个堆栈。
- 在诸如拓扑排序和强连通分量之类的图算法中
- 在内存管理中，任何现代计算机都使用堆栈作为运行目的的主要管理。在计算机系统中运行的每个程序都有自己的内存分配
- 字符串反转也是堆栈的另一个应用。在这里，每个字符都被一个一个地插入到堆栈中。所以字符串的第一个字符在栈底，字符串的最后一个元素在栈顶。在堆栈上执行弹出操作后，我们得到一个相反顺序的字符串。
实现：
栈的实现有两种方式：
- 使用数组
- 使用链表
使用数组实现堆栈
c++
复制代码
#include <bits/stdc++.h> using namespace std; #define MAX 1000 class Stack { int top; public: int a[MAX]; Stack() { top = -1; } bool push(int x); int pop(); int peek(); bool isEmpty(); }; bool Stack::push(int x) { if (top >= (MAX - 1)) { cout << "Stack Overflow"; return false; } else { a[++top] = x; cout << x << " 压入堆栈\n"; return true; } } int Stack::pop() { if (top < 0) { cout << "Stack Underflow"; return 0; } else { int x = a[top--]; return x; } } int Stack::peek() { if (top < 0) { cout << "Stack is Empty"; return 0; } else { int x = a[top]; return x; } } bool Stack::isEmpty() { return (top < 0); } int main() { class Stack s; s.push(10); s.push(20); s.push(30); cout << s.pop() << " 从堆栈中弹出\n"; cout<<"堆栈中存在的元素 : "; while(!s.isEmpty()) { cout<<s.peek()<<" "; s.pop(); } return 0; }
输出 ：
10 压入堆栈 20 压入堆栈 30 压入堆栈 30 从堆栈中弹出 顶部元素是： 20 堆栈中存在的元素： 20 10
优点： 易于实施。由于不涉及指针，因此节省了内存。
缺点： 它不是动态的。它不会根据运行时的需要增长和缩小。
使用链表实现堆栈：
#include <bits/stdc++.h> using namespace std; class StackNode { public: int data; StackNode* next; }; StackNode* newNode(int data) { StackNode* stackNode = new StackNode(); stackNode->data = data; stackNode->next = NULL; return stackNode; } int isEmpty(StackNode* root) { return !root; } void push(StackNode** root, int data) { StackNode* stackNode = newNode(data); stackNode->next = *root; *root = stackNode; cout << data << " pushed to stack\n"; } int pop(StackNode** root) { if (isEmpty(*root)) return INT_MIN; StackNode* temp = *root; *root = (*root)->next; int popped = temp->data; free(temp); return popped; } int peek(StackNode* root) { if (isEmpty(root)) return INT_MIN; return root->data; } int main() { StackNode* root = NULL; push(&root, 10); push(&root, 20); push(&root, 30); cout << pop(&root) << " popped from stack\n"; cout << "Top element is " << peek(root) << endl; cout<<"Elements present in stack : "; while(!isEmpty(root)) { cout<<peek(root)<<" "; pop(&root); } return 0; }
