数据结构与算法（c++）|【18. 模拟栈和队列】算法|开发语言|c++

模拟栈特点：栈是先进后出。

#include usign namespace std; const int N = 100010; int stk[N], tt; //tt表示栈顶,初始值设为0//插入 stk[++ tt] = x; //弹出 tt --; //判断栈是否为空 if(tt > 0) not empty else empty//栈顶 stk[tt];

题目
实现一个栈，栈初始为空，支持四种操作：

push x – 向栈顶插入一个数 x；

pop – 从栈顶弹出一个数；

empty – 判断栈是否为空；

query – 查询栈顶元素。

现在要对栈进行 M 个操作，其中的每个操作 3 和操作 4 都要输出相应的结果。
输入格式第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。
输出格式对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。
其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示栈顶元素的值。
数据范围 1 ≤ M ≤ 100000
1 ≤ x ≤ 109
所有操作保证合法。
输入样例：
10 push 5 query push 6 pop query pop empty push 4 query empty

输出样例：
5 5 YES 4 NO

代码

#include #include using namespace std; const int N = 100010; int stk[N], tt; // tt 表示栈顶,初始为0//插入 void push(int x) { stk[ ++ tt] = x; }//弹出 void pop() { tt --; }//判断栈是否为空void empty() { if (tt > 0)cout << "NO" << endl; else cout << "YES" << endl; }//栈顶 void query() { stk[tt]; cout << stk[tt] << endl; }int main() { int m; cin >> m; while (m --) { int x; string op; cin >> op; if (op == "push") { cin >>x; push(x); } else if (op == "query") { query(); } else if (op == "pop") { pop(); } else { empty(); } }}

模拟队列特点：先进先出。

//在队尾插入元素，在对头取出元素 int q[N], hh, tt = -1; //tt代表队头，hh代表队尾对头初始值设置为-1，也可以向栈一样设置为0//插入 q[ ++ tt] = x; //弹出 hh ++; //判断队列是否为空 if (hh <= tt) not empty else empty//取出队头元素 q[hh] //取出队尾元素 q[tt]

文章图片

题目
实现一个队列，队列初始为空，支持四种操作：

push x – 向队尾插入一个数 x；

pop – 从队头弹出一个数；

empty – 判断队列是否为空；

query – 查询队头元素。

现在要对队列进行 M 个操作，其中的每个操作 3 和操作 4 都要输出相应的结果。
输入格式第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。
输出格式对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。
其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示队头元素的值。
数据范围 【数据结构与算法（c++）|【18. 模拟栈和队列】】1 ≤ M ≤ 100000
1 ≤ x ≤ 109
所有操作保证合法。
输入样例：
10 push 6 empty query pop empty push 3 push 4 pop query push 6

输出样例：
NO 6 YES 4

代码

#include #include using namespace std; const int N = 100010; int q[N], hh, tt = -1; //插入 void push(int x) { q[ ++ tt]=x; }//弹出 void pop() { hh ++; }//判断是否为空 void empty() { if (hh <= tt)cout << "NO" << endl; else cout << "YES" << endl; }//取出队头元素 void query() { q[hh]; cout << q[hh] << endl; }int main() {int m; cin >> m; while (m --) { string op; cin >> op; int x; if (op == "push") { cin >> x; push(x); } else if (op == "pop") { pop(); } else if (op == "empty") { empty(); } else { query(); } } return 0; }