Stack Data Structure - Explained with Examples

Data Structures are frameworks to store, organize and process data in the database of a web application so that it can be used effectively. You must have seen how a bank’s cashier puts different currency notes in different sections of the drawer to make the transactions easier. Similarly, we need to store data in a structured way to perform operations easily.

There are multiple data structures for different use cases. In this article, we’ll learn about stack data structure, its operations, applications, and more.

Introduction to Stack Data Structure

Stack is a linear data structure that stores elements in a specific order.

Let’s take our browser history as an example. When we jump to a new page, the previous page gets stored in the browser history. We can access that page by simply clicking the back button.  

This is possible because all the pages we’ve visited are stored in a new-to-old arrangement in the form of a stack. Hitting the back button opens up the page that is right below the newest page. 

Stack is an abstract data type with a pre-defined capacity. 

What is an Abstract data type?

ADTs specify the data and its applications but is independent of how it’s implemented. ADTs are implemented using different methods and logic in different programming languages.

These data structures are flexible and don’t depend on languages or machines. (Learn more about ADT here)

Stack follows a Last In First Out principle for adding or removing elements.

Consider a stack of books arranged in an order.

Now, if we want to take the bottom-most book out, we will have to take out the topmost book first, then the second, then the third until we finally reach the first one at the bottom.

The book that goes in last will be the first one to come out. This is called the LIFO principle. In the same case, the book added first will be removed at last which refers to the First In Last Out method aka FILO.

A stack can only contain elements of the same data type.

Every time we add an element, it goes to the top of the stack, and that’ll always be the first one to be removed from the stack. 

In other words, stacks can be defined as containers in which operations like insertion and deletion can only take place at one end.

How does Stack work?

To implement a stack, we need to keep a pointer to the ‘top’ of the stack i.e. the last element to be added. As the operations always happen at the top of the stack, this pointer always follows the topmost element.

Operations in Stack Data Structure

push() –  Push operation means adding/inserting an element into the stack.

pop() – Pop operation refers to removing an element from the stack. As we know that we can only work with one element at a time, we remove the top of the stack.

peek() – This operation allows us to view the element which is at the top. There are no changes made in the stack here.

isEmpty() – It checks if the stack is empty or not to prevent the programmers from performing operations on an empty stack. This operation returns a boolean value – ‘True’ if size = 0, otherwise it returns ‘false’

isFull() – It’s the exact opposite of isEmpty operation, as it returns ‘true’ if the stack is full, else returns ‘false’.

Now, let’s go through a step by step process to see how these operations come together-

1) While initializing the stack, we set the value of the pointer ‘top’ = -1. This value means that the stack is empty.

2) When we add/push an element, the value increases to ‘top’ = 0, and the new element is placed in the position corresponding to the ‘top’ pointer.

3) Similarly, adding another element increases its value to ‘top = 1’ and the pointer comes up to the newest element.

4) Now, when we remove/pop an element, the pointer just moves below to show that the topmost element is no longer a part of the stack, and it can be deleted or replaced.

• We check if the stack is already full before pushing.

• We check if the stack is empty before implementing the pop operation.

Implementation of JavaScript Stack using Arrays

Let’s see how a stack is implemented using JavaScript.

class Stack {
    constructor() {
        this.items = [];
    }
    
    // add element to the stack
    push(element) {
        return this.items.push(element);
    }

    // remove element from the stack
    pop() {
        if(this.items.length > 0) {
            return this.items.pop();
        }
    }

    // view the last element
    peek() {
        return this.items[this.items.length - 1];
    }

    // check if the stack is empty
    isEmpty(){
      return this.items.length == 0;
    }

    // the size of the stack 
    size(){
        return this.items.length;
    }

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

In the above example, we create a new ‘stack’ class and implement the different operations like push, pop, isEmpty, etc.

Applications of Stack Data Structure

Expression evaluation 

Stack is used for the evaluation of a given expression. Let’s take the following expression as an example-

6* (2+4) + 16/4

It wouldn’t be wrong to say that this expression requires a list of operations. These operations are put in a stack in the order of high precedence.

As parenthesis (bracket) have the highest precedence, we solve the numbers inside the bracket first to get –

6*6 + 16/4

Once the parenthesis is accessed and returns a value, the division is next inline –

6*6 + 4

Now, we move to the multiplication part and get :

36 + 4,

The value returned after the addition is 40.

This is how arithmetic operations are kept in a stack to evaluate different expressions.

Converting Decimal to binary

We use stacks to find the equivalent binary code for a decimal number.

How?

We write a program in which – we divide any decimal value by 2 and store the remainder each time (be it 0 or 1) in a stack. Once the value reaches 0 (no digit left), we pop one digit at a time from the stack and print the binary number.

Since a stack remembers the sequence in which we call the functions, we get the correct returns.

Reversing a String

The characters of a string can be reversed using a stack. We use the basic ‘push’ and ‘pop’ functions to do this. First, we push the characters one by one into the stack.

Let’s take the word ‘MASAI’ as an example.

As stack follows the last in first out principle, the last element to go in would be the first one to come out. We’ll use the pop function one by one to print the reversed string.

Backtracking

We use stacks in backtracking. Backtracking solves complex problems using recursive algorithms.

Let’s say we have to solve a maze puzzle. We choose one path and if we get stuck somewhere in the middle or reach the wrong target, we come back to the starting point. Then we take another path and the process goes on until we find the optimal solution.

In this process, we have to store the previous path to be able to track back to the initial position. That’s where we use a stack.

It stores the previous solution to the problem which is then used to try a new solution.

Function Calls

We use stacks in programs that call functions in succession. Let’s say there is a function X which calls the function Y, and Y calls the function Z.

Now, we can only process function X if function Y is completed and returned. Similarly, for Y, the function Z needs to return.

We can see that the function X is the first one to get started but the last one to return. This should remind you of the FILO principle in stacks.

And, that’s why stack is the ideal structure for handling function calls.

Hopefully, this article helped you get a clear understanding of the stack data structure and its applications.

If you want to understand data structures & algorithms from scratch, here’s our beginner’s guide to DSA.

If you’re willing to learn full-stack web development at zero upfront fee and get a high-paying job in the software industry, check out the full-stack developer course. Masai provides both part-time and full-time training in web development and helps students get placed in top tech companies, the likes of Ola, Swiggy, Freshworks, Byju’s, Dream11, etc. (Know 11 unicorn startups that hire from Masai)