Offer 09. Implement queues with two stacks

Implement a queue with two stacks. Implement appendTail and deleteHead to insert an integer at the end of the queue and delete an integer at the head of the queue. (If there are no elements in the queue, the deleteHead operation returns -1)

Example 1:

Input: [" CQueue appendTail ", ""," deleteHead ", "deleteHead"] [[], [3], [], []] output: [3, null, null, 1]Copy the code

Example 2:

Input: [" CQueue deleteHead ", ""," appendTail ", "appendTail", "deleteHead", "deleteHead"] [[], [], [5], [2], [], []] output: [null, 1, null, null, 5, 2]Copy the code

Note: 1 <= values <= 10000 calls at most appendTail and deleteHead

Stack is first in, first out, queue is first in, first out. When an integer is inserted to the end of a queue, it is pushed. When the integer in the queue head is deleted, the data on stack 1 is put into stack 2 in sequence by using the feature of stack first in and then out. In this case, deleting the top element of stack is to delete the integer in the queue head.

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

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

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