2018.9.5 Java中使用栈来模拟队列
2024-10-19 19:44:03
栈的规律是是先进后出 队列的规律是先进先出
栈模拟队列
首先我们定义两个栈,一个放数据,一个出数据,判断B栈是否有元素,有元素则直接pop;没有元素则需要我们将A里面的元素出栈然后放到B里面,再取出,即实现队列的先进先出
最初思路想法
使用A和B两个栈来模拟队列,一个为入栈一个为出栈,这样来实现队列
两个栈stack1,stack2 入队在stack2.如果入队时stack2 不为空,那么stack2必须先清空(数据迁移到stack1 ),如果出对时stack2不为空,直接出栈。如果stack2为空,则需要把stack1中的数据全部转移到stack2中
修正后思路想法
利用两个栈S1和S2来模拟一个队列,当需要向队列中插入一个元素时,用S1来存放已经输入的元素,即S1执行入栈操作,当需要出队时,则对S2执行出栈操作。由于从栈中取出元素的顺序是原顺序的逆序,所以先将S1的所有元素全部出栈并入栈到S2中,再在S2中齿形出栈操作,就能实现出队操作,而在执行此操作之前,先判断S2是否为空,否则会导致顺序混乱,当栈S1和S2都为空时队列为空。
代码实现
import java.util.Stack;
/**
* 使用两个栈来模拟队列
* @author legend
* @param <E>
*
*/
public class MyQueue<E> {
/**
* 使用Java类库里面的stack定义两个栈 一个用于出栈一个用于入栈
*/
private Stack<E> stack = new Stack<E>();
private Stack<E> stack2 = new Stack<E>();
/**
* 入栈和出栈是为了增加线程安全 使用了同步
*/
public synchronized void put(E data) {
stack.push(data);
}
public synchronized E pop() {
//如果栈2为空,则把栈1里面的数据压到2里面,在出栈,即实现队列 若不为空,那么stack2中元素弹出(出列),若为空则提示队列为空
if(stack2.isEmpty()) {
while(!stack.isEmpty()) {
stack2.push(stack.pop());
return stack2.pop();
}
}
//否则直接出栈,实现栈对模拟队列
return stack2.pop();
}
public static void main(String[] args) {
MyQueue<Integer> myQueue = new MyQueue<Integer>();
myQueue.put(1);//第一元素
myQueue.put(2);//第二元素
myQueue.put(3);//第三元素
System.out.println("栈模拟队列后head的数据"+myQueue.pop());
}
}
2,队列模拟栈
两个队列q1,q2
入栈在q1,。q2作为一个缓冲队列。
出栈时,将q1除最后一个外,全部入队列q2。q1出队即是出栈。
最新文章
- css对齐
- NHibernate和 FluentNHibernate
- 3527: [Zjoi2014]力 - BZOJ
- android下身份验证方式调用webservice
- Windows下Subversion和Apache的安装及配置(一)
- 设置图片Alpha
- replace empty char with new string,unsafe method和native implementation的性能比较
- PHP 计算页面执行时间
- Avro基础
- A Corrupt Mayor&#39;s Performance Art(线段树区间更新+位运算,颜色段种类)
- AfxEnableControlContainer()
- 5.java.lang.IndexOutOfBoundsException(数组下标越界异常)
- mysql各版本区别
- 解决Android Studio Gradle Build特别慢的问题
- 词根:lun = moon, 表示“月亮”
- [转] C++中为什么要用指针,而不直接使用对象?
- OpenJDK-study-002 从GitHub下载openjdk,以及Cygwin的安装
- Effective Java 第三版——77. 不要忽略异常
- 简单使用metamascara
- 关于SS的一点笔记
热门文章
- 用HTMLParser解析html时报错:No module named 'htmlentitydefs'
- Docker &; ASP.NET Core 教程
- java——ArrayList 的存在有什么意义?
- getElementsByTagName 、 getElementsByName 、getElementById区别
- Neutron命令测试2
- (转)Python3.5 day3作业二:修改haproxy配置文件
- (七)使用jedis连接单机和集群(一步一个坑踩出来的辛酸泪)
- 如何实现Nginx+Keepalived中Nginx进程的高可用
- php锁定文本框内容的方法
- pat1100. Mars Numbers (20)