2019年面试题：由两个栈组成的队列
由两个栈组成的队列
【题目】
编写一个类,用两个栈实现队列,支持队列的基本操作(add,poll, peek)。
【解答】
栈的特点是先进后出,而队列的特点是先进先出。我们用两个栈正好能把顺序反过来实现类似队列的操作。
具体实现上是一个栈作为压入栈,在压入数据时只往这个栈中压入,记为 stack Push;另一个栈只作为弹出栈,在弹出数据时只从这个栈弹出,记为 stackpop.
因为数据压入栈的时候,顺序是先进后出的。那么只要把stack Push的数据再压入 stack Pop中,顺序就变回来了。例如,将1~5依次压入 stack Push,那么从 stack Push的栈顶到栈底为51,此时依次再将51倒入 stackpop,那么从 stackpop的栈顶到栈底就变成了1~5。再从 stack Pop弹出时,顺序就像队列一样,如图1-3所示。
听起来虽然简单,实际上必须做到以下两点。
1.如果 stack Push要往 Estack Pop中压入数据,那么必须一次性把stackPush中的数据全部压入。
2.如果 stack Pop.不为空, stack Push绝对不能向 stack Pop中压入数据。
违反了以上两点都会发生错误
违反1的情况举例:1~5依次压入 stack Push, stack Push的栈顶到栈底为5~1,从 stack Push压入 stack Pop时,只将5和4压入了tack Pop, stack Push还剩下1、2、3没有压入。此时如果用户想进行弹出操作,那么4将最先弹出,与预想的队列顺序就不一致。
违反2的情况举例:1~5依次压入 stack Push, stack Push将所有的数据压入了 stack Pop,此时从 stack Pop的栈顶到栈底就变成了15此时又有610依次压入 stack Push, stackpop不为空, stack Push不能向其中压入数据。如果违反2压入了 stackpop,从 stack Pop的栈顶到栈底就变成了610、15。那么此时如果用户想进行弹出操作6将最先弹出,与预想的队列顺序就不一致。
上面介绍了压入数据的注意事项。那么这个压入数据的操作在何时发生呢?
这个选择的时机可以有很多,调用add、poll和peek三种方法中的任何一种时发生“压”入数据的行为都是可以的。只要满足如上提到的两点,就不会出错。
测试类
/**
* Created by ${wuyupku} on 2019/3/27 14:53
*/
public class TwoStacksQueue {
private Stack<Integer> stackPush;//压入数据栈
private Stack<Integer> stackPop; //弹出数据栈
public TwoStacksQueue() {
this.stackPop = new Stack<>();
this.stackPush = new Stack<>();
}
/**
* 入队操作
* 直接将数据压入压入数据栈
* @param push
*/
public void push(int push) {
this.stackPush.push(push);
}
/**
* 出队操作
* @return
*/
public int poll() throws Exception {
if (stackPush.isEmpty() && stackPop.isEmpty()) {
throw new Exception("队列中没有数据");
} else if (stackPop.isEmpty()) {
//弹出数据栈为空，可以将整个压入数据栈中的数据倒入弹出数据栈
while (!stackPush.isEmpty()) {
stackPop.push(stackPush.pop());
}
}
return stackPop.pop();
}
/**
* 返回队头元素
* @return
* @throws Exception
*/
public int peek() throws Exception {
if (stackPush.isEmpty() && stackPop.isEmpty()) {
throw new Exception("队列中没有数据");
}else if (stackPop.isEmpty()) {
//弹出数据栈为空，可以将整个压入数据栈中的数据倒入弹出数据栈
while (!stackPush.isEmpty()) {
stackPop.push(stackPush.pop());
}
}
return stackPop.peek();
}
}主方法:
/**
* Created by ${wuyupku} on 2019/3/27 14:53
*【题目】：编写一个类，用两个栈实现队列，支持队列的基本操作（add、poll、peek）
*/
public class Main {
public static void main(String[] args) throws Exception {
TwoStacksQueue twoStacksQueue = new TwoStacksQueue();
int p = 0;
for (; p < 100; p++) {
int i = (int) (Math.random() * 1000);
twoStacksQueue.push(i);
System.out.println(i + "入队" );
}
for (; p > 1; p--) {
int pop = twoStacksQueue.poll();
System.out.println("出队元素:" + pop );
}
}
}