剑指Offer面试题7 & Leetcode232
Implement Queue using Stacks
用两个栈实现队列
Implement the following operations of a queue using stacks.
push(x) – Push element x to the back of queue.pop() – Removes the element from in front of queue.peek() – Get the front element.empty() – Return whether the queue is empty.
解题思路
考虑：push()时可以直接push进stackA，pop()时,如果stackA不为空，则如果想拿到队列头部元素，即stackA栈底元素，需要将stackA中的元素全部pop()出并存进stackB,此时stackB的栈顶元素即为队列头部元素，pop()即可。
当再一次pop()时，分两种情况:第一：stackB非空，则直接pop()；第二：stackB为空stackA非空，则再次执行上述操作，将stackA的元素pop到stackB。此时如果想进行push操作，扔可以直接push进stackA，因为在队列总stackA中的元素一定是在stackB元素的后面。
Solution
public class MyQueue {
private Stack<Integer> stackA =
new Stack<Integer>();
private Stack<Integer> stackB =
new Stack<Integer>();
/** Initialize your data structure here. */
public MyQueue() {
}
/** Push element x to the back of queue. */
public void push(
int x) {
stackA.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
if(!stackB.isEmpty()){
return stackB.pop();
}
else{
while(!stackA.isEmpty()){
stackB.push(stackA.pop());
}
return stackB.pop();
}
}
/** Get the front element. */
public int peek() {
if(!stackB.isEmpty()){
return stackB.peek();
}
else{
while(!stackA.isEmpty()){
stackB.push(stackA.pop());
}
return stackB.peek();
}
}
/** Returns whether the queue is empty. */
public boolean empty() {
return stackA.isEmpty() && stackB.isEmpty();
}
