In this Leetcode Implement Queue using Stacks problem solution Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

  1. void push(int x) Pushes element x to the back of the queue.
  2. int pop() Removes the element from the front of the queue and returns it.
  3. int peek() Returns the element at the front of the queue.
  4. boolean empty() Returns true if the queue is empty, false otherwise.

Leetcode Implement Queue using Stacks problem solution


Problem solution in Python.

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self._stack1 = []
        self._stack2 = []
        self._length = 0

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self._stack1.append(x)
        self._length += 1
        return None

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        if self._stack2:
            self._length -= 1
            return self._stack2.pop()
        else:
            while self._stack1:
                self._stack2.append(self._stack1.pop())
            if self._stack2:
                self._length -= 1
                return self._stack2.pop()
            else:
                raise Exception()

    def peek(self) -> int:
        """
        Get the front element.
        """
        if self._stack2:
            return self._stack2[-1]
        else:
            while self._stack1:
                self._stack2.append(self._stack1.pop())
            if self._stack2:
                return self._stack2[-1]
            else:
                raise Exception()

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return not bool(self._length)



Problem solution in Java.

class MyQueue {

    Stack<Integer> s1;
    Stack<Integer> s2;
    /** Initialize your data structure here. */
    public MyQueue() {
        this.s1 = new Stack<>();
        this.s2 = new Stack<>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        s1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if(s2.isEmpty()){
            while(!s1.isEmpty()){
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
    
    /** Get the front element. */
    public int peek() {
        if(s2.isEmpty()){
            while(!s1.isEmpty()){
                s2.push(s1.pop());
            }
        }
        return s2.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        if(s1.isEmpty() && s2.isEmpty())
            return true;
        return false;
    }
}


Problem solution in C++.

class MyQueue {
    
    std::stack<int> m_normal;
    std::stack<int> m_reversed;
    
public:
    /** Initialize your data structure here. */
    MyQueue() {
        
    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        
        m_normal.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        
        if(m_reversed.empty())
        {
            while(!m_normal.empty())
            {
                m_reversed.push(m_normal.top());
                m_normal.pop();
            }
        }
        
        int top = m_reversed.top();
        m_reversed.pop();
            
        return top;
    }
    
    /** Get the front element. */
    int peek() {
        
        if(m_reversed.empty())
        {
            while(!m_normal.empty())
            {
                m_reversed.push(m_normal.top());
                m_normal.pop();
            }
        }
        
        return m_reversed.top();
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        
        return m_normal.empty() and m_reversed.empty();
    }
};


Problem solution in C.

typedef struct {
    int *arr;
    int top;
} Queue;

/* Create a queue */
void queueCreate(Queue *queue, int maxSize) {
    queue->arr=(int*)malloc(maxSize*sizeof(int));
    queue->top=0;
}

/* Push element x to the back of queue */
void queuePush(Queue *queue, int element) {
    int top=queue->top++;
    int i;
    if(top==0){
        queue->arr[top]=element;
    }
    else{
        for(i=top-1;i>=0;i--) queue->arr[i+1]=queue->arr[i];
        queue->arr[0]=element;
    }
}

/* Removes the element from front of queue */
void queuePop(Queue *queue) {
    queue->top--;
}

/* Get the front element */
int queuePeek(Queue *queue) {
    int top=queue->top;
    return queue->arr[top-1];
}

/* Return whether the queue is empty */
bool queueEmpty(Queue *queue) {
    return !queue->top;
}

/* Destroy the queue */
void queueDestroy(Queue *queue) {
    queue->top=0;
}