leetcode Question: Implement Queue using Stacks

Implement Queue using Stacks

Implement the following operations of a queue using stacks.

• push(x) -- Push element x to the back of queue.
• pop() -- Removes the element from in front of queue.
• peek() -- Get the front element.
• empty() -- Return whether the queue is empty.

Notes:

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

Analysis:

This kind of problem usually requires more than one data structure to implement the other data structure. In this problem, two stacks are enough to implement a queue.

The idea is keep push element into stack 1, then "pop" is called, put all the elements from stack 1 to stack 2. Then pop the top element in stack 2.  If "pop" is called again, not stack 2 is not empty, just pop the top element is enough. If stack 2 is empty, put all the elements in stack 1 to stack 2.  In short, stack 1 is used for "push", stack 2 is used for "pop" and "peek". We do the "move element from stack1 to stack 2" only when stack 2 is empty and "pop" or "peek" is called.


e.g., We call push(1), push(2), push(3), push(4), and push(5), stack 1 is filled all the five elements, then do pop(), since stack 2 is empty, move elements from stack 1 to stack 2, then pop the top element (now is 1) in stack2:

 Then we call push(6), push(7), push(8), push(9), and pop(), pop(), pop(), stack 1 is used for pushing, and stack 2 is used for popping :

Again, we call pop() (now 5 is popped out and no element in stack 2), and a peek() operation is called, stack 2 is empty, so push elements from stack 1 to stack 2, and return the top element as the peek:

Code(C++):

class Queue {

stack<int> st1;
stack<int> st2;

public:
    // Push element x to the back of queue.
    void push(int x) {
        st1.push(x);
    }

    // Removes the element from in front of queue.
    void pop(void) {
        if (!st2.empty()){
            st2.pop();
        }else{
            while (!st1.empty()){
                st2.push(st1.top());
                st1.pop();
            }
            st2.pop();
        }
    }

    // Get the front element.
    int peek(void) {
        if (!st2.empty()){
            return st2.top();
        }else{
            while (!st1.empty()){
                st2.push(st1.top());
                st1.pop();
            }
            return st2.top();
        }
    }

    // Return whether the queue is empty.
    bool empty(void) {
        return (st1.empty() && st2.empty());
    }
};

Code(Python):

class Queue(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.st1 = []
        self.st2 = []
        

    def push(self, x):
        """
        :type x: int
        :rtype: nothing
        """
        self.st1.append(x)
        

    def pop(self):
        """
        :rtype: nothing
        """
        if len(self.st2) == 0:
            while len(self.st1) != 0:
                self.st2.append(self.st1.pop())
        self.st2.pop()
                

    def peek(self):
        """
        :rtype: int
        """    
        if len(self.st2) == 0:
            while len(self.st1) != 0:
                self.st2.append(self.st1.pop())
        return self.st2[-1]
        

    def empty(self):
        """
        :rtype: bool
        """
        return not self.st1 and not self.st2

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