Stack In Data Structures | Operations, Uses & More (+Examples)

12 mins read

A stack is a fundamental data structure that follows the Last In, First Out (LIFO) principle, meaning the last element added is the first to be removed. Imagine a stack of plates—when you add a new plate, it goes on top, and when you remove one, you take the topmost plate first.

In this article, we'll explore the concept of a stack, its operations (push, pop, peek, and isEmpty), its implementation using arrays and linked lists, and its real-world applications in areas like recursion, expression evaluation, and undo/redo functionality.

What Is A Stack In Data Structure?

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means that the last element added to the stack will be the first one to be removed. Think of it as a collection of elements where insertion and deletion happen only at one end, called the top of the stack.

Basic Stack Operations

A stack primarily supports the following operations:

1. Push – Adds an element to the top of the stack.
2. Pop – Removes the top element from the stack.
3. Peek (or Top) – Returns the top element without removing it.
4. isEmpty – Checks if the stack is empty.

Stacks can be implemented using arrays (fixed size) or linked lists (dynamic size). They are widely used in recursion, expression evaluation, and memory management.

Real-Life Analogy Of A Stack

Imagine a stack of plates in a cafeteria. When new plates are washed, they are placed on top of the stack. When someone needs a plate, they take the topmost plate first. You cannot take a plate from the middle or bottom without first removing the ones above it.

This is exactly how a stack works—the last plate placed (pushed) is the first one taken (popped).

Understanding Stack Operations

A stack supports four primary operations: Push, Pop, Peek (Top), and isEmpty. Let's explore each with explanations and examples.

1. Push (Insertion)

The Push operation adds an element to the top of the stack. If the stack is implemented using an array and is full, we call this a stack overflow.

Example:

Imagine we have an empty stack, and we push elements 10, 20, and 30 onto it.

Example (C++ using an array):

void push(int value) {
    if (top == MAX - 1) {
        cout << "Stack Overflow!\n";
        return;
    }
    arr[++top] = value;  // Increment top and add element
    cout << value << " pushed to stack\n";
}

2. Pop (Removal)

The Pop operation removes the top element from the stack. If the stack is empty, we call this a stack underflow.

Example:

Continuing from the previous stack (30 → 20 → 10):

Example (C++ using an array):

void pop() {
    if (top == -1) {
        cout << "Stack Underflow!\n";
        return;
    }
    cout << arr[top--] << " popped from stack\n";  // Remove top element
}

3. Peek (Top Element)

The Peek (Top) operation returns the top element without removing it.

Example:

If the stack is 30 → 20 → 10, peek() will return 30.

Example (C++ using an array):

int peek() {
    if (top == -1) {
        cout << "Stack is empty!\n";
        return -1;
    }
    return arr[top];  // Return top element
}

4. isEmpty (Check if Stack is Empty)

The isEmpty operation checks whether the stack contains any elements.

Example (C++ using an array):

bool isEmpty() {
    return (top == -1);  // Returns true if stack is empty
}

Stack Implementation In Data Structures

Stacks can be implemented using two approaches:

1. Array-based Stack – Uses static memory allocation.
2. Linked List-based Stack – Uses dynamic memory allocation.

Let’s explore both implementations in detail.

Stack Implementation Using Arrays

An array-based stack uses a fixed-size array to store elements. It operates efficiently but has a fixed size limitation, meaning it cannot grow dynamically if more space is needed.

Characteristics of Array-based Stack

• Static memory allocation (fixed size).
• Fast access since indexing is direct.
• Risk of Stack Overflow when the array is full.

Code Example:

#include <iostream>
#define MAX 5  // Maximum size of stack
using namespace std;

class Stack {
    int top;
    int arr[MAX];  // Stack array

public:
    Stack() { top = -1; }  // Constructor initializes top

    // Push operation
    void push(int value) {
        if (top == MAX - 1) {
            cout << "Stack Overflow!\n";
            return;
        }
        arr[++top] = value;  // Increment top and add element
        cout << value << " pushed to stack\n";
    }

    // Pop operation
    void pop() {
        if (top == -1) {
            cout << "Stack Underflow!\n";
            return;
        }
        cout << arr[top--] << " popped from stack\n";  // Remove top element
    }

    // Peek operation
    int peek() {
        if (top == -1) {
            cout << "Stack is empty!\n";
            return -1;
        }
        return arr[top];
    }

    // Check if stack is empty
    bool isEmpty() {
        return (top == -1);
    }
};

int main() {
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);
    cout << "Top element: " << s.peek() << endl;
    s.pop();
    cout << "Top element after pop: " << s.peek() << endl;
    return 0;
}

Output:

10 pushed to stack
20 pushed to stack
30 pushed to stack
Top element: 30
30 popped from stack
Top element after pop: 20

Explanation:
In the above code example-

