Module 15: Stack

Learning Objectives

By the end of this module, you will be able to:

• Understand the Stack data structure.
• Learn the LIFO (Last In, First Out) principle.
• Implement a stack using arrays and linked lists.
• Perform stack operations such as Push, Pop, Peek, and Display.
• Solve problems using stacks, including parentheses matching and expression evaluation.
• Learn infix, prefix, and postfix expressions.
• Build real-world applications like browser history and undo functionality.

Introduction

A Stack is one of the most fundamental linear data structures in Computer Science.

A stack stores elements in such a way that the last element inserted is the first one removed.

This behavior is called LIFO (Last In, First Out).

Stacks are widely used in:

• Function Calls
• Recursion
• Browser History
• Undo/Redo Systems
• Expression Evaluation
• Syntax Parsing
• Backtracking Algorithms
• Depth First Search (DFS)

What is a Stack?

A Stack is a linear data structure where insertion and deletion occur only at one end called the Top.

Visualization

textCopy
1          TOP
2           │
3           ▼
4        +------+
5        |  50  |
6        +------+
7        |  40  |
8        +------+
9        |  30  |
10        +------+
11        |  20  |
12        +------+
13        |  10  |
14        +------+

If we insert 60, it becomes the new top.

If we remove an element, 60 is removed first.

Stack Operations

Stack Using Array

Arrays provide a simple implementation of a stack.

We need:

• Array
• Top variable

Example

textCopy
1Array
2
3Index
4
50   1   2   3   4
6
7Top = -1 (Initially Empty)

Stack Implementation Using Array

cCopy
1#include <stdio.h>
2
3#define SIZE 5
4
5int stack[SIZE];
6int top = -1;
7
8void push(int value)
9{
10    if(top == SIZE - 1)
11    {
12        printf("Stack Overflow\n");
13        return;
14    }
15
16    stack[++top] = value;
17}
18
19int pop()
20{
21    if(top == -1)
22    {
23        printf("Stack Underflow\n");
24        return -1;
25    }
26
27    return stack[top--];
28}
29
30int peek()
31{
32    if(top == -1)
33        return -1;
34
35    return stack[top];
36}
37
38void display()
39{
40    for(int i = top; i >= 0; i--)
41    {
42        printf("%d ", stack[i]);
43    }
44
45    printf("\n");
46}
47
48int main()
49{
50    push(10);
51    push(20);
52    push(30);
53
54    display();
55
56    printf("Popped = %d\n", pop());
57
58    printf("Top = %d", peek());
59
60    return 0;
61}

Output

textCopy
130 20 10
2
3Popped = 30
4
5Top = 20

Time Complexity

Stack Overflow

Overflow occurs when we try to insert into a full stack.

Example

textCopy
1SIZE = 5
2
3Already contains
4
510
620
730
840
950
10
11Push 60
12
13↓
14
15Stack Overflow

Stack Underflow

Underflow occurs when we remove an element from an empty stack.

Example

textCopy
1Stack Empty
2
3Pop()
4
5↓
6
7Stack Underflow

Stack Using Linked List

Linked Lists remove the fixed-size limitation of arrays.

Each node contains:

• Data
• Next Pointer

Node Structure

cCopy
1struct Node
2{
3    int data;
4    struct Node *next;
5};

Push Operation

cCopy
1#include <stdlib.h>
2
3struct Node
4{
5    int data;
6    struct Node *next;
7};
8
9struct Node *top = NULL;
10
11void push(int value)
12{
13    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
14
15    newNode->data = value;
16    newNode->next = top;
17
18    top = newNode;
19}

Pop Operation

cCopy
1int pop()
2{
3    if(top == NULL)
4    {
5        printf("Stack Underflow\n");
6        return -1;
7    }
8
9    struct Node *temp = top;
10
11    int value = temp->data;
12
13    top = top->next;
14
15    free(temp);
16
17    return value;
18}

Array vs Linked List Stack

Applications of Stack

Stacks are used in many real-world systems.

Examples

• Browser Back Button
• Undo Feature
• Function Calls
• Expression Evaluation
• Syntax Checking
• Recursion
• Depth First Search
• Backtracking

Parentheses Matching

Problem

Check whether an expression contains balanced parentheses.

Example

Valid

textCopy
1(a+b)
2
3((x+y)*z)

Invalid

