Stack in Data Structure: What is Stack and Its Applications

TL;DR: A stack is a data structure where elements are added, removed, and accessed from the top. This article explains how push, pop, peek, isFull, and isEmpty work, how stacks are implemented using arrays and linked lists, and where they are used in programming

Stacks in Data Structures is a linear type of data structure that follows the LIFO (Last-In-First-Out) principle and allows insertion and deletion operations from one end of the stack data structure, that is top. Implementation of the stack can be done by contiguous memory which is an array, and non-contiguous memory which is a linked list. Stack plays a vital role in many applications.

Introduction to Stack in Data Structures

A stack is a linear data structure that follows the LIFO principle, which means Last In, First Out. It can also be understood as FILO, or First In, Last Out.

A simple real-life example of a stack is a pile of books. You add a new book to the top of the pile, and when you need to remove one, you usually take the top book first. In the same way, a stack allows insertion and deletion from only one end, called the top of the stack.

Adding a new element to a stack is called a push operation. Removing an element from a stack is called a pop operation. Since only the top element can be accessed at any given time, stacks are useful in areas like function calls, undo operations, browser history, and expression evaluation.

Next, let’s look at how stacks are represented in data structures.

Want a Top Software Development Job? Start Here!AI-Powered Full Stack Developer ProgramExplore Program

Stack Representation in Data Structures

Working of Stack in Data Structures

Now, assume that you have a stack of books.

You can only see the top, i.e., the top-most book, namely 40, which is kept top of the stack.

If you want to insert a new book first, namely 50, you must update the top and then insert a new text.

And if you want to access any other book other than the topmost book that is 40, you first remove the topmost book from the stack, and then the top will point to the next topmost book.

After working on the representation of stacks in data structures, you will see some basic operations performed on the stacks in data structures.

Basic Operations on Stack in Data Structures

There following are some operations that are implemented on the stack.

Push Operation

Push operation involves inserting new elements in the stack. Since you have only one end to insert a unique element on top of the stack, it inserts the new element at the top of the stack.

Pop Operation

Pop operation refers to removing the element from the stack again since you have only one end to do all top of the stack. So removing an element from the top of the stack is termed pop operation.

Peek Operation

Peek operation refers to retrieving the topmost element in the stack without removing it from the collections of data elements.

isFull(): isFull function is used to check whether or not a stack is empty.

isEmpty(): isEmpty function is used to check whether or not a stack is empty.

First, you will learn about the functions:

isFull()

The following is the algorithm of the isFull() function:

begin
    if top equals maxsize - 1
        return true
    else
        return false
end

The implementation of the isFull() function is as follows:

bool isFull() {
    if (top == maxsize - 1)
        return true;
    else
        return false;
}

isEmpty()

The following is the algorithm of the isEmpty() function:

begin
    if top equals -1
        return true
    else
        return false
end

The implementation of the isEmpty() function is:

Want a Top Software Development Job? Start Here!AI-Powered Full Stack Developer ProgramExplore Program

bool isEmpty() {
    if (top == -1)
        return true;
    else
        return false;
}

Push Operation

Push operation includes various steps, which are as follows :

Step 1: First, check whether or not the stack is full

Step 2: If the stack is complete, then exit

Step 3: If not, increment the top by one

Step 4: Insert a new element where the top is pointing

Step 5: Success

The algorithm of the push operation is:

begin push(stack, item)
    if stack is full
        display "Stack is full"
        exit
    end if

    top = top + 1
    stack[top] = item
end

This is how you implement a push operation:

void push(int item) {
    if (!isFull()) {
        top = top + 1;
        stack[top] = item;
    } else {
        printf("Stack is full");
    }
}

Pop Operation

Step 1: First, check whether or not the stack is empty

Step 2: If the stack is empty, then exit

Step 3: If not, access the topmost data element

Step 4: Decrement the top by one

Step 5: Success

The following is the algorithm of the pop operation:

begin pop(stack)
    if stack is empty
        display "Stack is empty"
        return null
    end if

    item = stack[top]
    top = top - 1
    return item
end

Implementing a pop operation is as follows:

int pop() {
    int item;

    if (!isEmpty()) {
        item = stack[top];
        top = top - 1;
        return item;
    } else {
        printf("Stack is empty");
        return -1;
    }
}

Peek Operation

