赞
踩
目录
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。
队尾(rear):只能从队尾添加元素,一般焦作EnQueue,入队
队头(front):只能从队头移除元素,一般焦作DeQueue,出队
先进先出的原则、First In Fist Out,FIFO(跟栈是反的,栈是后进先出)
在生活中队列案例也是随处可见。例如火车站排队买票,银行排队办理业务。
队列:只允许在一端进行插入数据操作,在另一端进行删除操作的特殊线性表,队列最重要的特性是先进先出(First In First Out)
C++队列queue模板类的定义在<queue>头文件中,queue 模板类需要两个模板参数,一个是元素类型,一个容器类型,元素类型是必要的,容器类型是可选的,默认为deque 类型。C++队列Queue是一种容器适配器,它给予程序员一种先进先出(FIFO)的数据结构。
队列只需要从对尾插入数据(入队,push_back),对头取数据(出队,pop_front);
队列只能访问对头和队尾数据,其他数据需要出队才能访问,所以不存在遍历队列;
返回队列头数据:front()
返回队列尾数据:back()
队列的操作有:入队: 通常命名为push(),出队: 通常命名为pop(),获取队首元素:front(),获取队尾元素:back(),判断队空:empty(),返回队列个数:size()
- q.push() 入队:在队尾压入新元素
- q.pop() 出队:删除队列首元素但不返回其值
- q.front() 返回队首元素的值,但不删除该元素
- q.back() 返回队列尾元素的值,但不删除该元素
- q.empty() 如果队列为空返回true,否则返回false
- q.size() 返回队列中元素的个数
- #include<iostream>
- #include<queue>
- using namespace std;
- int main()
- {
- queue<int> q; //定义一个数据类型为int的queue
- q.push(1); //向队列中加入元素1
- q.push(2); //向队列中加入元素2
- q.push(3); //向队列中加入元素3
- q.push(4); //向队列中加入元素4
- cout<<"将元素1、2、3、4一一加入队列中后,队列中现在的元素为:1、2、3、4"<<endl;
- cout<<"队列中的元素个数为:"<<q.size()<<endl;
- //判断队列是否为空
- if(q.empty())
- {
- cout<<"队列为空"<<endl;
- }
- else
- {
- cout<<"队列不为空"<<endl;
- }
- cout<<"队列的队首元素为:"<<q.front()<<endl;
- //队列中的队首元素出队
- q.pop();
- cout<<"将队列队首元素出队后,现在队列中的元素为2、3、4"<<endl;
- }
运行结果:
- 将元素1、2、3、4一一加入队列中后,队列中现在的元素为:1、2、3、4
- 队列中的元素个数为:4
- 队列不为空
- 队列的队首元素为:1
- 将队列队首元素出队后,现在队列中的元素为2、3、4
列中的数据和堆栈一样是不允许随机访问的,即不能通过下标访问,且队列内的元素也是无法遍历的。
我们可以通过while循环的方法将queue中的元素读取一遍,但是这种方法非常局限,因为我们每读取一个元素就需要将这个元素出队,因此该方法只能读取一遍queue中的元素。
- #include<iostream>
- #include<queue>
- using namespace std;
- int main()
- {
- queue<int> q; //定义一个数据类型为int的queue
- q.push(1); //向队列中加入元素1
- q.push(2); //向队列中加入元素2
- q.push(3); //向队列中加入元素3
- q.push(4); //向队列中加入元素4
- while(!q.empty())
- {
- cout<<q.front()<<" ";
- q.pop();
- }
- }
插松枝:
人造松枝加工场的工人需要将各种尺寸的塑料松针插到松枝干上,做成大大小小的松枝。他们的工作流程(并不)是这样的:
(1)小盒子已经满了,但推送器上取到的松针仍然不满足要求。此时将手中的松枝放到成品篮里,推送器上取到的松针压回推送器,开始下一根松枝的制作。
(2)小盒子中最上面的松针不满足要求,但推送器上已经没有松针了。此时将手中的松枝放到成品篮里,开始下一根松枝的制作。
(3)手中的松枝干上已经插满了松针,将之放到成品篮里,开始下一根松枝的制作。
现在给定推送器上顺序传过来的 N 片松针的大小,以及小盒子和松枝的容量,请你编写程序自动列出每根成品松枝的信息。
输入在第一行中给出 3 个正整数:N(≤103),为推送器上松针片的数量;M(≤20)为小盒子能存放的松针片的最大数量;K(≤5)为一根松枝干上能插的松针片的最大数量。
随后一行给出 N 个不超过 100 的正整数,为推送器上顺序推出的松针片的大小。
每支松枝成品的信息占一行,顺序给出自底向上每片松针的大小。数字间以 1 个空格分隔,行首尾不得有多余空格。
- 8 3 4
- 20 25 15 18 20 18 8 5
-
- 20 15
- 20 18 18 8
- 25 5
- #include<bits/stdc++.h>
- using namespace std;
- stack<int>box;
- queue<int>p,t;
- int main()
- {
- int n,m,k;
- cin>>n>>m>>k;
- for(int i=1;i<=n;i++)
- {
- int a;
- cin>>a;
- p.push(a);
- }
- while(p.size()||box.size())
- {
- t.push(101);
- while(t.size()<=k)
- {
- if(box.size()&&box.top()<=t.back())
- {
- t.push(box.top());
- box.pop();
- }
- else if(p.size()&&p.front()<=t.back())
- {
- t.push(p.front());
- p.pop();
- }
- else if(p.size()&&box.size()<m)
- {
- box.push(p.front());
- p.pop();
- }
- else
- break;
- }
- t.pop();
- cout<<t.front();
- t.pop();
- while(t.size())
- {
- cout<<" "<<t.front();
- t.pop();
-
- }
- cout<<endl;
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。