1. We include <iostream> header to enable input and output operations and define MAX as 5, which represents the maximum size of the stack.
2. The Stack class has two private members: top, which tracks the top index, and arr[MAX], an array that stores stack elements.
3. The constructor initializes top to -1, indicating that the stack is empty initially.
4. The push function checks if the stack is full (top == MAX - 1). If it is, we print "Stack Overflow!". Otherwise, we increment top and insert the new value.
5. The pop function checks if the stack is empty (top == -1). If so, we print "Stack Underflow!". Otherwise, we remove and display the topmost element.
6. The peek function returns the top element if the stack is not empty; otherwise, it prints "Stack is empty!" and returns -1.
7. The isEmpty function checks whether the stack is empty by returning true if top == -1.
8. In main(), we create a Stack object s, push three values (10, 20, 30), and display the top element using peek().
9. After popping an element, we check the top element again, demonstrating the Last-In-First-Out (LIFO) behavior of the stack.

Stack Implementation Using Linked Lists

A linked list-based stack dynamically allocates memory as needed, overcoming the fixed size limitation of arrays.

Characteristics of Linked List-based Stack

• Dynamic memory allocation (no fixed size).
• Efficient memory usage (no wasted space).
• No Stack Overflow unless system memory is exhausted.
• Slower access due to pointer traversal.

Code Example:

#include <iostream>
using namespace std;

// Node structure
class Node {
public:
    int data;
    Node* next;

    Node(int value) {
        data = value;
        next = nullptr;
    }
};

class Stack {
    Node* top;

public:
    Stack() { top = nullptr; }  // Constructor initializes top as NULL

    // Push operation
    void push(int value) {
        Node* newNode = new Node(value);
        newNode->next = top;  // New node points to old top
        top = newNode;  // Update top to new node
        cout << value << " pushed to stack\n";
    }

    // Pop operation
    void pop() {
        if (top == nullptr) {
            cout << "Stack Underflow!\n";
            return;
        }
        Node* temp = top;
        top = top->next;  // Move top pointer to next node
        cout << temp->data << " popped from stack\n";
        delete temp;  // Free memory
    }

    // Peek operation
    int peek() {
        if (top == nullptr) {
            cout << "Stack is empty!\n";
            return -1;
        }
        return top->data;
    }

    // Check if stack is empty
    bool isEmpty() {
        return (top == nullptr);
    }
};

int main() {
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);
    cout << "Top element: " << s.peek() << endl;
    s.pop();
    cout << "Top element after pop: " << s.peek() << endl;
    return 0;
}

Output: 

10 pushed to stack
20 pushed to stack
30 pushed to stack
Top element: 30
30 popped from stack
Top element after pop: 20

Explanation:

In the above code example-

1. We include <iostream> to enable input and output operations and use the std namespace for convenience.
2. The Node class represents a stack node, containing an integer data and a pointer next that links to the next node.
3. The Node constructor initializes data with the given value and sets next to nullptr.
4. The Stack class has a private pointer top, which tracks the top node of the stack.
5. The constructor initializes top as nullptr, indicating an empty stack.
6. The push function creates a new node, sets its next pointer to the current top, and updates top to point to this new node.
7. The pop function checks if the stack is empty (top == nullptr). If so, we print "Stack Underflow!". Otherwise, we store top in a temporary pointer, move top to the next node, print the popped value, and free the memory of the removed node.
8. The peek function returns the value of top if the stack is not empty; otherwise, it prints "Stack is empty!" and returns -1.
9. The isEmpty function checks whether the stack is empty by returning true if top == nullptr.
10. In main(), we create a Stack object s, push three values (10, 20, 30), and display the top element using peek().
11. After popping an element, we check the top element again, demonstrating the Last-In-First-Out (LIFO) behavior of the stack.

Comparison: Array vs. Linked List Implementation

Therefore:

• Array-based stacks are simpler and faster but suffer from fixed size limitations.
• Linked list-based stacks offer dynamic memory allocation and avoid overflow but require extra memory for pointers and are slightly slower.

For applications with a known, limited size, array-based stacks are efficient. If the stack size is dynamic, linked list-based stacks are preferred.

Applications Of Stack In Data Structures

Stacks play a vital role in various real-world and computational applications. Let's explore some of the key uses of stacks in programming and everyday scenarios.

1. Function Call Stack (Recursion)

Use Case: Manages function calls in programming languages.

When a function is called, its execution details (such as local variables, return address, etc.) are pushed onto the stack. When the function completes, it is popped from the stack. This mechanism enables recursion to work properly.

2. Expression Evaluation

Use Case: Evaluating infix, prefix, and postfix expressions.

Stacks are used in expression conversion (infix to postfix) and expression evaluation (postfix evaluation).

Example: Postfix Expression Evaluation

A postfix expression like 3 4 + 2 * is evaluated using a stack:

1. Push 3, push 4.
2. Encounter + → Pop 3 and 4, compute 3 + 4 = 7, push 7.
3. Push 2.
4. Encounter * → Pop 7 and 2, compute 7 * 2 = 14.

Final result: 14.

3. Undo/Redo Operations

Use Case: Used in text editors and software to track changes.

• Undo: Stores previous states of a document in a stack. Pressing "Undo" pops the last state.
• Redo: Uses another stack to store undone operations. Pressing "Redo" pushes back the popped state.

4. Backtracking (Maze Solving, DFS in Graphs)

