python/TangDou/AcWing/Queue/829.md

##[$AcWing$ $829$. 模拟队列](https://www.acwing.com/problem/content/831/)

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

`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≤10^9$
,所有操作保证合法。

**输入样例：**
```cpp {.line-numbers}
10
push 6
empty
query
pop
empty
push 3
push 4
pop
query
push 6
```
**输出样例：**
```cpp {.line-numbers}
NO
6
YES
4
```

### 二、理解和感悟

用数组模拟队列，比用数组模拟栈要麻烦一点，因为栈是同一边进同一边出，而队列是尾巴进，脑袋出。


**举个栗子**
1、先加入一个元素`a`，那么需要`++tt`,就是`tt==0`,然后要求`a`出队，就是`hh++`,这时，`hh=1`,现在队列为空，`hh>tt`。

2、因为数组的特点，在数组后面增加元素很方便，在头部增加元素很麻烦，所以设计了`hh`在左，`tt`在右的策略，出队`hh++`,入队`++tt`

3、使用数组模拟队列的另一个好处，就是可以遍历队列中的每一个数字，这和用数组模拟栈是一样的，这也是$STL$比不了的。


### 三、普通队列解法
```cpp {.line-numbers}
#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;
int q[N], hh, tt = -1;
int main() {
    int n;
    cin >> n;
    while (n--) {
        string op;
        cin >> op;
        if (op == "push") cin >> q[++tt];
        else if (op == "empty")
            hh > tt ? cout << "YES" << endl : cout << "NO" << endl;
        else if (op == "query")
            cout << q[hh] << endl;
        else hh++;
    }
    return 0;
}
```

### 四、循环队列解法
```cpp {.line-numbers}
#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;
int q[N], hh, tt;
int main() {
    int n;
    cin >> n;
    while (n--) {
        string op;
        cin >> op;
        if (op == "push") {
            cin >> q[tt++];
            if (tt == N) tt = 0; // 加冒了，就回到0
        } else if (op == "empty")
            hh == tt ? cout << "YES" << endl : cout << "NO" << endl;
        else if (op == "query")
            printf("%d\n", q[hh]);
        else {
            hh++;
            if (hh == N) hh = 0; // 加冒了，就回到0
        }
    }
    return 0;
}
```
### 五、总结

- 普通队列的时候，插入时是`q[++tt]`
- 循环队列的时候，插入时是`q[tt++]`
 

**个人理解**：如果真的队列$N$的数量不够，需要重复利用的话，那么进去队列的次数可不小。本来我们用数组模拟队列，一就是因为速度快，二就是因为可以利用数组找出入队列的顺序，也就是 **拓扑序**，要是真用了循环队列的话，那么被覆盖掉时，拓扑序也就没有机会再找出来了，还不如直接用$STL$的$queue$,一家之言，待后续的经验验证。