The title

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: [null.null.3, -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

Tip:

1 <= values <= 10000 Calls to appendTail and deleteHead are performed at most 10000 times

Answer key

In fact, the implementation idea is very simple, is as described in the problem, the use of two stacks to achieve the queue

Train of thought

Let’s start with the initial code.

var CQueue = function() {};/ * * *@param {number} value
 * @return {void}* /
CQueue.prototype.appendTail = function(value) {};/ * * *@return {number}* /
CQueue.prototype.deleteHead = function() {};/** * 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

The initial code gives you two prototype functions to operate on, so you need to declare two numbers in the CQueue.

this.stack1=[];
this.stack2=[];
Copy the code

Then there is the logic of joining and leaving the team.

  • Enqueue: Just push the data into Stack1.

  • Queue out: The whole idea is to pop all the data in array 1 and push it into array 2. Pop if there is data in array 2, otherwise push from array 1, return -1 if both 1 and 2 are empty.

      1. Check stack2, if there is data, pop, return;
      1. If 1 fails, loop out all the data in Stack1 and push it into Stack2;
      1. If there is no return in front, the return stack2 pop value is required, which defaults to -1.

code

The complete code

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

/ * * *@param {number} value
 * @return {void}* /
CQueue.prototype.appendTail = function(value) {
    this.stack1.push(value);
};

/ * * *@return {number}* /
CQueue.prototype.deleteHead = function() {
    if(this.stack2.length) return this.stack2.pop();
    while(this.stack1.length){
        this.stack2.push(this.stack1.pop())
    }
    return this.stack2.pop() || -1;
};

/** * 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