The algorithm of a peek operation is:

begin peek(stack)
    if stack is empty
        display "Stack is empty"
        return null
    end if

    return stack[top]
end

The implementation of the peek operation is:

int peek() {
    if (!isEmpty()) {
        return stack[top];
    } else {
        printf("Stack is empty");
        return -1;
    }
}

Want a Top Software Development Job? Start Here!AI-Powered Full Stack Developer ProgramExplore Program

Implementation of Stack in Data Structures

You can perform the implementation of stacks in data structures using two data structures that are an array and a linked list.

• Array: In array implementation, the stack is formed using an array. All the operations are performed using arrays. You will see how all operations can be implemented on the stack in data structures using an array data structure.

• Linked-List: Every new element is inserted as a top element in the linked list implementation of stacks in data structures. That means every newly inserted element is pointed to the top. Whenever you want to remove an element from the stack, remove the node indicated by the top, by moving the top to its previous node in the list.

Ranked No.1 Best Coding Bootcamp, our Post Graduate Program in Full Stack Web Development can help you accelerate your career as a software developer. Enroll today!

Application of Stack in Data Structures

Here are the top 7 applications of the stack in data structure:

• Expression Evaluation and Conversion
• Backtracking
• Function Call
• Parentheses Checking
• String Reversal
• Syntax Parsing
• Memory Management

Now you will understand all the applications one at a time.

1. Expression Evaluation and Conversion

There are three types of expression that you use in programming, they are:

Infix Expression: An infix expression is a single letter or an operator preceded by one single infix string followed by another single infix string.

• X
• X + Y
• (X + Y ) + (A - B)

Prefix Expression: A prefix expression is a single letter or an operator followed by two prefix strings.

• X 
• + X Y
• + + X Y - A B

Postfix Expression: A postfix expression (also called Reverse Polish Notation) is a single letter or an operator preceded by two postfix strings.

• X
• X Y +
• X Y + C D - +

Similarly, the stack is used to evaluate these expressions and convert these expressions like infix to prefix or infix to postfix.

Want a Top Software Development Job? Start Here!AI-Powered Full Stack Developer ProgramExplore Program

2. Backtracking

Backtracking is a recursive algorithm mechanism that is used to solve optimization problems.

To solve the optimization problem with backtracking, you have multiple solutions; it does not matter if it is correct. While finding all the possible solutions in backtracking, you store the previously calculated problems in the stack and use that solution to resolve the following issues.

The N-queen problem is an example of backtracking, a recursive algorithm where the stack is used to solve this problem.

3. Function Call

Whenever you call one function from another function in programming, the reference of calling function stores in the stack. When the function call is terminated, the program control moves back to the function call with the help of references stored in the stack.

So stack plays an important role when you call a function from another function.

4. Parentheses Checking

Stack in data structures is used to check if the parentheses like ( ), { } are valid or not in programing while matching opening and closing brackets are balanced or not.

So it stores all these parentheses in the stack and controls the flow of the program.

For e.g ((a + b) * (c + d)) is valid but {{a+b})) *(b+d}] is not valid.

5. String Reversal

Another exciting application of stack is string reversal. Each character of a string gets stored in the stack.

The string's first character is held at the bottom of the stack, and the last character of the string is held at the top of the stack, resulting in a reversed string after performing the pop operation.

6. Syntax Parsing

Since many programming languages are context-free languages, the stack is used for syntax parsing by many compilers.

7. Memory Management

Memory management is an essential feature of the operating system, so the stack is heavily used to manage memory.

With that, you have reached the end of this article on Stacks in Data Structures.

Also Read: Stack in Python

Next Step

“Queues and stack in data structures” is what is next. You will learn about some essential differences between stack and queue.

If you are interested in building a career in the field of software development, then feel free to explore Simplilearn’s Full Stack Development Courses that will give you the work-ready software development training you need. 

Key Takeaways

• A stack follows the Last In, First Out principle, meaning the last element added is the first one removed.
• The top of the stack is the only point where insertion, deletion, and access operations happen.
• The main stack operations are push, pop, peek, isFull, and isEmpty.
• Stacks can be implemented using arrays for contiguous memory or linked lists for dynamic memory allocation.
• Common applications of stacks include function calls, parentheses checking, string reversal, expression conversion, backtracking, syntax parsing, and memory management.