Implement Stack using Queues


  • 0

    Click here to see the full article post


  • 0
    M

    The third approach is really good.


  • 1

    We can also make a one-queue solution with push ~ O(1) and pop ~ O(n)

    // Push element x onto stack.
    void push(int x) {
    _top = x;
    q.push(x);
    }

    // Removes the element on top of the stack.
    void pop() {
        for (int i = q.size() - 1; i--; ) _top = q.front(), q.push(_top), q.pop();
        q.pop();
    }

  • 0

    The idea of the 3rd approach means rotating a queue, which has been included in some basic collection libraries.


  • 0
    T

    Using java dequeue to solve this!
    public class MyStack {

    Deque<Integer> queue;
    
    /** Initialize your data structure here. */
    public MyStack() {
    	queue = new LinkedList<Integer>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
    	queue.offerFirst(x);
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
    	if (!queue.isEmpty()) {
    		return queue.pollFirst();
    	}
    	return -1;
    }
    
    /** Get the top element. */
    public int top() {
    	if (!queue.isEmpty()) {
    		return queue.peekFirst();
    	}
    	return -1;
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
    	return queue.isEmpty();
    }
    

    }


  • 0
    A

    Didnt understand the second approach.
    If we do Q1.remove() it will pop 1 instead of 2. Please let me know if I am wrong


  • 0
    S

    Actually the Approach #3 is the samilar with Approach #2 as just replacing the 2 Queues with the only one common shared Queue1 like a Ring. So the Approach #1 can also replacing the 2 Queues with the only one common shared Queue1 like a Ring.


  • 0
    S

    @sirykd Actually the Approach #3 is the samilar with Approach #2 as just replacing the 2 Queues with the only one common shared Queue1 like a Ring. So the Approach #1 can also replacing the 2 Queues with the only one common shared Queue1 like a Ring as your Approach.


  • 0
    A

    Maintaining top separately is not needed for Approach #2. q1.peek() can be returned as top.


  • 0
    Y
    1. Why the space complexity of Approach #2,#3 push method are O(1)??? I thought it O(N) because we need additional memory to store the elements in queue.
    2. How to determine whether it is O(1) or O(N)?

  • 0
    S

    In the Approach #3 here is a wrong interface for pop(), the correct one should be:

        // Removes the element on top of the stack.
        public int pop() {
            return q1.remove();
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.