Java 栈和队列的相互转换详解
作者:Word码鸭 发布时间:2021-09-22 05:00:12
标签:Java,栈,队列,转换
栈和队列的本质是相同的,都只能在线性表的一端进行插入和删除。因此,栈和队列可以相互转换。
用栈实现队列—力扣232题
题目要求:仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作
使用双栈来实现队列,我们就可以让一个栈储存具体元素,另一个栈做辅助
上图可以看到,新元素进栈时,要确保该栈为空。进入栈的元素按顺序存到辅助栈中,等新元素进入栈之后,再将辅助栈中的元素按顺序出到该栈中。这样操作之后,栈中元素存放的顺序就和队列的一样啦
代码实现:
//双栈模拟队列
public class MyQueue{
//实际存储元素的栈
private Stack<Integer> s1 = new Stack<>();
//辅助栈
private Stack<Integer> s2 = new Stack<>();
public MyQueue() {
}
//将元素 x 推到队列的末尾
public void push(int x) {
if (s1.empty()){//栈为空,直接放入x
s1.push(x);
}else {
//此时不为空
//先把s1所有元素弹出放入s2
while (!s1.empty()){
s2.push(s1.pop());//s2放入的值就是s2弹出的值
//以下两句和上一句相同
// int val = s1.pop();
// s2.push(val);
}
//将新元素直接放入s1,此时新元素就处在s1的栈顶
s1.push(x);
//再次将s2的所有值依次弹出放入s1
while (!s2.empty()){
s1.push(s2.pop());
}
}
}
//从队列的开头移除并返回元素
public int pop() {
return s1.pop();
}
//返回队列开头的元素
public int peek() {
return s1.peek();
}
//判断队列是否为空
public boolean empty() {
return s1.empty();
}
}
用队列实现栈—力扣225题
题目要求:仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作
1. 双队列实现栈
使用双队列实现栈, q1是存储元素的队列,保证q2添加元素之后永远为空队列(新元素直接入q2),保证新元素处在队首。这样的话,新元素入队之后,另外一个队列的元素依次出队然后入队,这样就实现了一个栈。
代码实现:
public class MyStack {
//q1是存储元素的队列
private Queue<Integer> q1 = new LinkedList<>();
//q2是辅助队列
//添加元素后保证q2永远为空
private Queue<Integer> q2 = new LinkedList<>();
public MyStack () {
}
//将元素 x 压入栈顶
public void push(int x) {
//新入队元素直接入q2,成为q2队首
q2.offer(x);
//将q1中的所有元素依次出队,入q2
while (!q1.isEmpty()){
q2.offer(q1.poll());
}
//q1为空,q2为存储元素的队列,互换引用指向
//互换之后,q1任然是存储元素的队列,q2为空
Queue<Integer> temp = q1;
q1 = q2;
q2 = temp;
}
// 移除并返回栈顶元素
public int pop() {
return q1.poll();
}
//返回栈顶元素
public int top() {
return q1.peek();
}
//判断栈是否为空
public boolean empty() {
return q1.isEmpty();
}
}
2.一个队列实现栈
先将元素入队,再将之前的元素依次出队再入队即可!也就是说,保证新元素在队首
代码实现:
public class MyStack {
private Queue<Integer> queue = new LinkedList<>();
public MyStack() {
}
public void push(int x) {
//记录之前元素的个数
int size = queue.size();
//将新元素入队
queue.offer(x);
//将之前的元素依次出队再入队,新元素就在队首位置
for (int i = 0; i < size; i++) {
queue.offer(queue.poll());
}
}
public int pop() {
return queue.poll();
}
public int top() {
return queue.peek();
}
public boolean empty() {
return queue.isEmpty();
}
}
这几个例题实践目的是更加熟悉的掌握和了解栈和队列,实际应用中是不推荐的哦。
来源:https://blog.csdn.net/m0_58672924/article/details/122763811
0
投稿
猜你喜欢
- 废话开篇:iOS与android在实现列表界面的时候是有重用机制的,目的就是减少内存开销,用时间换空间。个人感觉flutter并没有特别强调
- 需求是需要在TextView前端加入一个标签展示。最终效果图如下:根据效果图,很容易就能想到使用SpannableStringBuilder
- PS:本文包含了大部分strings函数的说明,并附带举例说明。本来想自己整理一下的,发现已经有前辈整理过了,就转了过来。修改了原文一些源码
- 本文实例为大家分享了Java Swing实现扫雷源码的具体代码,供大家参考,具体内容如下先来看下效果运行时只需要创建一个GameWindow
- 将JavaDoc 注释 生成API文档1. 打开java代码,编写JavaDoc 注释,只有按照java的规范编写注释,才能很好的生成API
- 自从接触javascript以来,对this参数的理解一直是模棱两可。虽有过深入去理解,但却也总感觉是那种浮于表面,没有完全理清头绪。但对于
- 一个是新浪微博,腾讯微博的分享按钮,一个是他们的绑定情况(其实就是是否授权)。点击微博分享中新浪或腾讯按钮,就进行相应的授权(若没授权),显
- 本文介绍了SpringCloud +Zookeeper完成配置中心,分享给大家,具有如下:使用场景项目配置更改不需要打包,重启提供配置文件的
- 一 :问题背景问题:当查询接口较复杂时候,数据的获取都需要[远程调用],必然需要花费更多的时间。 假如查询文章详情页面,需要如下标注的时间才
- 前言:什么是多数据源?最常见的单一应用中最多涉及到一个数据库,即是一个数据源(Datasource)。那么顾名思义,多数据源就是在一个单一应
- 已知两个链表list1和list,2,各自非降序排列,将它们合并成另外一个链表list3,并且依然有序,要求保留所有节点。实现过程中,lis
- 邮件绑定功能【需求】1、 用户注册时,输入邮箱2、 通过Javamail技术,向用户邮箱发送一封祝贺邮件1、javamail发送邮件1.1、
- 前言我们一说到spring,可能第一个想到的是 IOC(控制反转) 和 AOP(面向切面编程)。没错,它们是spring的基石,得益于它们的
- 日期、数字格式化显示,是web开发中的常见需求,spring mvc采用XXXFormatter来处理,先看一个最基本的单元测试:packa
- 第1部分 ArrayList介绍ArrayList 是一个数组队列,相当于 动态数组。与Java中的数组相比,它的容量能动态增长。它继承于A
- @RequestBody配合@Valid校验入参参数自定义一个Controllerimport com.example.demo.pojo.
- 原来一直使用shiro做安全框架,配置起来相当方便,正好有机会接触下SpringSecurity,学习下这个。顺道结合下jwt,把安全信息管
- 本文需求实现了java通过方向键控制小球移动的具体过程,供大家参考,具体内容如下需求分析:第一 要画出一个小球第二 要能通过控制方向键控制它
- 如果没有安装过maven,是用的idea自带的maven,那就是idea的安装目录下 /plugins/maven/lib/maven3这个
- Web基础和HTTP协议┌─────────┐┌─────────┐