My code:
class MyQueue {
Stack<Integer> st = new Stack<Integer>();
// Push element x to the back of queue.
public void push(int x) {
Stack<Integer> temp = new Stack<Integer>();
while (!st.isEmpty()) {
temp.push(st.pop());
}
st.push(x);
while (!temp.isEmpty()) {
st.push(temp.pop());
}
}
// Removes the element from in front of queue.
public void pop() {
st.pop();
}
// Get the front element.
public int peek() {
return st.peek();
}
// Return whether the queue is empty.
public boolean empty() {
return st.isEmpty();
}
}
我采用的还是最简单的做法。所以，
push O(n)
pop O(1)
然后看了下答案，发现有更好的方法。
My code:
class MyQueue {
Stack<Integer> st1 = new Stack<Integer>();
Stack<Integer> st2 = new Stack<Integer>();
int front = 0;
// Push element x to the back of queue.
public void push(int x) {
if (st1.isEmpty()) {
front = x;
}
st1.push(x);
}
// Removes the element from in front of queue.
public void pop() {
if (st2.isEmpty()) {
while (!st1.isEmpty()) {
st2.push(st1.pop());
}
}
st2.pop();
}
// Get the front element.
public int peek() {
if (!st2.isEmpty()) {
return st2.peek();
}
return front;
}
// Return whether the queue is empty.
public boolean empty() {
return st1.isEmpty() && st2.isEmpty();
}
}
push O(1)
pop amortized time O(1), worst O(n)
就是维护两个栈，每次要pop了，就把第一个栈里面的元素全部pop到第二个栈上，正好reverse下，然后以后pop都先从这第二个栈pop，没了之后，再去栈1 拿元素进来。
reference:
https://leetcode.com/articles/implement-queue-using-stacks/
Anyway, Good luck, Richardo! -- 09/11/2016
