leetcode Question: Implement Stack using Queues

Implement Stack using Queues

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.

Notes:

• 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.
• Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
• You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

Analysis:

This is a classic question related to queue and stack. Let's review the stack and queue data structure, it is very easy to remember the properties of those two data structures that:

1. Queue:  FIFO (First In First Out)
2. Stack: LIFO (Last In First Out)

This question asks to use queue to simulate stack. There are several ways to do so, here I just provide one of the solutions that utilizing two queues. The basic idea is to swap the two queues every time when popping the element from stack. Queue 1 stores the stack top element, Queue 2 stores the previous elements. Every time when pushing one element into stack, push queue 1's top in queue 2, and push the new element in queue 1. Every time when popping the top element in stack, push the queue 1's top (only one element in this queue). Then push n-1 elements from queue 2 to queue 1, where n is the total number of elements in queue 2. In other words, we left one element in queue 2 (this is the top element in the current stack), and push all the other elements into the empty queue (queue 1). Finally we swap queue 1 and queue 2. The stack is empty iff queue 1 and queue 2 are all empty. The top element is always the only element in queue 1.

It is much clear and easier to understand the whole process by reading the code directly. See below for the code in C++ and python.

Code(C++):

class Stack {
private: 
queue<int> q1;
queue<int> q2;

public:
    Stack() {
        queue<int> q1;
        queue<int> q2;
    }
    
    // Push element x onto stack.
    void push(int x) {
        q1.push(x);
        if (q1.size()==1){return;}
        int tmp = q1.front();
        q1.pop();
        q2.push(tmp);
    }

    // Removes the element on top of the stack.
    void pop() {
        q1.pop();
        if (q2.size()==0){return;}
        for (int i=0;i<q2.size()-1; i++){
            q1.push(q2.front());
            q2.pop();
        }
        queue<int> tmp; 
        tmp = q1;
        q1 = q2;
        q2 = tmp;
    }

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

    // Return whether the stack is empty.
    bool empty() {
        if (q1.size()==0 && q2.size()==0){
            return true;
        }else{
            return false;
        }
    }
};

Code(Python):

class Stack(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.q1 = []
        self.q2 = []
        

    def push(self, x):
        """
        :type x: int
        :rtype: nothing
        """
        self.q1.append(x)
        if len(self.q1) == 1:
            return
        else:
            self.q2.append(self.q1.pop(0))
        

    def pop(self):
        """
        :rtype: nothing
        """
        self.q1.pop(0)
        for i in range(len(self.q2)-1):
            self.q1.append(self.q2.pop(0))
        self.q1, self.q2 =  self.q2, self.q1
        

    def top(self):
        """
        :rtype: int
        """
        return self.q1[0]

    def empty(self):
        """
        :rtype: bool
        """
        if len(self.q1)==0 and len(self.q2)==0:
            return True
        else:
            return False