LeetCode Implement Stack using Queues

Implement the following operations of a stack using queues.

Notes:

Update (2015-06-11):

The class name of theJavafunction had been updated toMyStackinstead of Stack.

思路分析：这题和LeetCode Implement Queue using Stacks类似，思路也类似，用两个队列来模拟一个栈。具体做法是，入栈只需要放入Q1队列尾部。出栈时，把Q1除了最后一个元素之外的所有元素出队列，并且压入Q2队列尾部，然后从Q1中取出最后那个元素。注意要保证Q2为空，它是一个辅助队列，所以我们交换Q1和Q2。top和pop方法类似，除了取出Q1中最后那个元素后，再返回它前还要压入到Q2中去，保证这个元素不被丢失，因为我们只想看栈顶元素，，并不想真正将它出栈。

AC Code

class MyStack {//Queue LinkedList<Integer> q1 = new LinkedList<Integer>(); LinkedList<Integer> q2 = new LinkedList<Integer>();// Push element x onto stack.public void push(int x) {q1.add(x);}// Removes the element on top of the stack.public void pop() {//peek(); poll();while(q1.size() > 1){q2.add(q1.poll());}q1.poll();//switchLinkedList<Integer> tem = q1;q1 = q2;q2 = tem;}// Get the top element.public int top() {//peek(); poll();while(q1.size() > 1){q2.add(q1.poll());}int res = q1.peek();q2.add(q1.poll());//switchLinkedList<Integer> tem = q1;q1 = q2;q2 = tem;return res;}// Return whether the stack is empty.public boolean empty() {return q1.isEmpty();}}

大理的洱海形如人耳，风平浪静时，

相关文章：

你感兴趣的文章：

标签云：