当前位置:   article > 正文

数据结构02 队列及其应用【C++实现】

数据结构02 队列及其应用【C++实现】

目录

队列及其特点

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

创建队列

空队条件

元素入队

 元素出队

 模拟超市收银问题

队列操作

初始化

入队操作

出队操作

取出队首元素

STL模板中队列的基本使用

训练:约瑟夫问题

参考程序


队列及其特点

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

总结队列的特点为:先入先出,即先入队的元素先出队。

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

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

创建队列

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

空队条件

front==rear;

元素入队

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

 元素出队

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

 模拟超市收银问题

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

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

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

队列操作

初始化

  1. const int MAXN=1100;
  2. int que[MAXN];
  3. int head = 0;
  4. int tail = 0;

入队操作

  1. void push(int x){
  2. if(tail>=MAXN) printf("队列溢出");
  3. else{
  4. que[tail] = x;
  5. tail++;
  6. }
  7. }

出队操作

  1. void pop(){
  2. if(head==tail) printf("队列为空");
  3. else head++;
  4. }

取出队首元素

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

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

参考程序

  1. #include<iostream>
  2. #include<queue>
  3. using namespace std;
  4. queue<int> que;
  5. int m,n;
  6. int main(){
  7. cin>>n>>m;
  8. for(int i=1;i<=n;i++) que.push(i); //编号入队
  9. int k=1;
  10. while(!que.empty()){
  11. if(k==m){ //数到了m
  12. cout<<que.front()<<" "; //输出
  13. que.pop(); //出队
  14. k=1; //再次初始化k
  15. }
  16. else{
  17. que.push(que.front());//队首放到队尾
  18. que.pop(); //出队
  19. k++;
  20. }
  21. }
  22. return 0;
  23. }

从C++入门到算法,再到数据结构,查看全部文章请点击此处icon-default.png?t=N7T8http://www.bigbigli.com/ 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Guff_9hys/article/detail/747783
推荐阅读
相关标签
  

闽ICP备14008679号