Topic describes

Their thinking

  1. What are the properties of unpacking stacks? A stack is like a stack of books. When you put a new book on top of the previous one, when you remove a book, you have to take the top book. There is no other way to manipulate the book. If you want to take the third book from the top down, you have to pick up both of the top books before you can take the third book. The term is First In Last Out.

  2. What are the properties of unqueuing? Queue is better understood, it’s like queuing, it’s like queuing to get into the subway, the first person in line is always first. The term is First In First Out.

  3. How to implement queues with two stacks? Since the characteristics of queue is first in, first out, so when entering, directly use a stack (called stack 1) can be pressed, when out of queue, so that the stack can realize the first to enter can be first out. In this case, we use another stack (called stack 2), and we add all the elements of stack 1 to stack 2, and then the elements of stack 2 are removed from the stack to achieve first-in, first-out queue.

    • If stack 2 is not empty, the element on stack 2 is pushed off the stack
    • If stack 2 is empty and stack 1 is not empty, we move all the elements from stack 1 to stack 2, and then we move all the elements from stack 2. Otherwise return -1 (there are no elements in either stack)

code

JS implementation

var cQueue = function(){
    this.stack1 = [];
    this.stack2 = [];
}

cQueue.prototype.appendTail = function(value){
    this.stack1.push(value);
}

cQueue.prototype.deleteHead = function(){
    if(this.stack2.length){
        return this.stack2.pop();
    }else{
        if(this.stack1.length){
            while(stack1.length){
                this.stack2.push(this.stack1.pop());
            }
            return this.stack2.pop();
        }else{
            return -1; }}}Copy the code

Conclusion:

Ideas, maintenance of two stacks, respectively to achieve the queue queue and queue.

Time complexity: O(n) Space complexity: O(n)

Difficulty: easy