题目:
Implement the following operations of a stack using queues.
- push(x) — Push element x onto stack.
- pop() — Removes the element on top of the stack.
- top() — Get the top element.
- empty() — Return whether the stack is empty.
分析:
使用队列实现栈的数据结构。
1个队列。入栈时,先将要入栈的元素添加到队尾,然后将除了这个元素之外的所有元素依次出队,再入队。这样可以保证新入栈的元素总是在队列的最前面。
出栈时,直接出队即可。
代码:
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
import java.util.LinkedList; import java.util.Queue; class MyStack { private Queue<Integer> queue; public MyStack(){ queue = new LinkedList<Integer>(); } // Push element x onto stack. public void push(int x) { queue.add(x); for(int i = 0; i < queue.size() - 1; i++){ queue.add(queue.poll()); } } // Removes the element on top of the stack. public void pop() { queue.poll(); } // Get the top element. public int top() { return queue.peek(); } // Return whether the stack is empty. public boolean empty() { return queue.isEmpty(); } } |