An introduction to the Stack data structure

30, Apr 2019 - 6 min read

Stacks are list-like data structures that are used to solve many computing problems. They are used extensively in programming language implementations for a lot of things for example expression evaluation, handling function calls using the call stack e.t.c. Data from the stack can be added or removed from the top of the stack only. This makes it easy to implement and fast.

Stacks are known as Last In, First Out(LIFO) data structures i.e the last added item will be the first to be removed. A simple example of a stack in real world is a loaf of bread. Slices can only be removed from top to bottom

Stack Operations

Since stacks are LIFO data structures, any element that is not at the top of the stack can't be accessed. To get an element at the top of the stack, you have to remove all elements on top of it first. The primary operations of a stack include:-

Push - Adding elements to a stack
Pop - Removing elements from the stack
Peek - Viewing the elements at top of the stack. Unlike the pop operation, this doesn't permanently remove the element from the stack

While pushing, popping and peeking are the primary operations of a stack, there might be other properties and operations you need to keep track of. For example we will be implementing a stack below with extra operations like clear to empty the stack and properties like length to keep track of the number of elements in the stack and isEmpty to tell us whether the stack is empty or not.

Implementing the Stack

There are several ways of implementing a stack in JavaScript. For example depending on the programming style you favour you might decide to use a factory function, a constructor function or ES6 classes. We will be seeing examples of all in this blog post. And during implementation, if you decide to implement it using the JavaScript array under the hood, you might decide to use JavaScript methods or not. We will see both approaches.

Using a factory function

Lets see how we can use a factory function to create a stack as seen below. We wont be using any array methods in the implementation.

Code explanation will be included as comments

// a function to help us create the stack
function createStack() {
  // to store items
  let stack = [];

  /**
   * The length of the stack
   * Will be used to keep track of the top most item of the stack
   */
  let stackLength = 0;

  // return an object literal that exposes stack operations and properties
  return {
    push(element) {
      // add element to stack
      stack[stackLength] = element;

      // increment stackLength by one
      stackLength += 1;
    },

    pop() {
      // if the stack is not empty
      if (stackLength > 0) {
        // decrement stackLength by one
        stackLength -= 1;
        // return the top most item of the stack
        return stack[stackLength];
      }
      // return undefined if stack is empty
      return undefined;
    },

    peek() {
      // return the top most item on the stack or undefined if stack is empty
      return stack[stackLength - 1];
    },

    clear() {
      // set the stackLength to zero
      stackLength = 0;
    },

    // we will use getters to determine whether the stack is empty
    get isEmpty() {
      return stackLength === 0;
    },

    // we use a getter to get the length of the stack
    get length() {
      return stackLength;
    },
  };
}

If you were curious you should have noticed that we don't remove an element from the stack when we run the pop operation, we only decrement the stackLength by one and return the top most value. This is so because the store stack variable isn't accessible to the outside world and there is no way to access those items as all operations depend on the stackLength. That is why we don't even need to set the stack array to an empty array in the clear operation.

Taking our stack toa test

stack = createStack();
console.log('Length: ', stack.length); // 0
console.log('Is Empty: ', stack.isEmpty); // true

console.log('Add 12');
stack.push(12);
console.log('Length: ', stack.length); // 1
console.log('Add Dennis');
stack.push('Dennis');
console.log('Length: ', stack.length); // 2
console.log('Next Item to Remove: ', stack.peek()); // "Dennis"
console.log('Removing: ', stack.pop()); // 'Removing Dennis'
console.log('Length: ', stack.length); // 1
console.log('Is Empty: ', stack.isEmpty); // false
console.log('Next Item to Remove: ', stack.peek()); // 12
console.log('Clearing the Stack');
stack.clear();
console.log('Length: ', stack.length); // 0
console.log('Is Empty: ', stack.isEmpty); // true

Using a constructor function

We will be leveraging a constructor function to create a stack in JavaScript, we won't use any array methods as well but we will make use of the Postfix and Prefix operators in favor of Addition Assignment (stackLength += 1) and Subtraction Assignment (stackLength -= 1) used to implement the push and pop method respectively. Lets see this in action.

