文章目录
• 前言
• 一、关于队列
• 二、队列的操作
• 1.数组模拟队列必备属性
• 2.向队尾插入一个元素x
• 3.从对头弹出一个数
• 4.查询对头元素
• 5.判断队列是否为空
• 三、例题， 代码
• 1.AcWing 828. 模拟栈
• 2.AC代码
• 四、时间复杂度
前言
复习acwing算法基础课的内容，本篇为讲解基础算法：用数组模拟队列，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上
一、关于队列
在C++中，STL已经帮助我们实现队列，详细见：STL—queue，本篇博客中，讲解如何用数组去模拟栈，实现队列的一些功能.
二、队列的操作
1.数组模拟队列必备属性
int q[N]; //数组q中存储的就是队列中的元素 int hh; //hh表示的是对头，初始值为0 int tt = -1; //tt表示的是队尾，初始值为-1，tt初始小于hh，证明队列里无元素
2.向队尾插入一个元素x
q[ ++ tt] = x; //因为向队尾插入了一个元素，所以对头hh不变，对尾tt向后移动一位，并把x赋值到q数组中
3.从对头弹出一个数
hh ++; //直接把hh向后移动一位即可
4.查询对头元素
printf("%d", q[hh]); //q[hh] 代表的就是对头元素
5.判断队列是否为空
if (tt < hh) printf("队列为空"); else printf("队列不空");
三、例题， 代码
1.AcWing 828. 模拟栈
本题链接：AcWing 828. 模拟栈
本博客给出本题截图：
2.AC代码
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int N = 100010; int q[N], tt = -1, hh; int main() { int n; scanf("%d", &n); while (n -- ) { string op; cin >> op; if (op == "push") { int x; scanf("%d", &x); q[ ++ tt ] = x; } else if (op == "pop") hh ++; else if (op == "empty") { if (tt < hh) printf("YES\n"); else printf("NO\n"); } else printf("%d\n", q[hh]); } return 0; }
四、时间复杂度
关于数组模拟栈的各操作时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
