How to Implement a Stack Data Structure

Stacks are a great data structure for use in many programming situations as they’re a cohesive way in which to keep a linear collection of elements. Stacks generally follow the “First in Last Out” principle and can be thought of by, well, a stack. Think stack of books a librarian is putting back onto the shelves, or a stack of mail that has yet to be opened and read. These items are all stacked right upon one another and the first item to be handled is taken from the top. The last item to be handled is usually the one all the way at the bottom.

In computer science, a stack is an abstract implementation of these tangible examples described above — a linear collection of elements. The element at the top of the stack data structure is the first element to be handled and the element at the bottom of the stack data structure is usually the last item to be handled.

Stack Data Structure Operations

Stacks have two main operations:

  1. Push adds an element to the top of the stack
  2. Pop removes an element from the top of the stack

Stacks can also have other operations, not limited to but including:

  1. Peek inspects the top most element without removing it
  2. Is Empty returns a Boolean indicating if the stack is empty
  3. Clear empties the stack instantly without iteration
  4. Size returns the length of the stack

Stack Data Structure in JavaScript

Below is an example of a stack data structure implemented as a Class in JavaScript:

class Stack {
  constructor() {
    this.items = [];
  }
  clear() {
    this.items = [];
  }
  isEmpty() {
    return this.items.length === 0;
  }
  peek() {
    return this.items[this.items.length - 1];
  }
  pop() {
    return this.items.pop();
  }
  push(element) {
    this.items.push(element);
  }
  size() {
    return this.items.length;
  }
}

Stack Data Structure Use Cases and Examples

Ever hear of a stack overflow? Or a call stack? Ever need to undo actions with particular software like a word processor or image editing software? Or even the back button on your web browser? These situations are all using stacks!

Below is an example of how a stack data structure could work for handling a “back button” or “undo” scenario:

// create a new stack
const pages = new Stack();

// user navigates to google to search for cat photos and clicks a result
// push the previous page onto the stack upon loading the next
pages.push('https://www.google.com');

// user is now on 'https://www.catphotos.org' and is clicking through
// continue pushing the previous page
pages.push('https://www.catphotos.org');
pages.push('https://www.catphotos.org/fuzzy-cat01.jpg');
pages.push('https://www.catphotos.org/fuzzy-cat02.jpg');

// user decides, ya know what, no more fuzzy cats, lets go back a bit
// user clicks back, the now current page is 'https://www.catphotos.org/fuzzy-cat02.jpg'
window.location = pages.pop();

// user clicks back again
// the now current page is 'https://www.catphotos.org/fuzzy-cat01.jpg'
window.location = pages.pop();

// user clicks back again
// the now current page is 'https://www.catphotos.org'
window.location = pages.pop();

// user clicks back one last time
// the now current page is 'https://www.google.com'
window.location = pages.pop();

// the stack is now empty, and can be confirmed by using the following:
pages.peak(); // returns undefined
pages.isEmpty(); // returns true

Stack Data Structure and Time Complexity

As a stack is a linear data structure with generally limited operations, accessing and/or interacting with the top-most item from the stack via push or pop has a worst-case run-time complexity of O(1).

Like what you've read?