【剑指offer】面试题9-用两个栈实现队列

题目

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

1.思路

（1）stack1只用来负责push()操作，只要push()就对stack1进行入栈操作，即queue.push – 对应– stack1.push()；
（2）stack1和stack2协同完成pop()操作，queue.pop()时会有两种情况：
①stack2非空，此时直接对stack2进行stack2.pop()操作即可;
②stack2为空，此时需要先从stack1中将全部元素出栈，然后依次压入栈stack2中，从而实现模拟队列的先进先出特性。

2.代码（Java实现）

import java.util.Stack;
public class Solution {
	Stack<Integer> stack1 = new Stack<Integer>();
	Stack<Integer> stack2 = new Stack<Integer>();
	// 模拟push()
	public void push(int node) {
		stack1.add(node);
	}
	// 模拟pop()
	public int pop() {
		if (stack2.isEmpty()) {				//stack2为空
			while (!stack1.isEmpty()) {		//将stack1中元素全部出栈
				stack2.push(stack1.pop());	//依次压入栈stack2中
			}
		}
		return stack2.pop();
	}
}

PS：苏大计算机考研真题也曾考过这个题，用简答的形式对用两个栈实现队列进行描述。

本文作者： whtli
本文链接： https://hexo.whtli.cn/archives/ea6627bd.html
版权声明： 遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。