Stacks/Queues

Question 1

What is a stack?

Answer 1

Data type that serves as a collection of elements. Two prinicipal operations: push and pop. Push adds element to collection. Pop removes last element that was added. LIFO.

Question 2

How do you push element on to linked list stack?

Answer 2

var newNode = node(); newNode.next = top; top = newNode;

Question 3

How do you pop element on to linked list stack?

Answer 3

if(top === null){ return false; } var result = top.value; top = top.next; return result;

Question 4

How do you reverse an array using a stack?

Answer 4

function reverseArray(arr){
 var stack = [];
 for(var i = 0; i \< arr.length; i++){
 stack.push(arr[i])
 }
 for(var j = 0; j \< arr.length; j++){
 arr[i] = stack.pop();
 }
 return arr;
}

Question 5

What is a queue?

Answer 5

Data type that serves as a collection of elements. Two principal operations: enqueue and dequeue. Enqueue adds element to the end collection. Dequeue removes element from the front of the collection. FIFO.

Question 6

How do you enqueue element on to linked list queue?

Answer 6

var newNode = node(); newNode.next = top; top = newNode;

Question 7

How do you dequeue element on to linked list queue?

Answer 7

if(top === null){ return false; } var result; while(top.next){ if(top.next === null){ result = top; top = null; } top = top.next; } return result;

Question 8

How would you design a stack which, in addition to push and pop, has a function min which returns the minimum element? Push, pop, and min should all operate in O(1) time.

Answer 8

function Stack(){
 this.count = 0;
 this.stack = {};
 this.min;
}

Stack.prototype.push = function(data){
 if(Object.keys(this.stack).length === 0){
 this.min = data;
 }
 else if(this.min \> data){
 this.min = data;
 }
 this.stack[this.count] = data;
 this.count++;
};

Stack.prototype.pop = function() {
if(this.size() > 0){
return this.stack[–this.count];
}
};

Stack.prototype.size = function(){
return this.count;
};

Stack.prototype.minimum = function(){
return this.min;
};