Use Case: Used in solving mazes and Depth-First Search (DFS) in graphs.

Backtracking involves exploring a path, and if it fails, reverting to the previous step (LIFO principle).

5. Browser History Navigation

Use Case: Managing web page visits in browsers.

• Back Button: Pops the last visited page from the stack.
• Forward Button: Pushes the popped page onto a redo stack.

Advantages And Disadvantages Of Stack Data Structure

Like every data structure, a stack has its own advantages and limitations. Let's explore them in detail.

Advantages Of Stack Data Structure

1. Simple and Efficient – Follows LIFO (Last In, First Out), making operations easy to implement.
2. Fast Operations – Push, pop, and peek take O(1) time complexity (very efficient).
3. Dynamic Memory Allocation – Linked list implementation avoids fixed size limitations of arrays.
4. Function Call Management – Used in recursion to store function execution states.
5. Expression Evaluation – Helps in evaluating infix, prefix, and postfix expressions.
6. Backtracking Support – Used in maze solving, DFS (Depth-First Search), and undo operations.
7. Reversing Data – Helpful in reversing strings, linked lists, and arrays.

Disadvantages Of Stack Data Structure

1. Fixed Size (Array Implementation) – If implemented with an array, size is limited and can cause stack overflow.
2. No Random Access – Can only access the top element; middle elements are not directly accessible.
3. Not Suitable for Frequent Modifications – Inefficient when inserting or deleting elements from the middle.
4. Stack Overflow in Recursion – Too many recursive calls can lead to program crashes.
5. Extra Memory Usage (Linked List Implementation) – Linked list-based stacks need extra space for pointers.

Conclusion

The Stack data structure is a fundamental concept in computer science, offering a simple yet powerful way to organize and manage data using the LIFO (Last In, First Out) principle. It is widely used in function call management, expression evaluation, backtracking algorithms, and undo/redo operations.

While stacks provide efficient push and pop operations with O(1) time complexity, they also come with limitations like fixed size (in arrays), no random access, and the risk of stack overflow in deep recursion. Choosing between an array-based or linked list-based implementation depends on the specific use case and memory constraints.

Understanding stacks helps in solving complex problems efficiently and is a building block for mastering advanced data structures like queues, trees, and graphs. By leveraging stacks effectively, we can optimize algorithm design and improve system performance. 

Frequently Asked Questions

Q. What is a stack in data structures, and how does it work?

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. This means the last element added is the first one to be removed.

• It supports basic operations like:
• Push – Adds an element to the top.
• Pop – Removes the top element.
• Peek (Top) – Returns the top element without removing it.
• isEmpty – Checks if the stack is empty.

Stacks can be implemented using arrays (fixed size) or linked lists (dynamic size).

Q. How is stack different from other data structures like queues and linked lists?

Stacks are LIFO-based, whereas:

• Queues follow FIFO (First In, First Out) – elements are removed in the order they were added.
• Linked Lists allow insertion/deletion at any position, while stacks allow it only from the top.

Q. Where are stacks used in real life?

Stacks are used in various applications, including:

• Function Call Stack – Stores function execution order in recursion.
• Undo/Redo Operations – Used in text editors, graphics software, and IDEs.
• Expression Evaluation – Used in infix, prefix, and postfix calculations.
• Browser History Navigation – The "Back" button works using a stack.
• Backtracking Algorithms – Used in DFS (Depth-First Search), maze-solving, and AI pathfinding.

Q. What are the limitations of using a stack?

While stacks are useful, they have some limitations:

• Fixed Size (Array Implementation) – If implemented using an array, the size is fixed, leading to stack overflow if more elements are added.
• No Random Access – Unlike arrays, stacks allow access only to the top element, making searching inefficient.
• Recursive Stack Overflow – Excessive recursive function calls can cause stack overflow, crashing the program.
• Extra Memory in Linked List Implementation – If implemented using a linked list, each node requires extra memory for pointers.

Q. How do array-based and linked list-based stack implementations differ?

Both implementations have their pros and cons:

Q. How does a stack handle function calls in programming?

In programming, stacks are used to manage function calls and recursion.

• When a function is called, its execution details (local variables, return address) are pushed onto the stack.
• Once the function completes, its details are popped off the stack, and control returns to the calling function.
• This mechanism helps in handling recursive function calls efficiently.

Example: Function Call Stack in Recursion

void functionA() { 
    functionB(); // functionB is called and pushed onto the stack 
} 
void functionB() { 
    functionC(); // functionC is called and pushed onto the stack
} 
void functionC() { 
    // FunctionC executes and completes
}  
int main() { 
    functionA();  // Function A starts first
}

Stack Execution Order:

• functionA() → functionB() → functionC() (pushed onto stack).
• functionC() completes and is popped, then functionB(), then functionA().

Suggested Reads: 

1. What Is Selection Sort Algorithm? Explained With Code Examples
2. Learn All About Bubble Sort Algorithm (With Code Examples)
3. Merge Sort Algorithm | Working, Applications & More (+Examples)
4. Quick Sort Algorithm | Working, Applications & More (+Examples)
5. Heap Sort Algorithm - Working And Applications (+ Code Examples)