Leetcode 225. Implement Stack using Queues

算法 Java Leetcode

Implement basic operations of a stack using queues.

Question

Implement the following operations of a stack using queues.

• push(x) —— Push element x onto stack.
• pop() —— Remove the element on top of the stack.
• top() —— Get the top element.
• empty() —— Return whether the stack is empty.

See it on Leetcode

Notes

1. You must use only standard operations of a queue —— which means only push to back, peek/pop from front, size and is empty operations are valid.
2. Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque(double-ended que), as long as you use only standard operations of a queue.
3. You may assume that all operations are valid(eg. no pop or top operations will be called on an empty stack).

Solution

• java
• cpp

class MyStack {  
    private Queue<Integer> q1 = new LinkedList<Integer>();
    private Queue<Integer> q2 = new LinkedList<Integer>();
    
    // Push element x onto stack.
    public void push(int x) {
        if (q1.isEmpty()) {
            q1.offer(x);
            while (!q2.isEmpty()) q1.offer(q2.poll());
        } else {
            q2.offer(x);
            while (!q1.isEmpty()) q2.offer(q1.poll());
        }
    }

    // Remove the element on top of the stack.
    public void pop() {
        if (!q1.isEmpty()) q1.poll();
        if (!q2.isEmpty()) q2.poll();
    }

    // Get the top element.
    public int top() {
        if (!q1.isEmpty()) {
            return q1.peek();
        } else {
            return q2.peek();
        }
    }

    // Return whether the stack is empty.
    public boolean empty() {
        return q1.isEmpty() && q2.isEmpty();
    } 
}

class Stack {
private:
    queue<int> queue1;  
    queue<int> queue2;
      
public:  
    // Push element x onto stack.
    void push(int x) {  
        if (queue1.empty())  
        {  
            queue1.push(x);  
            while(!queue2.empty()) {  
                int tmp = queue2.front();  
                queue2.pop();  
                queue1.push(tmp);  
            }  
        } else {  
            queue2.push(x);  
            while(!queue1.empty()) {  
                int tmp = queue1.front();  
                queue1.pop();  
                queue2.push(tmp);  
            }  
        }  
    }  
  
    // Removes the element on top of the stack.  
    void pop() {  
        if (!queue1.empty())  
            queue1.pop();  
        if (!queue2.empty())  
            queue2.pop();  
    }  
  
    // Get the top element.  
    int top() {  
        if (!queue1.empty())  
            return queue1.front();  
        if (!queue2.empty())  
            return queue2.front();
        return 0;
    }  
  
    // Return whether the stack is empty.  
    bool empty() {  
        return queue1.empty() && queue2.empty();  
    }  
};

Editorial Solution

• java
• cpp

class MyStack {  
    private LinkedList<Integer> q1 = new LinkedList<>();

    // Push element x onto stack.
    public void push(int x) {
        q1.add(x);
        int size = q1.size();
        while (size > 1) {
            q1.add(q1.remove());
            size--;
        }
    }

    // Remove the element on top of the stack.
    public void pop() {
        q1.remove();
    }

    // Get the top element.
    public int top() {
        return q1.peek();
    }

    // Return whether the stack is empty.
    public boolean empty() {
        return q1.isEmpty();
    }
}

class Stack {  
private:
    queue<int> q1;
    
public:  
    // Push element x onto stack.  
    void push(int x) {
        q1.push(x);
        int size = q1.size();
        int pushTemp;
        while (size > 1) {
            pushTemp = q1.front();
            q1.pop();
            q1.push(pushTemp);
            size--;
        }
    }  
  
    // Removes the element on top of the stack.  
    void pop() {  
        q1.pop();
    }  
  
    // Get the top element.  
    int top() {  
        return q1.front();
    }  
  
    // Return whether the stack is empty.  
    bool empty() {  
        return q1.empty();  
    }  
};