Stacks: The Delicious Data Structure with Arrays and Linked Lists

I have always enjoyed thinking of stacks as a pile of paratha, the Indian flatbread that is both savory and comforting. When you're eating, do you ever find yourself asking for more and more? I know I do. "Please add more at the top" is something I always say.

In computer science, a stack is a type of list where elements are added and removed in a specific order. This order is based on the principle of Last-In-First-Out (LIFO), which means that the last item added to the stack is the first one to be removed.

Here's an example to help understand this principle: imagine you have a stack of hot, freshly-made Parathas in front of you. The first Paratha you added to the stack is at the bottom, and the last one is at the top. If you want to eat a Paratha, you'll pick the one at the top of the stack, which is the last one you added.

Stack with an array

Lets define a stack with Typescript. It has a constructor that sets up three things: topIndex, size, and data.

• topIndex keeps track of the index of the top element in the stack (initialized to 1, since the stack is empty).
• size specifies the size of the stack (initialized to 4, but this can be changed).
• data is an array that stores the elements in the stack. The constructor initializes it to an empty array, but elements can be added to it using the push method.

Here's the breakdown of the basic operations of a stack:

• push: adds an item to the top of the stack.
• pop: removes the top item from the stack.
• peek: returns the top item without removing it.

class Stack {
  topIndex: number;
  size: number;
  data: number[];
  constructor() {
    this.topIndex = -1;
    this.size = 4;
    this.data = [];
  }
}

Let's add some elements to the stack!

private _resize() {
  if (this.topIndex === this.size) {
    this.size = this.size * 2;
  }
}
push(value: number) {
	this._resize();
	this.topIndex += 1;
	this.data[this.topIndex] = value;
}

Another way to think of a stack is as a dynamic array, where the last element added is always at the end of the array. As elements are added to the stack, the array grows dynamically to accommodate them. Check out how dynamic structures work in my other article ( Dynamic data structure from arrays to linked lists ).

peek() {
  return this.data[this.topIndex];
}
isEmpty() {
  return this.topIndex === -1;
}
pop() {
  if (this.isEmpty()) return null;
  let last = null;
  last = this.data[this.topIndex];
  this.data[this.topIndex] = null;
  this.topIndex -= 1;
  return last;
}

The pop method removes the top element from the stack. It first checks if the stack is empty, and if so, returns null. Otherwise, it sets the last element to a variable named last, sets the top element to null, decrements the topIndex, and returns last.

One thing to note is that in the current implementation, the pop method does not actually remove the element from the data array. Instead, it sets its value to null. There are various ways to optimize performance and memory, but in this article, I will focus on explaining how the stack works.

Stack with a linked list

Another way to implement a stack is by using a linked list. A linked list is a collection of nodes, each containing a value and a reference to the next node. We can use a linked list to implement a stack by treating the first node as the top of the stack. Check out my other article on how linked lists work ( Dynamic data structure from arrays to linked lists ).

Here's an implementation of a stack using a linked list:

class Node {
  value: number;
  next: Node | null;
  constructor(value: number, next: Node | null = null) {
    this.value = value;
    this.next = next;
  }
}

class Stack {
  top: Node | null;
  size: number;
  constructor() {
    this.top = null;
    this.size = 0;
  }
  push(value: number) {
    const newNode = new Node(value);
    newNode.next = this.top;
    this.top = newNode;
    this.size++;
  }
  pop() {
    if (!this.top) return null;
    const value = this.top.value;
    this.top = this.top.next;
    this.size--;
    return value;
  }
  peek() {
    if (!this.top) return null;
    return this.top.value;
  }
  isEmpty() {
    return this.size === 0;
  }
}

Just like we did with arrays you can implement the same methods. Stack class points to the first node with its top property, and keeps track of the number of nodes with its size property. The push method adds a new node with the given value to the top of the stack, increments the size, and sets its next property to the previous top. The pop method removes and returns the top node, and the peek method returns the value of the top node without removing it. The isEmpty method returns true if the stack is empty.

Using a linked list to implement a stack has several advantages over using an array. One significant advantage is that linked lists can grow dynamically without needing to resize. This means that you don't have to worry about the size of the stack when you're writing your code.

Another advantage is that you can easily insert or remove elements from the beginning of a linked list, which is much faster than doing so from the middle of an array. This can be especially useful if you need to frequently add or remove elements from the stack.

However, it's important to keep in mind that linked lists require more memory overhead than arrays. Each node in the linked list contains a reference to the next node, which takes up extra memory. This can be a concern if you're working with a large number of elements. Additionally, accessing elements in a linked list can be slower than accessing elements in an array, especially if the elements are not stored sequentially in memory.

In this blog post, we've covered the basics of stacks, including what they are, how they work, and some common implementations. I hope that this post has been helpful in your understanding of stacks and that you're now better equipped to use this powerful data structure in your own code.

Remember, stacks are just one of many data structures that you can use to solve problems. By learning about different data structures and algorithms, you can become a more versatile and effective programmer. So keep exploring, keep learning, and keep building amazing things!

// Stacks with arrays
class Stack {
  topIndex: number;
  size: number;
  data: number[];
  constructor() {
    this.topIndex = -1;
    this.size = 4;
    this.data = [];
  }
  private _resize() {
    if (this.topIndex === this.size) {
      this.size = this.size * 2;
    }
  }
  push(value: number) {
    this._resize();
    this.topIndex += 1;
    this.data[this.topIndex] = value;
  }
  peek() {
    return this.data[this.topIndex];
  }
  isEmpty() {
    return this.topIndex === -1;
  }
  pop() {
    if (this.isEmpty()) return null;
    let last = null;
    last = this.data[this.topIndex];
    this.data[this.topIndex] = null;
    this.topIndex -= 1;
    return last;
  }
}

Related Articles