数据结构02 队列及其应用

队列及其特点

队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，前端一般叫做队头，后端叫队尾。队列就像学校做操站队一样，来的人一个一个往后站，走的时候从前往后一个一个走。

总结队列的特点为：先入先出，即先入队的元素先出队。

利用数组模拟队列的基本操作

对于队列的使用，我们可以直接利用数组来模拟队列的基本操作，具体实现如下：

创建队列

int que[105];     //定义一个能存放105个数字的数组来模拟队列
int front=0,rear=0;    //front与rear分别表示队头和队尾元素的位置。

空队条件

front==rear；

元素入队

que[rear++]=x；    //元素x入队

 元素出队

x=que[front++]；  //队首元素出队，并将元素值赋值给x

 模拟超市收银问题

假设有一批顾客来到超市，在结账时，必须排队付款。先到达收银台的顾客先结账。

我们模拟收银过程，使用队列来实现，一般队列会提供以下几个功能：

push(x)：将x压入队列，即顾客来排队，应该站在队尾。
pop()：弹出队首元素，即排在最前面的人结完账后，离开队列。
front()：查询队首元素，即知道目前是谁结账。

队列操作

初始化

const int MAXN=1100;
int que[MAXN];
int head = 0;
int tail = 0;

入队操作

void push(int x){
    if(tail>=MAXN) printf("队列溢出");
    else{
        que[tail] = x;
        tail++;
    }
}

出队操作

void pop(){
    if(head==tail)  printf("队列为空");
    else head++;
}

取出队首元素

int front(){
    if(head==tail) printf("队列为空");
    else return que[head];
}

STL模板中队列的基本使用

对于队列的使用，我们也可以直接利用STL模板来实现，STL模板库中队列的基本操作如下：

头文件：#include<queue>

创建一个存放int类型数据的空队列s：queue<int> s;

s.empty():  判断队列是否为空，为空返回true，否则返回false；

s.size():  返回队列中元素的个数；

s.front():  获取队首元素的值；

s.back():  获取队尾元素的值；

s.push(k):   向队尾插入新的元素k；

s.pop():    删除队列s的队首元素。

训练：约瑟夫问题

n个人(n<=100)围成一圈,从第一个人开始报数,数到m的人出列,再由下一个人重新从1开始报数,数到m的人再出圈,……依次类推,直到所有的人都出圈,请输出依次出圈人的编号。

【输入描述】n和m

【输出描述】出列的顺序

【输入样例】4 17

【输出样例】1 3 4 2

参考程序

#include<iostream>
#include<queue>
using namespace std;
queue<int> que;
int m,n;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) que.push(i); //编号入队  
    int k=1;
    while(!que.empty()){
        if(k==m){ //数到了m
            cout<<que.front()<<" "; //输出
            que.pop(); //出队
            k=1;  //再次初始化k
        }
        else{
            que.push(que.front());//队首放到队尾            
            que.pop(); //出队
            k++;
        }
    }
    return 0;
}