225. Implement stack with queue

Title Link: 225. Implement stack with queue (simple)

Title Description

Please use only two queues to implement a last in first out (LIFO) stack, and support all four operations of the ordinary stack (push, top, pop and empty).

Implement MyStack class:

• void push(int x) pushes element X to the top of the stack.

• int pop() removes and returns the top of stack element.

• int top() returns the stack top element.

• boolean empty() returns true if the stack is empty; Otherwise, false is returned.

be careful:

• You can only use the basic operations of the queue -- that is, push to back, peek/pop from front, size and is empty.

• Your language may not support queues. You can use list or deque to simulate a queue, as long as it is a standard queue operation.

Example:

Input:
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output:
[null, null, null, 2, 2, false]
​
Explanation:
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); //  Return 2
myStack.pop(); //  Return 2
myStack.empty(); //  Return False

Tips:

• 1 <= x <= 9

• Call push, pop, top, and empty up to 100 times

• Ensure that the stack is not empty every time pop and top are called

Problem solution

Idea: according to the meaning of the topic, use a common queue and a queue for backing up data (in fact, using a queue for this topic is enough).

Two queues are used: for push(), just push the elements into the normal queue one by one; For pop(), first pop up the first n-1 elements in the ordinary queue (assuming there are n elements in the ordinary queue) and push them into the backup queue, and then pop up the last element; For top(), just return the end of line element; For empty(), you only need to judge whether the normal queue is empty.

Using a queue: push(), top(), empty() is the same as "using two queues"; for pop(), first pop up the first n-1 elements in the queue (assuming there are n elements in the queue) in order, push them from the end of the queue, and then pop up the last element.

Code (C + +)

//Use two queues
class MyStack {
public:
    deque<int> deq1;//Normal queue
    deque<int> deq2;//Backup queue
​
    MyStack() {
​
    }
​
    void push(int x) {
        deq1.push_back(x);
    }
​
    int pop() {
        //If queue 1 is not empty, the first in the queue is deleted n-1 Elements(Suppose there are n element)Push queue 2 and pop the last element
        while (deq1.size() - 1 > 0) {
            deq2.push_back(deq1.front());
            deq1.pop_front();
        }
        int result = deq1.front();
        deq1.pop_front();
        //Push all the elements in queue 2 into queue 1
        while (deq2.size() > 0) {
            deq1.push_back(deq2.front());
            deq2.pop_front();
        }
        return result;
    }
​
    int top() {
        return deq1.back();
    }
​
    bool empty() {
        if (deq1.empty()) return true;
        else return false;
    }
};

analysis:

• Time complexity: push(): O(1); pop(): O(N); top(): O(1); empty(): O(1); N is the number of elements in the queue

• Spatial complexity: O(N), two queues are required.

//Use a queue
class MyStack {
public:
    deque<int> deq;
​
    MyStack() {
​
    }
​
    void push (int x) {
        deq.push_back(x);
    }
​
    int pop() {
        int size = deq.size();
        while (size - 1 > 0) {
            deq.push_back(deq.front());
            deq.pop_front();
            size--;
        }
        int result = deq.front();
        deq.pop_front();
        return result;
    }
​
    int top() {
        return deq.back();
    }
​
    bool empty() {
        return deq.empty();
    }
​
};

analysis:

• Time complexity: push(): O(1); pop(): O(N); top(): O(1); empty(): O(1); N is the number of elements in the queue

• Spatial complexity: O(N), a queue is required.