textCopy
1(a+b))
2
3((x+y)

Algorithm

1. Push every opening bracket.
2. Pop when a closing bracket appears.
3. If the stack becomes empty correctly, the expression is balanced.

Program

cCopy
1#include <stdio.h>
2
3#define SIZE 100
4
5char stack[SIZE];
6int top = -1;
7
8void push(char c)
9{
10    stack[++top] = c;
11}
12
13char pop()
14{
15    return stack[top--];
16}
17
18int main()
19{
20    char str[] = "{[()]}";
21
22    for(int i = 0; str[i] != '\0'; i++)
23    {
24        if(str[i] == '(' || str[i] == '[' || str[i] == '{')
25        {
26            push(str[i]);
27        }
28        else
29        {
30            if(top == -1)
31            {
32                printf("Not Balanced");
33                return 0;
34            }
35
36            pop();
37        }
38    }
39
40    if(top == -1)
41        printf("Balanced");
42    else
43        printf("Not Balanced");
44
45    return 0;
46}

Time Complexity

textCopy
1O(n)

Expression Evaluation

Computers cannot directly evaluate infix expressions efficiently.

Stacks are used to:

• Convert expressions
• Evaluate expressions

Infix Expression

Operator appears between operands.

Example

textCopy
1A + B
2
35 + 10

Readable by humans.

Prefix Expression

Operator appears before operands.

Example

textCopy
1+ A B
2
3+ 5 10

No parentheses required.

Postfix Expression

Operator appears after operands.

Example

textCopy
1A B +
2
35 10 +

Easy for computers to evaluate using a stack.

Comparison of Expression Types

Evaluating a Postfix Expression

Example

textCopy
123*54*+

Step-by-Step

textCopy
1Push 2
2
3Push 3
4
5Multiply
6
7Push 5
8
9Push 4
10
11Multiply
12
13Add
14
15Result = 26

Algorithm

1. Scan left to right.
2. Push operands.
3. On an operator, pop two operands.
4. Perform the operation.
5. Push the result.
6. Continue until the expression ends.

Time Complexity

textCopy
1O(n)

Practice Project 1: Browser History

Browser history works like a stack.

Example

textCopy
1Google
2
3↓
4
5YouTube
6
7↓
8
9GitHub
10
11↓
12
13ChatGPT

Press Back

textCopy
1GitHub

Press Back Again

textCopy
1YouTube

Each new page is Push.

Back button performs Pop.

Practice Project 2: Undo Feature

Text editors use stacks.

Example

textCopy
1Write Hello
2
3↓
4
5Write World
6
7↓
8
9Delete World
10
11↓
12
13Undo
14
15↓
16
17World Restored

Every operation is stored in the stack.

Undo pops the latest action.

Applications

• MS Word
• VS Code
• Photoshop
• Figma

Practice Project 3: Reverse a String Using Stack

cCopy
1#include <stdio.h>
2#include <string.h>
3
4int main()
5{
6    char str[] = "Stack";
7    int length = strlen(str);
8
9    char stack[100];
10    int top = -1;
11
12    for(int i = 0; i < length; i++)
13    {
14        stack[++top] = str[i];
15    }
16
17    while(top != -1)
18    {
19        printf("%c", stack[top--]);
20    }
21
22    return 0;
23}

Output

textCopy
1kcatS

Time Complexity

textCopy
1O(n)

Common Interview Questions

1. Implement Stack using Array.
2. Implement Stack using Linked List.
3. Reverse a String using Stack.
4. Check Balanced Parentheses.
5. Convert Infix to Postfix.
6. Convert Infix to Prefix.
7. Evaluate a Postfix Expression.
8. Evaluate a Prefix Expression.
9. Design a Min Stack.
10. Implement Two Stacks in One Array.

Common Mistakes to Avoid

• Forgetting to check for Stack Overflow or Underflow.
• Accessing the top element when the stack is empty.
• Not updating the top pointer after push or pop operations.
• Forgetting to free memory when using a linked-list implementation.
• Confusing the order of operands during postfix or prefix evaluation.

Best Practices

• Always check whether the stack is empty before calling pop() or peek().
• Use an array-based stack when the maximum size is known in advance.
• Prefer a linked-list implementation when the stack size is dynamic.
• Keep stack operations modular by implementing separate functions for push, pop, peek, and isEmpty.
• Use stacks for problems involving recursion, expression parsing, backtracking, and balanced symbols.
• Analyze the time and space complexity of stack-based algorithms to choose the most efficient solution.

Module Summary

In this module, you learned:

• What a Stack is and how it follows the LIFO (Last In, First Out) principle.
• How to implement a stack using arrays and linked lists.
• Core stack operations such as Push, Pop, Peek, Display, Overflow, and Underflow.
• Practical applications of stacks, including browser history, undo functionality, and function call management.
• How stacks are used for parentheses matching and expression evaluation.
• The differences between Infix, Prefix, and Postfix expressions.
• How to solve common interview problems using stacks.

After completing this module, you'll be ready to learn Queues, where you'll study FIFO operations, circular queues, double-ended queues (Deque), priority queues, queue implementations using arrays and linked lists, and real-world scheduling applications.