当前位置：首页 > 编程日记 > 正文

【C++】STL队列和栈的使用

编程日记 2024-08-21 03:40:00

C++的STL标准模板库提供了队列和栈的基本操作。下面通过两个demo分别介绍STL队列和STL栈的使用。

Demo1：STL队列

【题目】卡片游戏（题目来自刘汝佳《算法竞赛入门》）

桌上又一叠牌，从第一张牌（即位于顶面的牌）开始从上往下依次编号为1~n。当至少还剩两张牌时进行以下操作：把第一张牌扔掉，然后把新的第一张放到整叠牌的最后。输入n，输出每次扔掉的牌，以及最后剩下的牌。

样例输入：7

样例输出：1 3 5 7 4 2 6

【分析】这些牌就是一个先进先出（FIFO）的队列，每次对排头的两张进行操作，第一张出队列，第二张放到队尾。

【代码】

#include<cstdio>
#include<queue>
using namespace std;int main()
{queue<int> q;int n;scanf("%d",&n);for(int i = 0;i < n;i++){q.push(i+1);}while(q.size()>=2){printf("%d\t",q.front());//输出需要队头第一张，并出队列q.pop();q.push(q.front());//将队头第二张放到队尾q.pop();}printf("%d\n",q.front());//输出剩余的最后一张return 0;
}

Demo2：STL堆栈

【题目】铁轨（题目来自刘汝佳《算法竞赛入门》）

某城市有一个火车站铁轨铺设如图，有n节车厢从A方向驶入车站，按进站顺序编号为1~n。你的任务是让它们按照某种特定的顺序进入B方向的铁轨并驶出车站。为了重组车厢，你可以借助中转站C。这是一个可以停放任意多节车厢的车站。但由于末端封顶，驶入C的车厢必须按照相反的顺序驶出C。对于每个车厢，一旦从A移入C，就不能再回到A了，一旦C移入B，就不能回到C了，换句话说，在任意时刻，只有两种选择：A->C，C->B。

样例输入：

1 2 3 4 5

5 4 1 2 3

6 5 4 3 2 1

样例输出：

Yes

【分析】A、B车站为队列，C站位LIFO栈。将A车站队列初始化为1~n，B车站队列初始化为用户输入的顺序，进行以下循环，直到B队列为空：

1.如果A车站的队头和B车站的队头相等，直接将A车站对头列车开到B车站（A、B队列均进行出队列操作）。

2.否则如果C栈顶元素和B队头元素相等，则将C的栈顶列车驶入B（C出栈操作，B出队列操作）。

3.否则如果A队列不为空，将A队列队头元素入C栈，

4.否则标记不成功，跳出循环。

【代码】

#include <cstdio>
#include <stack>
#include <queue>
using namespace std;int main()
{int n,temp;while(scanf("%d",&n)==1){stack<int> c;queue<int> a,b;for(int i=1;i<=n;i++){scanf("%d",&temp);a.push(i);b.push(temp);}int ok=1;while(b.size()!=0){if(a.size()!=0&&a.front()==b.front()){a.pop();b.pop();}else if(c.size()!=0 && b.front()==c.top()){b.pop();c.pop();}else if(a.size()!=0){c.push(a.front());a.pop();}else {ok=0;break;}}if(ok)printf("Yes");elseprintf("No");}return 0;	
}

https://www.dkcj.cn/info/15179.html

【C++】STL队列和栈的使用

Demo1：STL队列

Demo2：STL堆栈

相关文章：

mongodb的shell命令

字典、集合及其特性

[HDOJ2819]Swap（二分图最大匹配, 匈牙利算法）

脚本路径问题_dirname

【iOS官方文档翻译】iOS蓝牙的基本概念

元组、列表、字典及集合练习

【iOS】sqlite3的使用（増删改查）

网上搜集了点资料，学web的人互相分享共同进步吧（php编码的好习惯必须养成）...

div模拟textarea文本域轻松实现高度自适应——张鑫旭

【iOS】Mapkit的使用：地图显示、定位、大头针、气泡等

java.lang.NoSuchMethodError: org.springframework.core.io.ResourceEditor错误

SDUTOJ 1293 乘积最大的分解（数论）

列表及字典生成式

[SQL基础教程] 1-5 表的删除和更新

【iOS】自定义控件入门:可拖动的环形进度

在.NET2.0中解析Json和Xml

虚拟机的基本操作

strong assign属性

iOS7的界面上移问题

【Android】ActionBar的使用（1）

装饰器及例题分析

iOS开发系列--让你的应用“动”起来

ios app 砸壳

基于visual Studio2013解决面试题之0804复杂链表

python考试编程题

【分享】bootstrap学习笔记

大三下学期总结

通过 cygwin64 自己编译对应的 Tera Term cyglaunch.exe

面向对象概念及三大特点

【Android】ViewPager实现无限循环滚动