Stack

  • Data Structures
  • Code
  • Stack

I've been doing a ton of writing this week on a conference talk that I'm hoping to present in the next month or two. This is taking the majority of my focus, but I still wanted to put out my regular posts, so I'm tackling some shorter data structures. This week it'll be the Stack and next week it'll be the Queue. And that conference talk will likely make its way here as a nice, lengthy blog post as well. Anyway, onto the Stack!

A Stack is a data collection that abides by a LIFO (Last In, First Out) principle. The last element added to the Stack will be the first element removed from the Stack.

You can visualize this data structure like a stack of plates that you are cleaning. You build the stack of plates by placing one on top of another. When you take a plate to clean it, you will take that plate from the top of the stack. In this way the last plate placed on the stack is the first plate that is removed from the stack that gets cleaned.

Structure and Terminology

Like with Singly and Doubly Linked Lists, a single item of data within a Stack is called a node. A node in a Stack stores two things:

  1. A Value (I will use val), which is the thing you want stored
  2. A Previous reference (I will use prev), which is the pointer that references the previous item in the Stack

As for the Stack itself, it will always keep track of a first property, which is the very first item inserted into the Stack, a last property, which is the last item inserted into the Stack, and the size, which is the number of items in the Stack.

So what does a Stack look like? Here's a very basic example:

1000 -> 100 -> 10 -> 1

In this little example, each number represents a node within the Stack. For each node, the number represents that node's value, and the arrow represents the prev pointer reference.

1000 would be the last item in the Stack, and the first item to be removed from the Stack. 1000's prev would reference 100, 100's prev would reference 10, and 10's prev would reference 1. 1 would be the first item in the Stack, making it the first item that was inserted into the Stack as well as the last item that would be removed from the Stack. The size of the Stack is 4, as there are 4 items within the Stack.

Practical Examples of a Stack

So where might you encounter a Stack in real world programming? The call stack is one instance, which keeps track of where a script has run within a program. Another example might be the Undo/Redo functionality within Photoshop.

Big O of a Stack

OperationComplexity
InsertionO(1)
RemovalO(1)
SearchingO(n)
AccessO(n)

Insertion and Removal: Insertion and Removal happen in constant time because we are only working with the start or end of the list, wherever insertion/removal happens.

Searching and Access: Searching and Access are not very efficient in a Stack. Remember that we are concerned with one data item at a time, the item on the top of the Stack (technically, the item that was most recently inserted into the Stack). If the thing we are looking for is at the bottom of Stack (or the first item inserted into the Stack), then we need to remove everything else within the Stack first, giving us a Big O of O(n).

Implementing a Stack with an Array

Some programming languages have their own Stack implementation. Unfortunately, JavaScript is not one of those languages. We can (and will) implement a Stack on our own, but we can also use a plain old Array with built-in array methods to mimic Stack-like behavior.

Array Implementation #1: .push() and .pop()

One way that we can implement a Stack using an Array is with the .push() and .pop() methods, which add and remove items at the end of the array.

var stack = [];
// Add things instack.push("Joey");stack.push("Sebastian");stack.push("Bart");
// Items have been stacked one after another, newest item lastconsole.log(stack);// ["Joey", "Sebastian", "Bart"]
// "Peek" at the last item insertedconsole.log(stack.at(-1)); // "Bart"
// Check if the "Stack" is emptyconsole.log(!stack.length); // false
// Remove items - Last In, First Out (LIFO)stack.pop(); // "Bart";stack.pop(); // "Sebastian"stack.pop(); // "Joey"

I want to call out the stack.at(-1) line of code. The .at() method is new in JavaScript and not fully adopted by all modern browsers. It's an alternative way of accessing items in an Array (or a String), as opposed to bracket notation. I will likely write a blog post about this new method, but here I'm leveraging one of its useful features: the ability to use negative values to access items from the end of the Array. stack.at(-1) is simply a way of accessing the item at the end of the array, and achieves the same thing as stack[stack.length - 1].

I'll also discuss the !stack.length line. This simply coerces the value of stack.length to its opposite Boolean. Remember that 0 is falsy, so if stack.size is 0, then stack.size will coerce to false, but the single ! operator will return its opposite value, true. If stack.size is any other value it will evaluate to true, and the single ! operator will return its opposite value, false, indicating that there are items within the array. This is the same as the following:

if (stack.length === 0) {  return true;} else {  return false;}

Array Implementation #2: .unshift() and .shift()

The second way that we can implement Stack-like behavior using an Array is with the .unshift() and .shift() methods, which add and remove items at the beginning of the array.

var stack = [];
// Add things instack.unshift("Joey");stack.unshift("Sebastian");stack.unshift("Bart");
// Items have been stacked one after another, newest item firstconsole.log(stack);// ["Bart", "Sebastian", "Joey"]
// "Peek" at the last item insertedconsole.log(stack.at(0)); // "Bart"
// Check if the "Stack" is emptyconsole.log(!stack.length); // false
// Remove items - Last In, First Out (LIFO)stack.shift(); // "Bart"stack.shift(); // "Sebastian"stack.shift(); // "Joey"

This is a good place to offer a gentle reminder that adding and removing stuff at the beginning of an Array is inefficient due to re-indexing subsequent items. This makes the .push()/.pop() method far more efficient than .unshift()/.shift().

A final note in this section is that this simply demonstrates the ability to use the built-in Array structure to achieve Stack-like behavior and treatment of data. You also could use one of our Linked List implementations as well. There are major performance considerations to think about if any of these structures are actually going to get used in a real-world application, and this gets into territory that is well beyond the scope of this blog.

