03-两个队列模拟一个栈
数据结构特点:
1.队列和栈数据结构底层都是线性表,实现上可以为数组或者链表
2.队列:先进先出(FIFO=first in first out),有队尾进队头出
3.栈:后进先出(LIFO=last in first out)
/**
* 2个队列模拟栈
* 栈:LIFO(last in first out)
* 队列:FIFO(first in first out)
* 思路:首先队列是先进先出,我们可以发现队列无论怎么倒,我们不能逆序一个队列。
* 那么就得另谋出路,但是可以预知无非就是两个队列进行交替的入队出队操作,
* 那么唯一要做的就是判断目前出队的值是否是按照放入元素顺序中最后放入的元素
* 参考链接:https://www.jianshu.com/p/285419bfa880
* @author lqs
* @param <E>
*/
public class StackImplByTwoQueue<E> {
Queue<E> queue1 = new LinkedList<>();
Queue<E> queue2 = new LinkedList<>();
public E push(E e){
if (!queue1.isEmpty()) {
queue1.offer(e);
}else if(!queue2.isEmpty()){
queue2.offer(e);
}else{
queue1.offer(e);
}
return e;
}
public E pop(){
E result = null;
if (!queue1.isEmpty()) {
while (!queue1.isEmpty()) {
result=queue1.poll();
if(!queue1.isEmpty()){
queue2.offer(result);
}
}
}else if(!queue2.isEmpty()){
while (!queue2.isEmpty()) {
result=queue2.poll();
if(!queue2.isEmpty()){
queue1.offer(result);
}
}
}
return result;
}
public static void main(String[] args) {
StackImplByTwoQueue<Object> mockStack = new StackImplByTwoQueue<>();
mockStack.push(1);
mockStack.push(2);
mockStack.push(3);
mockStack.push(4);
mockStack.push(5);
System.out.println(mockStack.pop());
System.out.println(mockStack.pop());
System.out.println(mockStack.pop());
System.out.println(mockStack.pop());
System.out.println(mockStack.pop());
mockStack.push(6);
mockStack.push(7);
mockStack.push(8);
System.out.println(mockStack.pop());
}
}
Last updated
Was this helpful?