栈（Stack）的基本原理及算法实现
一、栈的基本概念
栈（Stack）是一种后进先出（LIFO，Last In First Out）的线性表，其特点是只允许在一端进行插入操作，而在另一端进行删除操作。栈的基本操作有：入栈（push）、出栈（pop）、查看栈顶元素（top）等。
二、栈的实现原理
-
数组实现：使用一组连续的内存空间来存储栈中的元素，栈顶指针指向栈顶元素的下一个位置。入栈时，将新元素存储在栈顶指针的下一个位置；出栈时，将栈顶元素移动到栈顶指针的位置，并释放该空间。
-
链表实现：使用一组节点来存储栈中的元素，每个节点包含一个数据域和一个指向下一个节点的指针。入栈时，将新元素添加到链表尾部；出栈时，将栈顶元素从链表中移除，并更新栈顶指针。
-
递归实现：利用递归的方式实现栈的操作，如
push和pop。这种实现方式较为简洁，但效率较低。
下面分别介绍数组实现和链表实现的栈算法流程。
1. 数组实现
算法步骤：
- 初始化一个空栈。
push操作：将新元素存储在栈顶指针的下一个位置，然后更新栈顶指针。pop操作：将栈顶元素移动到栈顶指针的位置，并释放该空间，然后更新栈顶指针。top操作：返回栈顶元素的值。
C++代码实现：
#include<bits/stdc++.h> // 引入常用的头文件
#define reg register // 定义寄存器宏
#define ull unsigned long long // 定义无符号长整型别名
using namespace std; // 使用标准命名空间
// 读取输入的函数，返回值为整数类型
inline int read(){
int x=0,f=1; // 初始化变量x和f
char ch=getchar(); // 读取一个字符
while(ch<'0'||ch>'9'){ // 如果字符不是数字，则继续读取
if(ch=='-') f=-1; // 如果字符是负号，则将f设为-1
ch=getchar(); // 读取下一个字符
}
while(ch>='0'&&ch<='9'){ // 如果字符是数字，则将其转换为整数并累加到x中
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar(); // 读取下一个字符
}
return x*f; // 返回结果，如果f为-1，则返回负数
}
// 输出结果的函数，参数为整数类型
void write(int x){
if(x<0){ // 如果x小于0，则输出负号
putchar('-');
x=-x; // 取绝对值
}
if(x>9) write(x/10); // 如果x大于9，则递归调用write函数，将x除以10的结果作为参数传入
putchar(x%10+'0'); // 输出x除以10的余数，并将其转换为字符类型
return ;
}
int t; // 定义整数变量t，用于存储测试用例的数量
vector<ull > a; // 定义一个无符号长整型向量a，用于存储数据
int main(){
t=read(); // 读取测试用例的数量
while(t--){ // 循环处理每个测试用例
int n=read(); // 读取操作次数n
a.clear(); // 清空向量a
while(n--){ // 循环执行n次操作
string s; // 定义一个字符串变量s，用于存储操作指令
cin>>s; // 读取操作指令
if(s=="push"){ // 如果指令是"push"，则执行以下操作
ull x; // 定义一个无符号长整型变量x
cin>>x; // 读取要压入向量a的元素
a.push_back(x); // 将元素x压入向量a的末尾
continue;
}
if(s=="pop"){ // 如果指令是"pop"，则执行以下操作
if(a.empty()){ // 如果向量a为空，则输出"Empty"并跳过本次循环
printf("Empty\n");
continue;
}
a.pop_back(); // 否则，弹出向量a的最后一个元素
continue;
}
if(s=="query"){ // 如果指令是"query"，则执行以下操作
if(a.empty()){ // 如果向量a为空，则输出"Anguei!"并跳过本次循环
printf("Anguei!\n");
continue;
}
cout<<a.back()<<endl; // 否则，输出向量a的最后一个元素
continue;
}
if(s=="size"){ // 如果指令是"size"，则执行以下操作
cout<<a.size()<<endl; // 输出向量a的大小
}
}
}
return 0; // 程序正常结束，返回0
}
2. 链表实现
算法步骤：
- 初始化一个空链表。
push操作：将新元素添加到链表尾部。pop操作：遍历链表，找到第一个等于栈顶元素的节点并将其移除。同时更新链表头和栈顶指针。如果链表为空，则表示栈为空。