数组模拟实现 队列

一、队列简介

队列 ( queue ) 是一种 操作受限 的 线性表。

1. 操作受限：只允许在表的 前端（front）进行删除操作，而在表的 后端（rear）进行插入操作。
因此队列具有 先进先出 ( FIFO ) 的特点。

2. 队头：进行删除操作的端称为队头；
3. 队尾：进行插入操作的端称为队尾；

4. 入队：向队列中 插入 一个队列元素
5. 出队：从队列中 删除 一个队列元素

6. 空队列：队列中没有元素。

二、 用数组模拟实现队列

1. 队列的定义

int q[N]; // 用于存储队列元素 
int hh; // 表示队头的下标 ( 若队列中有元素 )
int tt = -1; // 表示队尾的下标 ( 若队列中有元素 )

说明：初始状态下，队列中没有元素，为空队列

{:height=”40%” width=”40%”}

2. 入队 ( push )

q[ ++ tt ] = x; // 插入队列元素 x

tt 与 hh 的含义
在本模板中，若队列中有元素，
则可以将 hh 看作 队头的下标，将 tt 看作 队尾的下标 。
在 空队列 中，则不行（ 如初始状态下 ）。（后续有队列的判空操作）

在最初的空队列中，插入第一个元素，tt ++ → 0 ，此时 tt == hh
因为队列中含有一个元素，该元素既是队头，也是队尾，因此 tt == hh

随着元素的入队，hh 保持队头下标，而 tt 则随着队尾坐标而递增。
因此说 hh 为 队头的下标， tt 为 队尾的下标 。

{:height=”60%” width=”60%”}

3. 出队 ( pop )

hh ++; // 将 队头 移出队列

说明：
只要让队头指针直接向后移动，则原队头元素便被排除，
不能再被队列的中的下标所访问。

虽然数值仍保留在数组中，但相当于该元素被删除。

{:height=”60%” width=”60%”}

4. 判断队列是否为空

if( hh <= tt ) not empty
else empty

有前述可得：当队列不为空时， hh 为 队头的下标， tt 为 队尾的下标 。

1. 若 hh == tt ，队列中只有 1 个元素；
2. 若 hh < tt ，队列中有 tt - hh + 1 个元素；
3. 若 hh > tt ，队列中没有元素，队列为空。

5. 取出队头

q[hh]; // 当队列不为空时，hh 为队头的下标

补充：事实上，队尾元素为 q[tt]，
但由于队列为 FIFO 的线性表，因此知道队尾元素，意义不大。

三、应用场景

实现一个队列，并支持队列的基本操作。

题源： 829. 模拟队列 - AcWing题库

四、函数模板

#include <iostream>

using namespace std;

const int N = 100010;

int q[N]; // 用于存储队列元素 
int hh; // 表示队头的下标 ( 若队列中有元素 ) 
int tt = -1; // 表示队尾的下标 ( 若队列中有元素 ) 

int main()
{
    int m;
    cin >> m;

    while( m-- )
    {
        int x;
        string op;

        cin >> op;

        if( op == "push" ) // 入队
        {
            cin >> x;
            q[ ++ tt ] = x; // 插入队列元素 x 
        }
        else if( op == "pop" ) // 出队 
        {
            hh ++ ; // 将 队头 移出队列
        }
        else if( op == "empty" ) // 判断队列是否为空 
        {
            if( hh <= tt ) cout << "NO" << endl; 
            else cout << "YES" << endl;
            // if( hh <= tt ) not empty
            // else empty
        }
        else if( op == "query" ) // 查询队头元素 
        {
            cout << q[hh] << endl; // 当队列不为空时，hh 为队头的下标

            // 事实上，队尾元素为 q[tt]
            // 但由于队列为 FIFO 的线性表，因此知道队尾元素，意义不大
        }
    }
    return 0;
} 

五、参考资料

1. y 总的课~~
2. 队列（常用数据结构之一）_百度百科 (baidu.com)

六、( 无注释版 ) 函数模板

#include <iostream>
using namespace std;

const int N = 100010;

int q[N], hh, tt = -1;

int main()
{
    int m;
    cin >> m;

    while( m-- )
    {
        int x;
        string op;
        cin >> op;

        if( op == "push" )
        {
            cin >> x;
            q[ ++ tt ] = x;
        }
        else if( op == "pop" ) hh ++ ;
        else if( op == "empty" )
            if( hh <= tt ) cout << "NO" << endl; 
            else cout << "YES" << endl;
        else if( op == "query" ) cout << q[hh] << endl;
    }
    return 0;
} 

（接受批评指正，欢迎交流补充~~ XD）