225. Implement Stack using Queues

Question

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.

Example:

MyStack stack = new MyStack();

stack.push(1);
stack.push(2);
stack.top();   // returns 2
stack.pop();   // returns 2
stack.empty(); // returns false

Thinking:

Method 1：通过linkedList实现

class MyStack {
    LinkedList<Integer> list;
    int count = 0;
    /** Initialize your data structure here. */
    public MyStack() {
        list = new LinkedList<>();
    }

    /** Push element x onto stack. */
    public void push(int x) {
        list.add(x);
        count++;
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        count --;
        return list.pollLast();
    }

    /** Get the top element. */
    public int top() {
        return list.get(count - 1);
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return count == 0;
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

二刷

Use LinkedList to realize stack.

class MyStack {
 LinkedList<Integer> stack = null;
 int size = 0;
 /** Initialize your data structure here. */
 public MyStack() {
     stack = new LinkedList<>();
 }
 /** Push element x onto stack. */
 public void push(int x) {
     this.stack.addFirst(x);
     this.size++;
 }
 /** Removes the element on top of the stack and returns that element. */
 public int pop() {
     this.size --;
     return this.stack.pollFirst();
 }
 /** Get the top element. */
 public int top() {
     return this.stack.get(0);
 }  
 /** Returns whether the stack is empty. */
 public boolean empty() {
     return this.size == 0;
 }
}
/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */