栈和队列的相互实现
文章目录
- 一、用栈实现队列
- 入队:
- 出队:
- Java代码实现:
- 二、用队列实现栈
- 入栈:
- 出栈:
- Java代码实现:
- 附:C++版代码
- 1、用栈实现队列
- 2、用队列实现栈
栈(stack):先进后出,后进先出。限定在表尾进行插入删除的线性表。
队列(queue):先进先出,后进后出。限定在表头删除,在表尾插入的线性表。
那么如何用栈来实现队列和如何用队列来实现栈的数据结构呢?
一、用栈实现队列
单个栈肯定无法实现队列,所以至少应该用两个栈来实现队列。
入队:
- 数据栈:每次有新元素来时,先把存放的元素弹入辅助栈,再把新元素压入数据栈底;
- 辅助栈:等待新元素进入数据栈以后依次弹出元素压入数据栈中;
根据这两个栈的功能,不管是数据栈中是否有元素存在,新元素都会被沉到栈底中,实现入队的功能。
出队:
由于在入队时,通过数据栈与辅助栈的交换,实现了后加入的元素沉在栈底,先进入的元素保留在栈顶,直接通过出栈弹出即可
Java代码实现:
public class StackImplQueue {// 数据栈private Stack<Integer> stack;// 辅助栈private Stack<Integer> aux;StackImplQueue() {stack = new Stack<>();aux = new Stack<>();}// 入队--通过数据栈与辅助栈相互交换,保证新加入的元素沉在数据栈底public void enqueue(Integer e) {while (!stack.isEmpty()) {aux.push(stack.pop());}stack.push(e);while(!aux.isEmpty()){stack.push(aux.pop());}}// 出队--弹出数据栈元素public Integer dequeue(){return stack.pop();}// 查看队头元素public Integer peek(){return stack.peek();}// 是否为空public boolean isEmpty(){return stack.isEmpty();}public static void main(String[] args) {StackImplQueue queue = new StackImplQueue();queue.enqueue(1);System.out.println(queue.peek());queue.enqueue(2);System.out.println(queue.peek());queue.enqueue(3);System.out.println(queue.peek());System.out.println("=============");System.out.println(queue.dequeue());System.out.println(queue.dequeue());System.out.println(queue.dequeue());}
}
二、用队列实现栈
入栈:
入栈的元素要在队头,而队列入队的元素在队尾,只需让队头至队尾前的其它所有元素依次出队再入队,直至在队尾新加入的元素被移到队头,也即实现了让新压入的元素保留在栈顶。
出栈:
由于在入栈时保证队列中新加入队尾的元素被移到了队头,出栈只需弹出队头元素即可
Java代码实现:
public class QueueImplStack {// 定义队列private Queue<Integer> queue;public QueueImplStack() {queue = new LinkedList();}// 入栈--在队尾加入元素后,让其他元素按顺序出队再入队,保持新加入的元素永远在队头public void push(Integer e) {queue.offer(e);int size = queue.size();int i = 0;while (i < size - 1) {queue.offer(queue.poll());i++;}}// 出栈--将队尾前的其它所有元素出队再入队,直至队尾元素移到队头public Integer pop() {return queue.poll();}// 查看栈顶元素--即队头元素public Integer peek() {return queue.peek();}// 是否为空public boolean isEmpty() {return queue.isEmpty();}public static void main(String[] args) {QueueImplStack stack = new QueueImplStack();stack.push(1);System.out.println(stack.peek());stack.push(2);System.out.println(stack.peek());stack.push(3);System.out.println(stack.peek());System.out.println("=============");System.out.println(stack.pop());System.out.println(stack.pop());System.out.println(stack.pop());System.out.println(stack.isEmpty());}
}
附:C++版代码
1、用栈实现队列
#include<stack>
#include<iostream>using namespace std;class queue{
public:stack<int> dataStack;//数据栈 stack<int> auxStack;//辅助栈//入队,通过辅助栈让新元素沉于栈底
void push(int x) {while(!dataStack.empty()){auxStack.push(dataStack.top());dataStack.pop();}dataStack.push(x);while(!auxStack.empty()){dataStack.push(auxStack.top());auxStack.pop();}
}// 出队--弹出数据栈元素int outqueue(){int temp = dataStack.top();dataStack.pop();return temp;}// 查看队头元素int top(){return dataStack.top();}// 是否为空bool empty(){return dataStack.empty();}};int main(){queue iq;iq.push(1);cout<<iq.top()<<endl;iq.push(2);cout<<iq.top()<<endl;iq.push(3);cout<<iq.top()<<endl;cout<<"-------------"<<endl;cout<<iq.outqueue()<<endl;cout<<iq.outqueue()<<endl;cout<<iq.outqueue()<<endl; return 0;
}
2、用队列实现栈
#include<deque>
#include<iostream>using namespace std;class stack{
public:deque<int> de;// 入栈--在队尾加入元素后,让其他元素按顺序出队再入队,保持新加入的元素永远在队头void push(int x) {de.push_front(x);int size = de.size();int i = 0;while (i < size - 1) {de.push_front(de.back());de.pop_back();i++;}}// 出栈--将队尾前的其它所有元素出队再入队,直至队尾元素移到队头int pop() {int temp = de.front();de.pop_front();return temp;}// 查看栈顶元素--即队头元素int top() {return de.front();}// 是否为空bool isEmpty() {return de.empty();}
};int main(){stack iq;iq.push(1);cout<<iq.top()<<endl;iq.push(2);cout<<iq.top()<<endl;iq.push(3);cout<<iq.top()<<endl;cout<<"-------------"<<endl;cout<<iq.pop()<<endl;cout<<iq.pop()<<endl;cout<<iq.pop()<<endl; return 0;
}
本文参考来源:
- 用队列实现栈,用栈实现队列,听起来有点绕,都搞懂了就掌握了精髓! - 云+社区 - 腾讯云 (tencent.com)
- 《小灰的算法之旅》
相关文章:
栈和队列的相互实现
文章目录一、用栈实现队列入队:出队:Java代码实现:二、用队列实现栈入栈:出栈:Java代码实现:附:C版代码1、用栈实现队列2、用队列实现栈栈(stack):先进后出&a…...
iTab新标签页重磅更新 |这些功能绝对有你想要的新体验!
01 写在前面 csdn的朋友们,你好哦,我是iTab 插件的独立开发者,今天给大家安利一下我做的这款桌面插件。 首先要告诉大家一个好消息: 最近iTab新标签页被Edge 浏览器商店官方热门🔥推荐啦。 在此,特别感谢…...
【改机教程】iOS系统去除小黑条,改拍照声、拨号音、键盘音,不用越狱,支持所有机型
大家好,上次给大家分享了几个iOS系统免越狱改机教程 今天带来最新的教程,这次修改利用的是同一个漏洞,由外网大神 tamago 开发,国内大神冷风 进行汉化和优化 可以修改的地方包括 去除底部小黑条 dock栏透明 桌面文件夹透明 桌面…...
Android10开机向导中复用设置中的Wifi界面
很多时候我们需要定制开机向导,在开机向导界面我们一般会实现联网和设置时间等功能,考虑复用与稳定性问题,我们最好复用设置中的WiFi设置和日期设置。但是设置中的wifi设置界面默认是没有下一步按钮的,这会让用户感觉很奇怪。在以…...
川农机械专业小伙转行Java开发,年薪20w
本期学员就业故事,知了姐邀请到一位“特别”的同学,一位从知了堂就业成功近两年的学员再度接受我们的采访。 来自四川农业大学的曾同学,一个本来学机械开挖掘机的粗犷男人,因为不断地努力学习编程,最终成为一个性格闷…...
华为OD机试题 - 打印文件(JavaScript)| 机考必刷
更多题库,搜索引擎搜 梦想橡皮擦华为OD 👑👑👑 更多华为OD题库,搜 梦想橡皮擦 华为OD 👑👑👑 更多华为机考题库,搜 梦想橡皮擦华为OD 👑👑👑 华为OD机试题 最近更新的博客使用说明本篇题解:打印文件题目输入输出示例一输入输出示例二输入输出Code代码解析…...
免费常用API大全,程序员必备
淘宝接口 淘宝开放平台 http://open.taobao.com/?spma219a.7395905.1.1.YdFDV6 APISpace 生活常用 今天吃什么:随机返回一顿美味食物,解决你今天吃什么的难题。 星座查询:根据日期或星座名称,查询星座详细信息,包…...
MySQL主从复制,读写分离
目录 一、MySQL主从复制介绍 MySQL复制过程分成三步 二、主库配置master 1、步骤1 2、第二步:重启Mysql服务 3、第三步:登录Mysql数据库,执行下面SQL 4、第四步:登录Mysql数据库,执行下面SQL,记录下结果中File和…...
什么是UEFI签名认证?UEFI签名有什么好处?
为了防御恶意软件攻击,目前市面上所有电脑设备启动时默认开启安全启动(Secure Boot)模式。安全启动(Secure Boot)是UEFI扩展协议定义的安全标准,可以确保设备只使用OEM厂商信任的软件启动。UEFI签名认证就是对运行在 UEFI 系统下的 efi 驱动和通过 UEFI …...
案例14-课程推送页面逻辑整理--vue
目录一级目录二级目录三级目录一、背景介绍二、问题分析问题1:逻辑边界不清晰,封装意识缺乏问题问题2:展示效果上的问题三、解决过程问题一 代码结构混乱问题解决问题二 代码结构混乱问题解决问题三 展示效果上的细微问题四、总结一级目录 二…...
5大GPU厂商共建 | openKylin社区GPU SIG首次例会召开!
3月8日,openKylin社区GPU SIG首次例会以线上形式召开。此次会议由长沙景美集成电路设计有限公司、摩尔线程智能科技(北京)有限责任公司、格兰菲智能科技有限公司、象帝先计算技术(重庆)有限公司等GPU厂商的多位SIG Mai…...
SpringBoot读取配置文件
目录一、简介1、SpringBoot 中常用读取配置方法2、 ConfigurationProperties和Value的区别二、使用 ConfigurationProperties 读取配置三、使用 Value 读取配置一、简介 在日常开发使用 SpringBoot 框架时,经常有一些配置信息需要放置到配置文件中,我们…...
51驱动NRF24L01通信,NRF24L01与TTL转NRF24L01模块通信
51驱动NRF24L01通信,NRF24L01与TTL转NRF24L01模块通信NRF24L01一、简介二、引脚功能描述程序设计一、对 24L01 的程序编程的基本思路如下:二、Tx 与 Rx 的配置过程1、Tx 模式初始化过程:2、Rx 模式初始化过程:三、基本程序函数通信…...
C++友元
欢迎来观看温柔了岁月.c的博客 目前 设有C学习专栏 C语言项目专栏 数据结构与算法专栏 目前主要更新C学习专栏,C语言项目专栏不定时更新 待C专栏完毕,会陆续更新C项目专栏和数据结构与算法专栏 一周主要三更,星期三,星期五&#x…...
MySQL内置函数
文章目录日期函数字符串函数数学函数其他函数日期函数 获取年月日: mysql> select current_date(); ---------------- | current_date() | ---------------- | 2023-02-01 | ---------------- 1 row in set (0.00 sec)获得时分秒: mysql> se…...
mysql数据库之innodb存储引擎架构之内存架构
一、逻辑存储结构 mysql5.5版本开始,默认使用innodb存储引擎,它擅长事务处理,具有崩溃恢复特性,在日常开发中使用非常广泛。 架构图(左侧为内存架构,右侧为磁盘架构) 二、 内存架构。 1、缓冲…...
Vue:(三十五)路由vue-router
今天,我们开始学习vue中一个很关键的知识点,路由。理解vue的一个插件库,专门用来实现SPA应用单页web应用整个应用只有一个完整的页面点击页面中的导航连接不会刷新页面,只会做页面的局部更新数据需要通过ajax请求获取下来…...
Dynabook笔记本电脑无法开机怎么重装新系统?
Dynabook笔记本电脑无法开机怎么重装新系统?有用户使用Dynabook笔记本电脑出现了无法正常开机的情况。遇到这样的问题是我们的电脑系统出现了损坏,可以尝试进行系统修复。如果无法修复的话,就需要进行系统重装了。以下为大家带来Dynabook笔记…...
React Native基础知识点
1、组件 与react编写web应用不同,不是使用div、span等标签。而是使用RN官方提供的组件,如View、Text等组件来搭建页面 2、宽高 React Native 中的尺寸都是无单位的,表示的是与设备像素密度无关的逻辑像素点。默认值为auto <View style{{…...
nginx 平滑升级
背景介绍 因为一些原因,比如说 Nginx 发现漏洞、应用一些新的模块等等,想对 Nginx 的版本进行更新,最简单的做法就是停止当前的 Nginx 服务,然后开启新的 Nginx 服务。但是这样会导致在一段时间内,用户是无法访问服务…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...
苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...
WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成
厌倦手动写WordPress文章?AI自动生成,效率提升10倍! 支持多语言、自动配图、定时发布,让内容创作更轻松! AI内容生成 → 不想每天写文章?AI一键生成高质量内容!多语言支持 → 跨境电商必备&am…...
dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...
Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...
动态 Web 开发技术入门篇
一、HTTP 协议核心 1.1 HTTP 基础 协议全称 :HyperText Transfer Protocol(超文本传输协议) 默认端口 :HTTP 使用 80 端口,HTTPS 使用 443 端口。 请求方法 : GET :用于获取资源,…...
深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...
