This is the first day of my participation in Gwen Challenge

Topic describes

You can implement a last in, first out (LIFO) stack with just two queues and support all four operations (push, top, POP, and Empty) of normal queues.

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.

Pay attention to

  • 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.

Example:

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
  • Most call100 次 push,pop,top 和 empty
  • Each callpop 和 topMake sure the stack is not empty

Advanced:

Can you implement a stack with O(1) amortized time for each operation? In other words, the total time complexity of performing n operations is O(n), even though one of them may take longer than the others. You can use more than two queues.

Thought analysis

Using queue to implement stack, involves queue and stack these two data structures, queue is first in first out, one entrance, one exit, and stack is first in last out, only one entrance/exit. With queue emulation stack, you can simulate with two queues and one queue respectively.

Each time val is added to queue A, since both A and B are empty at the beginning, val is added to queue A and is switched between queue B and queue A. Next, val is added to queue A when queue A is empty. Queue B already has values (because it was swapped last time), add values from queue B to queue A, and then queue B is stored in the same order as the normal stack, and queue A and queue B are swapped each time. The other operation is to fetch from the A queue.

When we look at the solution of a queue, the key is still the push method. Every time we push, we first get the number of values in the queue, and then put the values in the queue. The for loop will loop n times to put the values out of the queue and then put them at the end of the queue.

The code shown

Solution a: push operation time complexity is O (n) (n)} {O O (n), other operation complexity is O (1) (1)} {O O (1), space complexity is O (n) (n)} {O O (n).

class MyStack {
  
    Queue<Integer> queueA = null;
    Queue<Integer> queueB = null;
    /** Initialize your data structure here. */
    public MyStack(a) {
        queueA = new LinkedList<>();
        queueB = new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queueA.offer(x);
        while(! queueB.isEmpty()){ queueA.offer(queueB.poll()); } Queue<Integer> temp = queueA; queueA = queueB; queueB = temp; }/** Removes the element on top of the stack and returns that element. */
    public int pop(a) {
        return queueB.poll();
    }
    
    /** Get the top element. */
    public int top(a) {
       return queueB.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty(a) {
        returnqueueB.isEmpty(); }}Copy the code

Method 2: push operation time complexity is O (n) (n)} {O O (n), and other operation complexity is O (1) (1)} {O O (1), space complexity is O (n) (n)} {O O (n).

class MyStack {
    Queue<Integer> queue;

    /** Initialize your data structure here. */
    public MyStack(a) {
        queue = new LinkedList<Integer>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        int n = queue.size();
        queue.offer(x);
        for (int i = 0; i < n; i++) { queue.offer(queue.poll()); }}/** Removes the element on top of the stack and returns that element. */
    public int pop(a) {
        return queue.poll();
    }
    
    /** Get the top element. */
    public int top(a) {
        return queue.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty(a) {
        returnqueue.isEmpty(); }}Copy the code

conclusion

Corresponding to the topic of this simulation class, the key is to master the characteristics of data structure, and this simple simulation stack, two queues and a queue can be solved, a queue processing logic is also very clear.