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)?

Log in to reply
 

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