Stack Implementation

I'd also like to implement my own version of the Stack data structure, just like I did with the Singly and Doubly Linked Lists. Here's the full implementation for future reference. Sections below will detail each method.

Note that there are a lot of different ways to implement a Stack, and this is just one. The thought with this approach is to continue with the same methods I have used to build Singly Linked List and Doubly Linked List implementations, and to demonstrate the foundational concepts behind a Stack. If you want to do an Object- or Array-based implementation, then I highly encourage you to do so! I believe that no matter your approach, understanding the mechanics of these data structures and getting them to work makes you a stronger programmer.

class Node {  constructor(val) {    this.val = val;    this.prev = null;  }}
class Stack {  constructor() {    this.first = null;    this.last = null;    this.size = 0;  }  isEmpty() {    return this.first ? false : true;  }  peek() {    return this.first ? this.last.val : undefined;  }  pop() {    if (!this.first) {      return undefined;    }    var currentLast = this.last;    if (this.size === 1) {      this.first = null;      this.last = null;    } else {      this.last = currentLast.prev;      currentLast.prev = null;    }    this.size--;    return currentLast.val;  }  push(val) {    var newLast = new Node(val);    if (!this.first) {      this.first = newLast;      this.last = this.first;    } else {      newLast.prev = this.last;      this.last = newLast;    }    return ++this.size;  }}

Node Class

Each item within the Stack is called a node. Any time we add a node into the Stack, we'll do it using a Node Class. This class accepts a value, val, and also has a prev property. By default prev will be assigned the value of null, but as new nodes get added to the Stack, the prev on these new nodes will point to earlier items in the Stack.

class Node {  constructor(val) {    this.val = val;    this.prev = null;  }}

Stack List Class

We'll also use a Stack Class to initialize the Stack iteslf. We're starting here with just its constructor, but we'll add in all of the needed methods as we go. On initialization, an empty Stack will have a first set to null, a last also set to null, and a size set to 0.

class Stack {  constructor() {    this.first = null;    this.last = null;    this.size = 0;  }}

Methods and Operations

.push()

The first method we'll introduce is the .push() method, which adds a new node to the Stack.

Here are the steps we take to create the .push() method:

  1. Create a new node with the value, val. I'll store this in a variable called newLast
  2. Check if the Stack is empty. We'll know we have an empty Stack if the Stack has no first
  3. If the Stack is empty:
    1. Assign the new node as last
    2. Assign the first to also equal last
  4. If the Stack isn't empty:
    1. Set the new node's prev to equal the current last item in the Stack
    2. Assign the new node as the last item in the Stack
  5. Increment the size by 1
  6. Return the size

.push() Implementation

push(val) {  var newLast = new Node(val);  if (!this.first) {    this.first = newLast;    this.last = this.first;  } else {    newLast.prev = this.last;    this.last = newLast;  }  return ++this.size;}

In the very last line, return ++this.size, I'm using the ++ increment operator in a pre-increment fashion. This is done by pre-pending this.size with ++. This code simply increments this.size before returning this.size. It allows me to accomplish, in one line, the following:

this.size++;return this.size;

It's a small optimization. Read more about pre-incrementing in this Stack Overflow thread.

.pop()

Now let's look at the .pop() method, which removes the last item in the Stack.

  1. Return undefined if the Stack is empty (again, if there's no first then it's an empty Stack)
  2. Store the current last item into a variable named currentLast
  3. Check whether there is only 1 item in the Stack
  4. If there's only 1 item in the Stack:
    1. Assign first the value of null
    2. Assign last the value of null
  5. If there's more than 1 item in the Stack:
    1. Assign last the value of currentLast's prev
    2. Assign currentLast's prev the value of null, breaking the link between this node and the Stack
  6. Decrement size by 1
  7. Return the value of the node we have removed from the list (currentLast.val)

.pop() Implementation

pop() {  if (!this.first) {    return undefined;  }  var currentLast = this.last;  if (this.size === 1) {    this.first = null;    this.last = null;  } else {    this.last = currentLast.prev;    currentLast.prev = null;  }  this.size--;  return currentLast.val;}

.peek()

In a Stack we're only concerned with the value of the last item in the Stack. Because of this, there is no .get() method. Instead, our Access method is called .peek().

  1. Check if the Stack is empty
  2. If the Stack is empty:
    1. Return undefined
  3. If the Stack isn't empty:
    1. Return (but do not modify or remove) the value of the last item in the Stack

.peek() Implementation

peek() {  if (!this.first) {    return undefined;  } else {    return this.last.val;  }}

This code works just fine, but considering we're only returning one of two things based off the condition of one thing existing, this little bit of code can get cleaned up with the help of a Ternary Operator.

peek() {  return this.first ? this.last.val : undefined;}

This code does the same thing as the if/else statement above. It checks whether this.first evaluates to true. If so, it will return this.last.val. Otherwise, if this.first evaluates to false, it will return undefined.

.isEmpty()

The last method in our Stack implementation is the .isEmpty() method, which returns true if the Stack is empty and false if the Stack is not empty.

  1. Check whether there are any items in the Stack
  2. If there aren't items in the Stack, return true
  3. If there are items in the Stack, return false

Similar to the .peek() method, we could use an if/else statement here, but I'll go for another Ternary Operator statement to keep things consistent.

.isEmpty() Implementation

isEmpty() {  return this.first ? false : true;}