The difference between queue and stack

  • The queue is first-in, first-out

  • The stack is first in and last out

Train of thought

You can implement a stack with two queues, one a queue and one B queue,

  • The first step is to put the pushed value into queue A
  • The second step is to put the pushed values in queue B, and then to eject the values in queue A, in that orderbQueue until queue A clears
  • The second step is to put the pushed values in queue A, and then to eject the values in queue B, in that orderaQueue until queue B clears
  • . The cycle

Step figure

  • Step 1: push
A B
h
  • Step 2: push
A B
h
e
  • Step 3: push
A B
h
e
l
  • Step 4: push
A B
h
e
l
l
  • Step 5 push
A B
h
e
l
l
o
  • Step 6 pop
A B
h
e
l
l
  • Step 7 pop
A B
h
e
l
  • Step 8 pop
A B
h
e
  • Step 9 pop
A B
h
  • Step 10 pop
A B

code

const Queue = require('./queue')

class Stack {
    constructor() {
        this.A = new Queue()
        this.B = new Queue()
    }

    push(val) {
        if(this.A.size()) {
            this.B.enqueue(val)
            while(this.A.size()) {
                this.B.enqueue(this.A.dequeue())
            }
        }else{
            this.A.enqueue(val)
            while(this.B.size()) {
                this.A.enqueue(this.B.dequeue())
            }
        }
    }

    pop() {
        if(this.A.size()) {
            console.log(this.A.peek());
            return this.A.dequeue()
        }else{
            console.log(this.B.peek());
            return this.B.dequeue()
        }
    }
}

const stack = new Stack()
stack.push('h');
stack.push('e');
stack.push('l');
stack.push('l');
stack.push('o');
stack.pop();     //o
stack.pop();     //l
stack.pop();     //l
stack.pop();     //e
stack.pop();     //h
Copy the code

conclusion

Define two stacks, each time the stack is pushed, the data is first put into the empty queue, and then the data of the other queue is put into the empty queue, and the data of the stack is popped out of the stack