This as well demonstrates one of the ways how OOP was done before the coming of ES6 classes. The main difference between this approach and the factory function approach is that the length and isEmpty are methods in this approach unlike the factory function approach where they were properties.

function Stack() {
  // to store items
  this._stack = [];

  /**
   * The length of the stack
   * Will be used to keep track of the top most item of the stack
   */
  this._stackLength = 0;
}

// add an item to the stack
Stack.prototype.push = function(element) {
  /**
   * this._stackLength++ uses this._stackLength to access the top item
   * increments it to the new stack length
   */
  this._stack[this._stackLength++] = element;
};

Stack.prototype.pop = function() {
  // --this._stackLength++ decrements stack length by one and then uses it to
  // access the top item in the stack
  return this._stackLength > 0 ? this._stack[--this._stackLength] : undefined;
};

// return the top item of the stack
Stack.prototype.peek = function() {
  return this._stack[this._stackLength - 1];
};

// clear the stack
Stack.prototype.clear = function() {
  this._stackLength = 0;
};

// return length of the stack
Stack.prototype.length = function() {
  return this._stackLength;
};

// show whether a stack is empty or not
Stack.prototype.isEmpty = function() {
  return this._stackLength === 0;
};

You must have noticed change in implementation of the pop and push methods. The implementation of the constructor function uses Postfix and Prefix operators. Though it results into less lines of code, the code is confusing and might not be obvious if someone doesn't know how the two work. Its always better to write readable code instead of doing some clever confusing hacks

Lets take our stack to a test.

stack = new Stack();
console.log('Length: ', stack.length()); // 0
console.log('Is Empty: ', stack.isEmpty()); // true

console.log('Add 12');
stack.push(12);
console.log('Length: ', stack.length()); // 1
console.log('Add Dennis');
stack.push('Dennis');
console.log('Length: ', stack.length()); // 2
console.log('Next Item to Remove: ', stack.peek()); // "Dennis"
console.log('Removing: ', stack.pop()); // 'Removing Dennis'
console.log('Length: ', stack.length)(); // 1
console.log('Is Empty: ', stack.isEmpty()); // false
console.log('Next Item to Remove: ', stack.peek()); // 12
console.log('Clearing the Stack');
stack.clear();
console.log('Length: ', stack.length()); // 0
console.log('Is Empty: ', stack.isEmpty()); // true

Using ES6 classes

In this section, we will use ES6 classes to implement the stack, we will as well use array methods to do so in favour of the indexing approach used in the previous approaches. Lets see this in action.

class Stack {
  constructor() {
    // the array to implement the stack
    this._stack = [];
  }

  push(item) {
    // use the array push method to add the item to the stack
    this._stack.push(item);
  }

  pop() {
    // use the array pop method to remove item from the stack
    return this._stack.pop();
  }

  peek() {
    return this._stack.length > 0
      ? this._stack[this._stack.length - 1]
      : undefined;
  }

  clear() {
    // clear the stack
    this._stack = [];
  }

  get isEmpty() {
    return this._stack.length === 0;
  }

  get length() {
    return this._stack.length;
  }
}

Taking our stack toa test

stack = new Stack();
console.log('Length: ', stack.length); // 0
console.log('Is Empty: ', stack.isEmpty); // true

console.log('Add 12');
stack.push(12);
console.log('Length: ', stack.length); // 1
console.log('Add Dennis');
stack.push('Dennis');
console.log('Length: ', stack.length); // 2
console.log('Next Item to Remove: ', stack.peek()); // "Dennis"
console.log('Removing: ', stack.pop()); // 'Removing Dennis'
console.log('Length: ', stack.length); // 1
console.log('Is Empty: ', stack.isEmpty); // false
console.log('Next Item to Remove: ', stack.peek()); // 12
console.log('Clearing the Stack');
stack.clear();
console.log('Length: ', stack.length); // 0
console.log('Is Empty: ', stack.isEmpty); // true

I hope this was a good introduction to the stack data structure, if you find anyway this blog post can be improved feel free to reach out to me on twitter. I am dennisjjagwe on twitter

Discuss On Twitter | Tweet | Edit on Github