C、C++常用数据结构：栈
栈
- 栈：栈（Stack）是一种后进先出（LIFO, Last In First Out）的数据结构。
- 栈的本质是一种线性表。
- 添加元素，称为入栈（push）；删除元素，称为出栈（pop）。
- 栈可以用顺序存储实现，也可以用链式存储实现，分别成为顺序栈和链栈。但一般使用顺序存储实现，因为栈不允许在栈中间进行插入和删除。
- 栈数据结构有两种初始化方式，一种是动态初始化，另一种是静态初始化。
动态初始化和静态初始化对比
1. 内存分配方式
- 动态初始化：栈的大小在运行时确定，通常使用动态内存分配（如
new或malloc）来实现。栈的内存从堆中分配，而不是栈帧或全局数据段。（重点是从堆中分配内存）。可以根据实际需要调整栈的大小。例如int* stack = new int[100]; - 静态初始化：栈的大小在编译时确定，通常使用数组来实现，并且在栈帧或全局数据段中分配内存。一旦栈的大小确定，就不能再改变。例如：
int stack[100];
2. 性能对比
- 动态初始化：由于涉及动态内存分配（如
new、delete），分配和释放速度较慢，并且有内存碎片的可能。 - 静态初始化：因为内存是在栈上或全局段中分配的，分配和释放的速度非常快。
代码示例
动态初始化：
#include <iostream>using namespace std;/*** 动态内存分配栈*/
class DynamicStack
{
private:int *stack;int top;int maxsize;public:DynamicStack(int size) : top(-1), maxsize(size){stack = new int[size];}bool isEmpty(){return top == -1;}bool isFull(){return top == maxsize - 1;}void push(int val){if (isFull()){cout << "动态分配的栈已满（达到最大值）" << endl;return;}stack[++top] = val;cout << stack[top] << "入栈" << endl;}void pop(){if (isEmpty()){cout << "栈为空，不能pop" << endl;return;}cout << stack[top] << "出栈" << endl;top--;}int getTop(){if (isEmpty()){cout << "栈为空，不能getTop" << endl;return -1;}return stack[top];}
};int main(int argc, char const *argv[])
{DynamicStack dystack(5);dystack.push(11);dystack.push(25);dystack.push(36);cout << "栈顶：" << dystack.getTop() << endl;dystack.pop();dystack.pop();dystack.pop();return 0;
}
静态初始化：
#include <iostream>using namespace std;#define MAXSIZE 100/*** 静态内存分配栈*/
class StaticStack
{
private:int stack[MAXSIZE];int top;public:StaticStack() : top(-1) {}bool isEmpty() { return top == -1; }bool isFull() { return top == MAXSIZE - 1; }void push(int value){if (isFull()){cout << "栈已满" << endl;return;}stack[++top] = value;cout << stack[top] << "入栈" << endl;}void pop(){if (isEmpty()){cout << "栈为空" << endl;return;}cout << stack[top] << "出栈" << endl;top--;}int getTop(){if (isEmpty()){cout << "栈为空" << endl;return 0;}return stack[top];}
};int main(int argc, char const *argv[])
{/* code */StaticStack static_stack;static_stack.push(11);static_stack.push(25);static_stack.push(36);cout << "栈顶：" << static_stack.getTop() << endl;static_stack.pop();static_stack.pop();static_stack.pop();return 0;
}
C++的标准库<stack>
以上通过编写栈的相关代码，只是为了更直观和简单地理解栈数据结构，实际上，在 C++ 中，可以使用标准库 <stack> 提供的 stack 模板来创建和操作栈。
stack是一个模板类，可以用来存储任何类型的数据（如int、double、自定义对象等）。例如：stack<int> s;stack的一些基本操作：push: 将元素压入栈顶。pop: 移除栈顶元素。top: 获取栈顶元素的值（但不移除）。empty: 检查栈是否为空。size: 获取栈中元素的数量。