Offer 09. (Implement queue with two stacks)

Since we need to use two stacks, we use one stack to record the end of the queue, and one stack to record the head of the queue.

var CQueue = function() {
  this.tail_stack=[]  // This is the stack that records the end of the queue
  this.head_stack=[]  // This is the stack that records the queue header
};
/ * * *@param {number} value
 * @return {void}* /
CQueue.prototype.appendTail = function(value) {
   this.tail_stack.push(value)  Append_stack should be operated on when appendTail is called
};

/ * * *@return {number}* /
CQueue.prototype.deleteHead = function() {

   // The difficulty lies in the operation function
   / / steps:
   // 1. If head_stack is empty and tail_stack is empty, the stack is empty and -1 is output
   // 2. If head_stack is empty, but tail_stack is not empty, so we need to find the queue head, and then output
   Tail_stack is inverted into head_stack until tail_stack is empty.
   // The stack of head_stack is queued from top to bottom
   // 3. If head_stack is not empty, return the top element of head_stack
   
   
   
    if(!this.head_stack.length){
        if(!this.tail_stack.length){
            return -1
        }
        else{
            while(this.tail_stack.length){
                this.head_stack.push(this.tail_stack.pop())
            }
        }
    }
    return this.head_stack.pop()
};

/** * Your CQueue object will be instantiated and called as such: * var obj = new CQueue() * obj.appendTail(value) * var param_2 = obj.deleteHead() */
Copy the code