Implement the following operations of a stack using queues.
使用队列实现下面的栈操作:
这道题和232. Implement Queue using Stacks很像,跟他是相反的要求。
其实用队列实现栈无非就是一个出的顺序不一样,栈是后进先出,队列是先进先出,因此要么改变队列出的做法,全部出完直到最后一个才是作为栈需要出的;要么改入队的做法,每次入的时候都全部取出来一遍,将新元素入在队首去,这样出的时候就是第一个出的了。
因为题目的代码要求有两个取元素操作,一个添加元素操作,所以我采用了第二种做法,改变入队方式,具体实现还是很简单的。
class MyStack {
Queue<Integer> q;
public MyStack(){
q = new LinkedList<Integer>();
//temp = new LinkedList<Integer>();
}
// Push element x onto stack.
public void push(int x) {
Queue<Integer> temp = new LinkedList<Integer>();
while (q.peek() != null) {
temp.add(q.poll());
}
q.add(x);
while (temp.peek() != null) {
q.add(temp.poll());
}
}
// Removes the element on top of the stack.
public void pop() {
q.remove();
}
// Get the top element.
public int top() {
return q.peek();
}
// Return whether the stack is empty.
public boolean empty() {
return q.peek() == null;
}
}