知识概览

• 在数据结构中，栈和队列都属于线性表。栈是先进后出（FILO）的，队列是先进先出（FIFO）的。

代码模板

#include <iostream>using namespace std;const int N = 100010;// ********************** 栈
int stk[N], tt;// 插入
stk[++tt] = x;// 弹出
tt--;// 判断栈是否为空
if (tt > 0) not empty
else empty// 栈顶
stk[tt];// ********************** 队列// 在队尾插入元素，在对头弹出元素
int q[N], hh, tt = -1;// 插入
q[++tt] = x;// 弹出
hh++;// 判断队列是否为空
if (hh <= tt) not empty
else empty// 取出队头元素
q[hh];

栈

题目链接

https://www.acwing.com/problem/content/830/

代码（数组模拟）

#include <iostream>using namespace std;const int N = 100010;int m;
int stk[N], tt;int main()
{cin >> m;while (m--){string op;int x;cin >> op;if (op == "push"){cin >> x;stk[++tt] = x;}else if (op == "pop") tt--;else if (op == "empty") cout << (tt ? "NO" : "YES") << endl;else cout << stk[tt] << endl;}return 0;
}

代码（STL）

#include <iostream>
#include <stack>using namespace std;int m;
stack<int> stk;int main()
{cin >> m;while (m--){int x;string op;cin >> op;if (op == "push"){cin >> x;stk.push(x);}else if (op == "pop") stk.pop();else if (op == "empty") cout << (stk.empty() ? "YES" : "NO") << endl;else cout << stk.top() << endl;}return 0;
}

队列

题目链接

https://www.acwing.com/problem/content/831/

代码（数组模拟）

#include <iostream>using namespace std;const int N = 100010;int m;
int q[N], hh, tt = -1;int main()
{cin >> m;while (m--){string op;int x;cin >> op;if (op == "push"){cin >> x;q[++tt] = x;}else if (op == "pop") hh++;else if (op == "empty") cout << (hh <= tt ? "NO" : "YES") << endl;else cout << q[hh] << endl;}return 0;
}

代码（STL）

#include <iostream>
#include <queue>using namespace std;int m;
queue<int> q;int main()
{cin >> m;while (m--){int x;string op;cin >> op;if (op == "push"){cin >> x;q.push(x);}else if (op == "pop") q.pop();else if (op == "empty") cout << (!q.empty() ? "NO" : "YES") << endl;else cout << q.front() << endl;}return 0;
}