Skip to content

Instantly share code, notes, and snippets.

@thinker3197
Last active September 9, 2016 15:05
Show Gist options
  • Save thinker3197/be2356b19026e773e745c7cac8d92ea3 to your computer and use it in GitHub Desktop.
Save thinker3197/be2356b19026e773e745c7cac8d92ea3 to your computer and use it in GitHub Desktop.
Implementation of queue using two stacks in O(m) time for m operations
// Create Stack
function Stack() {
var array = [];
this.push = function() {
array.push.apply(array, arguments);
return arguments;
};
this.pop = function() {
return array.pop.apply(array, arguments);
};
this.length = function() {
return array.length;
};
this.peek = function() {
return array;
};
}
// Create Queue
function Queue() {
var inStack = new Stack,
outStack = new Stack;
this.eneque = function() {
inStack.push.apply(inStack, arguments);
};
this.dequeue = function() {
if (outStack.length() === 0) {
while (inStack.length() > 0) {
outStack.push(inStack.pop());
}
}
return outStack.pop();
};
this.length = function() {
return inStack.length() + outStack.length();
};
this.peek = function() {
if(outStack.length() === 0) {
return inStack.peek();
}
return outStack.peek().concat(inStack.peek());
};
}
// Tests (queue)
var queue = new Queue();
queue.eneque(10, 20, 30, 40, 50, 70);
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.peek());
queue.eneque(90, 120, 300, 410, 80, 110);
console.log('SIZE: ', queue.length());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log('SIZE: ', queue.length());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.peek());
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment