首页 > itarticle > 2. queue using two stacks

2. queue using two stacks

admin 11月 13, 2020 0

[Problem]

Create a queue using two stacks.

[Algorithms]

Create a stack.
Create a queue with two instances of Stack( ).
For dequeue of Queue, Move elements from stack1(inbox) to stack2(outbox), and return the highest element in outbox.

[Solution]

// STACK
function Stack() {
  var items = [];

  this.push = function() {
    items.push.apply(items, arguments);
  };
  this.pop = function() {
      return items.pop.apply(items, arguments);
  };
  this.size = function() {
      return items.length;
  };
  this.peek = function() {
      return items;
  };
  this.isEmpty = function() {
    return items.length === 0;
};
}

// STACK TESTS
var stack = new Stack();
stack.push(1, 2, 3, 4, 5);
console.log(stack.peek()); // [ 1, 2, 3, 4, 5 ]
stack.pop();
console.log(stack.peek()); // [ 1, 2, 3, 4 ]


// QUEUE
function Queue() {
  var inbox = new Stack();
  var outbox = new Stack();

  this.eneque = function() {
      inbox.push.apply(inbox, arguments);
  };
  this.dequeue = function() {
      if (outbox.size() === 0) {
          while (inbox.size())
              outbox.push(inbox.pop());
      }
      return outbox.pop();
  };
  this.size = function(){
    return inbox.size() + outbox.size();
  };
  this.peek = function() {
      return outbox.peek();
  };
  this.isEmpty = function() {
    return inbox.length + outbox.length === 0;
  };
  this.front = function() {
    if (outbox.size() === 0) {
      while (inbox.size())
        outbox.push(inbox.pop());
    }
    return outbox.peek()[0];
  };
}

// QUEUE TESTS
var queue = new Queue();
console.log(queue.size()); // 0
queue.eneque(10, 20, 30, 40, 50, 60);
console.log(queue.size()); // 6
console.log(queue.peek()); // [] Not move to outbox yet
console.log(queue.dequeue()); // 10
console.log(queue.dequeue()); // 20
console.log(queue.peek()); // [ 60, 50, 40, 30 ]
console.log(queue.front()); // 60
console.log(queue.size()); // 4
console.log(queue.dequeue()); // 30
console.log(queue.dequeue()); // 40
console.log(queue.peek()); // [ 60, 50 ]

[What I learned]

Use the value of array.pop() as parameter of other array.push()

this.dequeue = function() {
    if (outbox.size() === 0) {
        while (inbox.size())
            outbox.push(inbox.pop());
    }
    return outbox.pop();
};