栈（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
}