Stack which finds the minimum element

Question

Write a program to implement stack which implements min a method which gives the minimum element below the top element in the stack.

const items = Symbol('Stack items');
class Stack {
 constructor() {
 this[items] = [];
 } 
 pop() {
 return this[items].pop();
 }
 push(data) {
 this[items].push(data);
 }
 size() {
 return this[items].length;
 }
 isEmpty() {
 return this.size() === 0;
 }
 peek() {
 return this[items][this.size() - 1];
 }
}
class MinStack {
 constructor(iterable) {
 this.stack = new Stack();
 this.minStack = new Stack();
 if (iterable) {
 for (let val of iterable) {
 this.push(val);
 }
 }
 } 
 min() {
 if (this.stack.isEmpty()) {
 throw new Error('Min of empty stack'); 
 }
 return this.minStack.peek();
 }
 pop() {
 if (this.stack.isEmpty()) {
 throw new Error('Popping from empty stack'); 
 }
 let val = this.stack.pop();
 if (val === this.minStack.peek()) {
 this.minStack.pop();
 }
 return val;
 }
 push(data) {
 if (this.minStack.isEmpty() && this.stack.isEmpty()) {
 this.minStack.push(data);
 } else if (data <= this.minStack.peek()) {
 this.minStack.push(data);
 }
 this.stack.push(data);
 }
 size() {
 return this.stack.size();
 }
 isEmpty() {
 return this.stack.isEmpty();
 }
 peek() {
 return this.stack.peek();
 }
}
const s = new MinStack();
console.log('// Empty Stack //');
try {
 console.log(s.min()); // Err
} catch (err) {
 console.log('Err: ' + err.message);
}
console.log('// Non-Empty Stack //');
s.push(1);
s.push(2);
s.push(3);
console.log(s.pop() === 3);
console.log(s.min() === 1);
console.log(s.pop() === 2);
console.log(s.min() === 1);
console.log(s.pop() === 1);
try {
 console.log(s.min()); // Err
} catch (err) {
 console.log('Err: ' + err.message); // Err
}
console.log('// Using iterator //');
const s2 = new MinStack([3, 2, 5, 1]);
console.log(s2.min() === 1);
console.log(s2.pop() === 1);
console.log(s2.min() === 2);
console.log(s2.pop() === 5);
console.log(s2.min() === 2);
console.log(s2.pop() === 2);
console.log(s2.min() === 3);
console.log(s2.pop() === 3);
/*
Space complexity: O(2n) ~ O(n)
Time complexities:
1. Construction
 Iterator: O(n) else O(1)
2. Push
 O(1) for both stacks
3. Pop
 O(1) for both stacks
4. Min
 O(1)
5. Size
 O(1)
6. isEmpty
 O(1)
*/

Answer 1

Nicely written. The space saving trick you did with min stack is especially nice.

When you push, the conditions can be a bit simpler:

push(data) {
 if (this.minStack.isEmpty() && this.stack.isEmpty()) {
 this.minStack.push(data);
 } else if (data <= this.minStack.peek()) {
 this.minStack.push(data);
 }
 this.stack.push(data);
}

The min stack will only be empty when the stack is empty, so you can drop the second condition in the first if statement. And since the else if branch does the same thing as the if branch, you can combine them:

push(data) {
 if (this.minStack.isEmpty() || data <= this.minStack.peek()) {
 this.minStack.push(data);
 }
 this.stack.push(data);
}

• greybeard: (Reading space saving trick, I searched for tricky handling of runs of identical values...)