Data Structures: Stack

Introduction

Stack is a Last In First Out data structure that holds a collection of items. The last element pushed into the stack will be the first element that is going to be removed. The stack data structure is one of the most used data structures and is simple to learn.

Important Concept

• The last item that is pushed into the stack is called the top of the stack.
• Stack works on LIFO (last in first out) system which means the last pushed item will be removed first.
• In a stack, we always perform insertion and deletion at the top of the stack.

Time Complexity

Applications of Stack

Undo/Redo

For Undo/Redo features, the stack has been a choice for a lot of engineers. Stack and momento design pattern combined are heavily used to create Undo/Redo mechanism.

Backtracking

Backtracking is one of the algorithm designing techniques. In backtracking, we try a way to solve a problem. If that way is not efficient, we come back to the previous state and go into some other paths. To get back from the current state, we need to store the previous state. For that purpose, we need a stack.

CallStack

If you are working with javascript then you will definitely come across the term "Call Stack". Yes, javascript execution states are also maintained in a stack that is in the browser. For more information read my blog How V8 engine works?

Coding a Stack in JavaScript

Let's take a look at how we can create a stack in javascript

class Stack {
  constructor() {
    this.items = []; // initially, the stack is empty.
  }
}

We are going to use Arrays to create a stack. We have created a simple class named Stack and inside the constructor, we are initializing an empty array which is an empty stack.

Now let's take a look at some of the most important operations of a stack.

push

Adding an item at the end/top of a stack is called push

  push(item) {
    this.items.push(item);
    return item;
  }

pop

Removing an item at the end/top of a stack is called pop.

  pop() {
    return this.items.pop();
  }

length / size

size method returns the length of the stack or the count of total items in the stack.

  size() {
    return this.items.length;
  }

peek

peek method returns the top element of the stack.

  peek() {
    return this.items[this.size() - 1];
  }

Now, we have coded all the operations in the stack, let's test it.

const stack = new Stack();  // [] => Empty stack
stack.push(1);              // [1];
stack.push("Heyy!!");       // [1, 'Heyy!!']
stack.size();               // 2
stack.peek();               // "Heyy!!"
stack.push(false);          // [1, "Heyy!!", false] 
stack.pop();                // After pop, stack:  [1, "Hey!!"]
stack.pop();                // After pop, stack:  [1]
stack.peek();               // 1

Improvements?

For now, the basic functionality of the stack is done. But yes, we can add more stuff to make it more functional. And you are going to do it as your assignment.

Tasks:

1. Add an isEmpty() function which can check either a stack is empty or not. The function will return boolean true if the stack is empty and false if not.

2. Use that function in the pop, peek and size method and provide user-friendly messages to users. For example, If I'm poping an element from the stack, and the stack is already empty, you can show a message The stack is already empty.

---

That's all folks!

That's it, folks! hope it was a good read for you. Thank you! ✨

👉 Follow me: Github Twitter LinkedIn Youtube