1. 栈

1.1 栈的概念和相关术语

栈是一种特殊的线性表，它只允许在表的一端进行插入和删除操作。这使栈具有 “后进先出”（Last In First Out，LIFO）的特性

栈顶：栈中允许进行插入和删除操作的一端

栈底：栈的另一端，是最先放入元素的位置，在栈的操作过程中，栈底通常是固定的。

入栈：也叫压栈、进栈，是将元素添加到栈顶的操作。

出栈：也叫弹栈，是从栈顶弹出一个元素。

栈空：当栈中没有任何元素时，称栈为空栈。

因为栈的性质，栈是一个相对简单的数据结构

1.2 栈的实现

//可以使用数组模拟实现栈
//创建栈，id可以标记栈顶的位置
const int N = 1e6 + 10;
int id;
int stk[N];//进栈，有效元素从1开始，可以有效避免一些问题,时间复杂度O(1)
void push(int x)
{stk[++id] = x;
}//出栈,时间复杂度O(1)
void pop()
{id--;
}//查询栈顶元素，时间复杂度O(1)
//因为栈的特殊性，不支持遍历整个栈
int top()
{return stk[id];
}//判断栈是否为空,时间复杂度O(1)
bool empty()
{return id==0;
}//有效元素个数,时间复杂度O(1)
int size()
{return id;
}

2. stack

#include<stack>
void test()
{//创建stackstack<int> st;//向栈顶插入元素st.push(1);st.push(3);//打印有效元素个数cout << st.size() << endl;//打印栈顶元素cout << st.top() << endl;//删除元素st.pop();st.pop();cout << st.size() << endl;//判断栈是否为空if (st.empty()){cout << "空" << endl;}
}