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

C++的STL队列实现栈

编程日记 2024-04-22 13:00:00

使用C++的队列STL实现一个栈的数据结构
实现以下四个函数：
1.push(x) : 将元素x压入栈中
2.pop() : 弹出(移除)栈顶元素
3.top() : 返回栈顶元素
4.empty() : 判断栈是否是空

队列的数据结构为先入先出，栈的数据结构为先入后出；
即队列的元素顺序与栈中元素的顺序是相反的，所以只需要保证后面插入的元素是在前面的元素之前能够被弹出即可。
在这里插入图片描述
转换成栈之后的存储形态，弹出队列头部的元素即类似与弹出栈顶元素

这里插入元素时维护一个临时队列，即可将原先队列中的元素顺序做一个逆置调整。
实现算法如下(文末有测试代码)：

void push(int x) {queue<int> tmp_queue;tmp_queue.push(x);/*对所有原队列的元素做顺序调整*/while (!data.empty()){tmp_queue.push(data.front());data.pop();}/*将调整后的顺序放入原队列，此时该队列元素顺序已经为栈存储的元素顺序*/while (!tmp_queue.empty()){data.push(tmp_queue.front());tmp_queue.pop();}
}

实现如下：

#include <iostream>
#include <algorithm>
#include <queue>using namespace std;
class My_stack {private:queue<int> data;public:void push(int x) {queue<int> tmp_queue;tmp_queue.push(x);while (!data.empty()){tmp_queue.push(data.front());data.pop();}while (!tmp_queue.empty()){data.push(tmp_queue.front());tmp_queue.pop();}}/*弹出元素，即弹出队列头部元素*/int pop() {int x = data.front();data.pop();return x;}/*此时队列中的元素已经和栈存储的元素同步了，直接返回对头元素*/int top() {return data.front();}   bool empty(){return data.empty();}
};int main() {My_stack s;cout << "construct the stack " << endl;int tmp;for (int i = 0;i < 5; ++i) {cin >> tmp;s.push(tmp);}cout << "top " << s.top() << endl;cout << "pop " << s.pop() << endl;cout << "top " << s.top() << endl;s.push(10);cout << "top after push '10' " << s.top() << endl;return 0;
}

输出如下：

construct the stack 
1 3 4 5 2
top 2
pop 2
top 5
top after push '10' 10

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

C++的STL队列实现栈

相关文章：

PHP实现XML传输

wordpress短代码转php,WordPress中的shortcode短代码功能使用详解

在ESXi主机上关闭无响应的虚拟机

React和Jquery比较

C++的STL栈实现队列

如何设置SOLR的高亮 (highlight)？

java快排算法解读,java 快排的思路与算法

SQL：EXISTS的用法理解（转）

002.Heartbeat部署及httpd高可用

C++的STL栈实现获取栈中最小元素的成员

java servlet applet,详解Java Servlet与Applet比较

NTP时间同步服务器搭建

OI基础系列之最大子数组问题

springCloud Zuul网关

f-free 查看系统中空闲和使用的内存

对比两个同类型的泛型集合并返回差异泛型集合 ——两个List类名的比较

php insert failed,较大的MySQL INSERT语句导致PHP错误

js 取得文件大小

Spring Boot thymeleaf模版支持，css,js等静态文件添加

s-sed(stream editor) 文本填充和编辑基本使用

c语言动态迁移mysql,flask-migrate动态迁移数据库

软考之路-网络攻击：主动攻击和被动攻击

edge.js架起node.js和.net互操作桥梁

connect() failed (111: Connection refused) while connecting to upstream, cli

C++的STL 栈实现判断栈的出栈顺序是否合理

fire.php,Fire PHP

json_encode时中文编码转正常状态

验证URL链接和IP有效性的JS代码（正则表达式）

[转帖]什么是光纤的波长？看看有哪些是你不知道的！

C++的STL 栈实现四则运算