[225. Stack implementation with queues]

“This is my 39th day of participating in the First Challenge 2022. For more details: First Challenge 2022.”

Topic describes

You can implement a last in, first out (LIFO) stack with just two queues and support all four operations of a normal 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 element of the stack. Int top() returns the top element of the stack. Boolean empty() Returns true if the stack is empty; Otherwise, return false.

Note:

  • You can only use the basic operations of queues — namely push to Back, peek/ Pop from Front, size, and is empty.
  • Your language may not support queues. You can use a list or a deque to simulate a queue, as long as it’s standard queue operations.

The sample

Example 1:

Input: [" MyStack ", "push" and "push", "top", "pop", "empty"] [[], [1], [2], [], [], []] output: [null, null, null, 2, 2, false] MyStack MyStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // Return 2 mystack.pop (); // Return 2 mystack.empty (); / / returns FalseCopy the code

Tip:

  • 1 <= x <= 9
  • Push, POP, peek, and Empty are called up to 100 times
    • Each callpop 和 topMake sure the stack is not empty

Advancements: Can you implement a stack with just one queue?

Train of thought

This is a test of the basic data structure stack and queue, does not involve a specific algorithm. The stack is characterized by fifo and the queue is characterized by fifO. The difference is that the output order is different. In order to achieve the output order, similar to yesterday, you need to use two queues, called queue 1 and queue 2. Queue 1 does the operation and queue 2 does the temporary storage of elements. For push operation, push directly to input queue 1, POP operation and PEEK operation, all data of queue (except the last one) need to be transferred to queue 2, meeting the requirements of stack. After transfer and output, data should be put back to queue 1. Empty operation needs to check both queues at the same time. See the code for other details.

The progression tells us that we have some space to optimize, but we don’t have to open two queues, just one queue, and notice that we just need to record the number of data, move the data from the head to the tail, and leave the last data standing, and we can do that.

Code implementation

Two queues:

class MyStack {
    private:
    queue<int> queue1;
    queue<int> queue2;
public:
    /** Initialize your data structure here. */
    MyStack() {}/** Push element x onto stack. */
    void push(int x) {
      queue1.push(x);
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop(a) {
     int time=queue1.size(a)- 1;
     while(time--){   // Save to queue 2
         queue2.push(queue1.front());
         queue1.pop(a); }int resule=queue1.front(a); queue1.pop(a);/ / record
     queue1=queue2;     
     while(! queue2.empty())  / / reduction
     queue2.pop(a);return resule;
    }
    
    /** Get the top element. */
    int top(a) {
      return queue1.back(a); }/** Returns whether the stack is empty. */
    bool empty(a) {
return queue1.empty();
    }
};

/** * Your MyStack object will be instantiated and called as such: * MyStack* obj = new MyStack(); * obj->push(x); * int param_2 = obj->pop(); * int param_3 = obj->top(); * bool param_4 = obj->empty(); * /
Copy the code

conclusion

The stack and queue are two basic data structures.