Hello, everyone, I am the beaten Amumu, love algorithm front-end fish old. Recently, I will frequently share with you my thoughts and experiences in the process of brush algorithm. If you also want to improve the forced case of fish old, welcome to pay attention to me, learn together.

The title

Interview question 03.04. Turn stacks into queues

Implement a MyQueue class that uses two stacks to implement a queue.

Example:

MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // Return 1 queue.pop(); // Return 1 queue.empty(); / / returns falseCopy the code

Description:

  • You can only use standard stack operations — that is, onlypush to top.peek/pop from top.size 和 is emptyThe operation is legal.
  • Your language may not support stacks. You can use a list or a deque to simulate a stack, as long as it’s standard stack operations.
  • Assume that all operations are valid (for example, an empty queue does not call pop or PEEK).

Train of thought

  1. Now we have two arrays, and we can only use one array at a timepushandpopOperation, how to reach firstpushThe elements that go in canpopCome out;
  2. So we can take two buckets of things, one by one into the first bucket, and before we take it out, we can take the first bucket of things one by one to the second bucket, and then the second bucket can be taken out in turn.

implementation

var MyQueue = function() {
    / / into the stack
    this.stackIn = [];
    / / stay out of the stack
    this.stackOut = [];
};

// Put something in
MyQueue.prototype.push = function(x) {
    this.stackIn.push(x);
};

// Take out the element you put in first
MyQueue.prototype.pop = function() {
    if (this.stackOut.length === 0) {
        // Pour them out one by one and put them in the ununloaded stack list
        while (this.stackIn.length) {
            this.stackOut.push(this.stackIn.pop()); }}return this.stackOut.pop();
};

// Get the element put in first without taking it out
MyQueue.prototype.peek = function() {
    if (this.stackOut.length === 0) {
        // Pour them out one by one and put them in the ununloaded stack list
        while (this.stackIn.length) {
            this.stackOut.push(this.stackIn.pop()); }}return this.stackOut[this.stackOut.length - 1];
};

// Is there anything in your pocket
MyQueue.prototype.empty = function() {
    return this.stackIn.length === 0 && this.stackOut.length === 0;
};

/** * Your MyQueue object will be instantiated and called as such: * var obj = new MyQueue() * obj.push(x) * var param_2 = obj.pop() * var param_3 = obj.peek() * var param_4 = obj.empty() * /
Copy the code

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.