Part 0：本文声明

本文只介绍基本写队列方法。
文章所有代码均为原创，转载请注明来源。
循环队列请看这里。

Part 1：啥是队列

一天，一群小可爱们在排队买奶茶。

店主认识第一个小可爱，给他打了骨折（大雾），小可爱买到了奶茶，他快乐的（真的？）离开了。

其他人往前挪一位：

然后，目前排在第一位的小可爱买了奶茶，一蹦一跳的离开了：

接下来，其他人往前挪一位：

这样进行下去，最后，只剩下了一位小可爱，他买了奶茶，兴冲冲的离开了：

没有人啦！奶茶店卖完了奶茶，兴冲冲的关门了。

这就是队列，先进先出的数据结构。

Part 2：手写队列

如果你已经搞清楚了队列是酱紫的，我们来尝试手写一下队列。
我们简单看一下刚才排队的过程，我们可以发现，一个队列需要实现：

增加（有人来买奶茶）
弹出第一个（买完奶茶走掉）
求队列中元素个数（有多少个人）
判断队列是否为空（到底有冇得人）
获取队首元素（看看第一个小可爱到底是谁啊，咱给他打个骨折）

那么，我们尝试用数组和结构体来实现一下：

struct Queue{
    int que[1000];     //最大容纳1000个元素
    int head = 0;      //队列的第一个元素
    int tail = 0;      //队列的最后一个元素
    void push(int x){}  //增加一个
    void pop(){}      //弹出第一个
    bool empty(){}     //是否为空
    int num(){}        //返回有多少个元素
    int getHead(){}    //获取第一个元素
}

然后，我们来尝试写一下第一个函数push(int x)：

1
2
3

void push(int x){
    que[tail++]=x;
}

tail++是个神奇的语句，不仅可以增加一个元素，并且还可以tail指向下一个元素，增加队列的长度。
第二个：push()，我们直接让head++：

1
2
3

void pop(){
    head++;
}

第三个：empty()，直接tail-head，因为tail一定大于等于head，想想为什么：

1
2
3

bool empty(){
    return tail-head;//tail-head为0的时候队列为空，返回0，也就是false
}

第四个num()其实和empty()很类似：

1
2
3

int num(){
    return tail-head;
}

第五个也极其简单：

1
2
3

int getHead(){
    return que[head];
}

完整代码：

struct Queue{
    int que[1000];     //最大容纳1000个元素
    int head = 0;      //队列的第一个元素
    int tail = 0;      //队列的最后一个元素
    void push(int x){ que[tail++]=x; }  //增加一个
    void pop(){ head++; }      //弹出第一个
    bool empty(){ return tail-head; }     //是否为空
    int num(){ return tail-head; }        //返回有多少个元素
    int getHead(){ return que[head]; }    //获取第一个元素
}

我们拿去试下：

#include <iostream>
using namespace std;
struct Queue{
    int que[1000];     //最大容纳1000个元素
    int head = 0;      //队列的第一个元素
    int tail = 0;      //队列的最后一个元素
    void push(int x){ que[tail++]=x; }  //增加一个
    void pop(){ head++; }      //弹出第一个
    bool empty(){ return tail-head; }     //是否为空
    int num(){ return tail-head; }        //返回有多少个元素
    int getHead(){ return que[head]; }    //获取第一个元素
};
int main(){
    struct Queue queue;
    //买奶茶，6个人
    for(int i = 0;i < 6;i ++){
        queue.push(i);
    }
    //功能测试
    cout << queue.getHead() << endl;
    cout << queue.num() << endl;
    //然后弹出
    for(int i = 0;i < 6; i++){
        queue.pop();//弹出一个
        cout << queue.num() << ' ';//看看有多少元素
        cout << queue.getHead() << endl;//获取头元素
    }
    cout << queue.empty() << endl;//看看是否为空
}

程序输出：

Part 3：STL里边的queue

别人也帮我们写了一个queue，我们来看看怎么用。

#include<queue>
queue<int> q;//队列q里边元素的的类型是int
q.push(144514);
q.size();   //返回1
q.front();  //返回第一个元素144514
q.back();   //哈，比我们多一个结尾元素
q.empty();  //跟我们自己手写的empty一样
q.pop();    //弹出

尝试使用STL的queue写出买奶茶程序吧~

啥是佩奇？哦不，啥是队列

Part 0：本文声明

Part 1：啥是队列

Part 2：手写队列

Part 3：STL里边的queue