📘 Unit III: Stacks

Complete Exam & Teaching Notes | BCA / BIT / MCA / BSc.CSIT

Full Theory + Terminology + Algorithms + Applications + Programs + Q&A

Unit Objectives:

Become proficient in using stacks and understanding their terms.

Proficiency in implementing stack algorithms such as POP and PUSH.

Application of stacks in solving problems like reverse string, postfix expression evaluation, and infix to postfix conversion.

3.1 Introduction to Stack

What is a Stack?

In real life, a stack is a pile of objects where you can only add or remove items from the top:

A stack of plates in a cafeteria — you take the top plate, and the new plate goes on top.
A stack of books — you place a new book on top and pick from the top.
A stack of trays in a cafeteria dispenser — spring-loaded, always gives the top tray.

In computer science:

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

The analogy is perfect: the last item placed on the stack is the first one taken off.

Why Stack?

Stacks are used everywhere in computing:

The computer's own function call mechanism uses a stack.
Undo operations in text editors use a stack.
Browser back button uses a stack of visited pages.
Compilers use stacks to parse expressions and check brackets.
Recursion is internally implemented using a stack.

Stack as an Abstract Data Type (ADT)

ADT Stack {
    Data:
        - A collection of elements with LIFO ordering
        - A TOP pointer indicating the topmost element

    Operations:
        - push(element)  : Insert element at top
        - pop()          : Remove and return top element
        - peek()/top()   : View top element without removing
        - isEmpty()      : Return true if stack has no elements
        - isFull()       : Return true if stack is full (array implementation)
        - size()         : Return number of elements

    Constraints:
        - All insertions and deletions happen only at the TOP
        - Elements below TOP are not accessible directly
}

Visual Representation

Initial (Empty):        After push(10):     After push(20):     After push(30):
                        TOP → | 10 |        TOP → | 20 |        TOP → | 30 |
   TOP → (empty)               |    |               | 10 |               | 20 |
                               ------               ------               | 10 |
                                                                         ------

After pop() → returns 30:    After pop() → returns 20:
              TOP → | 20 |                 TOP → | 10 |
                    | 10 |                       |    |
                    ------                       ------

3.2 Operations on Stack

A stack supports the following core operations:

Operation 1: PUSH

Definition: Insert (add) an element at the top of the stack.

Before pushing, check if the stack is full → if full, it's an Overflow condition.
If not full, increment TOP and place the element.

Operation 2: POP

Definition: Remove (delete) the element from the top of the stack and return it.

Before popping, check if the stack is empty → if empty, it's an Underflow condition.
If not empty, retrieve the element at TOP and decrement TOP.

Operation 3: PEEK / TOP

Definition: Return the top element of the stack without removing it.

Also called peek or top.
Checks for underflow before returning.

Operation 4: isEmpty

Definition: Returns true if the stack has no elements, false otherwise.

Condition: TOP == -1 (for array implementation).

Operation 5: isFull

Definition: Returns true if the stack has reached its maximum capacity.

Condition: TOP == MAX_SIZE - 1 (for array implementation).

Operation 6: size

Definition: Returns the number of elements currently in the stack.

Value: TOP + 1 (for array implementation).

3.3 Stack Terminology

Term	Definition
TOP	Pointer/index that always refers to the topmost element in the stack
PUSH	Operation to insert an element onto the top of the stack
POP	Operation to remove and return the top element of the stack
PEEK / TOP()	Operation to view the top element without removing it
OVERFLOW	Error condition when PUSH is attempted on a full stack
UNDERFLOW	Error condition when POP is attempted on an empty stack
isEmpty	Condition when the stack has zero elements (TOP = -1)
isFull	Condition when the stack has reached maximum capacity
Stack Frame	A block of memory allocated on the call stack when a function is invoked
Base of Stack	The bottom-most element of the stack (first element pushed)
LIFO	Last In First Out — the fundamental property of a stack
MAX_SIZE	The maximum number of elements a stack can hold (array implementation)
Stack Pointer	The register or variable that holds the address/index of the top element

LIFO Explained

PUSH order:   10 → 20 → 30 → 40
POP order:    40 → 30 → 20 → 10

Stack at maximum:
    TOP →  [ 40 ]   ← Pushed last, Popped first
           [ 30 ]
           [ 20 ]
           [ 10 ]   ← Pushed first, Popped last
    BASE → [    ]

The last element pushed (40) is the first one popped. This is LIFO.

3.4 Algorithms for PUSH and POP

Stack Implementation — Array-Based

In array implementation, we use:

An array STACK[0...MAX-1] to store elements.
An integer TOP initialized to -1 (indicating empty stack).

Initial State: TOP = -1 (Stack Empty)
After 1 push:  TOP = 0
After 2 pushes: TOP = 1
After n pushes: TOP = n-1
isFull when:   TOP = MAX - 1

3.4.1 Algorithm for PUSH

Algorithm PUSH(STACK, TOP, MAX, ITEM)
[Inserts ITEM onto the Stack]

Step 1: IF TOP = MAX - 1 THEN
            Print "STACK OVERFLOW"
            Return
        END IF

Step 2: SET TOP = TOP + 1
        [Increment the TOP pointer]

Step 3: SET STACK[TOP] = ITEM
        [Insert ITEM at the new TOP position]

Step 4: Print "Element", ITEM, "pushed successfully"

Step 5: Return

Flowchart Description:

START
  ↓
Is TOP = MAX-1?
  ↓ YES             ↓ NO
OVERFLOW        TOP = TOP + 1
Print Error         ↓
  ↓          STACK[TOP] = ITEM
STOP                ↓
               Print "Pushed"
                    ↓
                  STOP

C Implementation:

#include <stdio.h>
#define MAX 5

int stack[MAX];
int top = -1;

void push(int item) {
    if (top == MAX - 1) {               // Overflow check
        printf("Stack Overflow! Cannot push %d\n", item);
        return;
    }
    top++;                              // Increment TOP
    stack[top] = item;                 // Insert element
    printf("Pushed: %d\n", item);
}

Java Implementation:

public class Stack {
    int[] stack;
    int top;
    int max;

    Stack(int size) {
        stack = new int[size];
        max = size;
        top = -1;
    }

    void push(int item) {
        if (top == max - 1) {           // Overflow check
            System.out.println("Stack Overflow! Cannot push " + item);
            return;
        }
        stack[++top] = item;           // Increment top, then insert
        System.out.println("Pushed: " + item);
    }
}

Time Complexity: O(1) — push always operates at the top, no shifting needed.

3.4.2 Algorithm for POP

Algorithm POP(STACK, TOP, ITEM)
[Removes and returns the top element from the Stack]

Step 1: IF TOP = -1 THEN
            Print "STACK UNDERFLOW"
            Return NULL
        END IF

Step 2: SET ITEM = STACK[TOP]
        [Retrieve the top element]

Step 3: SET TOP = TOP - 1
        [Decrement the TOP pointer]

Step 4: Print "Popped element:", ITEM

Step 5: Return ITEM

Flowchart Description:

START
  ↓
Is TOP = -1?
  ↓ YES              ↓ NO
UNDERFLOW       ITEM = STACK[TOP]
Print Error           ↓
  ↓             TOP = TOP - 1
STOP                  ↓
               Print "Popped: ITEM"
                      ↓
                 Return ITEM
                      ↓
                    STOP

C Implementation:

int pop() {
    if (top == -1) {                   // Underflow check
        printf("Stack Underflow! Stack is empty\n");
        return -1;
    }
    int item = stack[top];             // Retrieve top element
    top--;                             // Decrement TOP
    printf("Popped: %d\n", item);
    return item;
}

Java Implementation:

int pop() {
    if (top == -1) {                   // Underflow check
        System.out.println("Stack Underflow! Stack is empty");
        return -1;
    }
    int item = stack[top--];           // Retrieve and decrement
    System.out.println("Popped: " + item);
    return item;
}

Time Complexity: O(1) — pop always operates at the top.

3.4.3 Algorithm for PEEK

Algorithm PEEK(STACK, TOP)
[Returns the top element without removing it]

Step 1: IF TOP = -1 THEN
            Print "Stack is Empty"
            Return NULL
        END IF

Step 2: Return STACK[TOP]

C Implementation:

int peek() {
    if (top == -1) {
        printf("Stack is empty\n");
        return -1;
    }
    return stack[top];
}

Complete Stack Program in C

#include <stdio.h>
#define MAX 5

int stack[MAX];
int top = -1;

// PUSH operation
void push(int item) {
    if (top == MAX - 1) {
        printf("Stack Overflow!\n");
        return;
    }
    stack[++top] = item;
    printf("Pushed: %d | TOP = %d\n", item, top);
}

// POP operation
int pop() {
    if (top == -1) {
        printf("Stack Underflow!\n");
        return -1;
    }
    int item = stack[top--];
    printf("Popped: %d | TOP = %d\n", item, top);
    return item;
}

// PEEK operation
int peek() {
    if (top == -1) {
        printf("Stack is empty\n");
        return -1;
    }
    return stack[top];
}

// isEmpty check
int isEmpty() { return top == -1; }

// isFull check
int isFull() { return top == MAX - 1; }

// Display stack
void display() {
    if (top == -1) { printf("Stack is empty\n"); return; }
    printf("Stack (TOP to BOTTOM): ");
    for (int i = top; i >= 0; i--)
        printf("%d ", stack[i]);
    printf("\n");
}

int main() {
    push(10); push(20); push(30); push(40); push(50);
    push(60);   // Overflow
    display();
    pop(); pop();
    display();
    printf("Peek: %d\n", peek());
    printf("isEmpty: %s\n", isEmpty() ? "Yes" : "No");
    return 0;
}

Output:

Pushed: 10 | TOP = 0
Pushed: 20 | TOP = 1
Pushed: 30 | TOP = 2
Pushed: 40 | TOP = 3
Pushed: 50 | TOP = 4
Stack Overflow!
Stack (TOP to BOTTOM): 50 40 30 20 10
Popped: 50 | TOP = 3
Popped: 40 | TOP = 2
Stack (TOP to BOTTOM): 30 20 10
Peek: 30
isEmpty: No

Complete Stack Program in Java

public class Stack {
    int[] stack;
    int top, max;

    Stack(int size) {
        stack = new int[size];
        max = size;
        top = -1;
    }

    void push(int item) {
        if (top == max - 1) { System.out.println("Overflow!"); return; }
        stack[++top] = item;
        System.out.println("Pushed: " + item + " | TOP = " + top);
    }

    int pop() {
        if (top == -1) { System.out.println("Underflow!"); return -1; }
        int item = stack[top--];
        System.out.println("Popped: " + item + " | TOP = " + top);
        return item;
    }

    int peek() {
        if (top == -1) { System.out.println("Empty!"); return -1; }
        return stack[top];
    }

    boolean isEmpty() { return top == -1; }
    boolean isFull()  { return top == max - 1; }

    void display() {
        if (top == -1) { System.out.println("Stack empty"); return; }
        System.out.print("Stack (TOP to BOTTOM): ");
        for (int i = top; i >= 0; i--) System.out.print(stack[i] + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        Stack s = new Stack(5);
        s.push(10); s.push(20); s.push(30);
        s.display();
        s.pop();
        s.display();
        System.out.println("Peek: " + s.peek());
    }
}

3.5 Stack Applications

Stacks are one of the most versatile data structures. Here are the key applications:

3.5.1 Stack Frame (Function Call Stack)

What is a Stack Frame?

When a program calls a function, the computer must remember:

Where to return after the function finishes.
The values of local variables inside the function.
The parameters passed to the function.

All this information is stored in a stack frame (also called an activation record), which is pushed onto the call stack when the function is called, and popped when the function returns.

Structure of a Stack Frame

┌─────────────────────────────┐
│  Return Address             │  ← Where to go after function ends
│  Parameters                 │  ← Arguments passed to function
│  Local Variables            │  ← Variables declared inside function
│  Saved Registers            │  ← CPU registers to restore
│  Previous Frame Pointer     │  ← Link to caller's stack frame
└─────────────────────────────┘

Example

int add(int a, int b) {
    int result = a + b;    // Local variable
    return result;
}

int main() {
    int x = 5, y = 3;
    int sum = add(x, y);   // Function call
    printf("%d", sum);
    return 0;
}

Call Stack at the moment add() is executing:

┌─────────────────┐  ← TOP of call stack
│ add() frame     │
│   a = 5         │
│   b = 3         │
│   result = 8    │
│   return to main│
├─────────────────┤
│ main() frame    │
│   x = 5         │
│   y = 3         │
│   sum = ???     │
└─────────────────┘

After add() returns:

add()'s frame is popped.
Control returns to main() at the return address.
sum is assigned the returned value 8.

Recursive Function Call Stack

int factorial(int n) {
    if (n == 1) return 1;
    return n * factorial(n - 1);
}
// factorial(4) call

Call stack grows with each recursive call:

│ factorial(1) │ ← TOP (returns 1)
│ factorial(2) │ (waiting for factorial(1))
│ factorial(3) │ (waiting for factorial(2))
│ factorial(4) │ (waiting for factorial(3))
└──────────────┘

Then pops one by one as each returns.

Stack Overflow in recursion happens when too many frames pile up and exhaust memory.

3.5.2 Reverse a String using Stack

Concept

The LIFO property of stacks makes them perfect for reversal:

Push all characters of the string onto the stack.
Pop them one by one — since LIFO, they come out in reverse order.

Example:

String: "HELLO"
Push H, E, L, L, O

Stack:
TOP → O
      L
      L
      E
      H ← BOTTOM

Pop: O, L, L, E, H
Result: "OLLEH"

C Program:

#include <stdio.h>
#include <string.h>
#define MAX 100

char stack[MAX];
int top = -1;

void push(char c) {
    if (top == MAX - 1) { printf("Overflow\n"); return; }
    stack[++top] = c;
}

char pop() {
    if (top == -1) { printf("Underflow\n"); return '\0'; }
    return stack[top--];
}

void reverseString(char str[]) {
    int len = strlen(str);

    // Step 1: Push all characters
    for (int i = 0; i < len; i++)
        push(str[i]);

    // Step 2: Pop all characters into string
    for (int i = 0; i < len; i++)
        str[i] = pop();
}

int main() {
    char str[] = "HELLO WORLD";
    printf("Original: %s\n", str);
    reverseString(str);
    printf("Reversed: %s\n", str);
    return 0;
}

Output:

Original: HELLO WORLD
Reversed: DLROW OLLEH

Java Program:

import java.util.Stack;

public class ReverseString {

    static String reverse(String str) {
        Stack<Character> stack = new Stack<>();

        // Step 1: Push all characters
        for (char c : str.toCharArray())
            stack.push(c);

        // Step 2: Pop all characters
        StringBuilder result = new StringBuilder();
        while (!stack.isEmpty())
            result.append(stack.pop());

        return result.toString();
    }

    public static void main(String[] args) {
        String str = "HELLO WORLD";
        System.out.println("Original: " + str);
        System.out.println("Reversed: " + reverse(str));
    }
}

Output:

Original: HELLO WORLD
Reversed: DLROW OLLEH

Trace:

Input: "CAT"
Push C → Stack: [C]
Push A → Stack: [C, A]
Push T → Stack: [C, A, T]  ← TOP=T

Pop T → result: "T"
Pop A → result: "TA"
Pop C → result: "TAC"

Output: "TAC" ✓

3.5.3 Notation Systems — Prefix, Infix, Postfix

Before studying postfix evaluation and infix-to-postfix conversion, we must understand the three notations.

What is a Notation?

A notation is a way of writing a mathematical or logical expression — specifically, where the operator is placed relative to its operands.

Three Notations

Notation	Operator Position	Example	Full Name
Infix	Between operands	A + B	"In the middle"
Prefix	Before operands	+ A B	Polish Notation
Postfix	After operands	A B +	Reverse Polish Notation (RPN)

Examples

Infix	Prefix	Postfix
A + B	+ A B	A B +
A + B * C	+ A * B C	A B C * +
(A + B) * C	* + A B C	A B + C *
A - B + C	+ - A B C	A B - C +
(A + B) * (C - D)	* + A B - C D	A B + C D - *

Why Postfix?

Infix requires rules about operator precedence and parentheses — complex to evaluate by computers.
Postfix has NO parentheses needed and can be evaluated left-to-right using a simple stack — very efficient for computers.
All modern calculators and compilers convert infix to postfix internally.

Operator Precedence (for conversions)

Operator	Precedence	Associativity
^ (power)	3 (Highest)	Right to Left
* , /	2	Left to Right
+ , -	1 (Lowest)	Left to Right
(	0	—

3.5.4 Evaluation of Postfix Expression

Algorithm

Algorithm EVALUATE_POSTFIX(expression)
Input:  Postfix expression as a string
Output: Numerical result

Step 1: Create an empty stack
Step 2: Scan the expression from LEFT to RIGHT
Step 3: For each token in expression:
            IF token is an OPERAND (number):
                PUSH it onto the stack
            IF token is an OPERATOR (+, -, *, /):
                POP operand2 from stack  ← top
                POP operand1 from stack  ← below top
                result = operand1 OPERATOR operand2
                PUSH result onto stack
Step 4: POP and return the final result from stack

Important: When popping for an operator, the first pop gives the right operand and the second pop gives the left operand.

Detailed Example 1: Evaluate `5 3 + 2 *`

Step	Token	Action	Stack State
1	5	Push 5	[5]
2	3	Push 3	[5, 3]
3	+	Pop 3, Pop 5; 5+3=8; Push 8	[8]
4	2	Push 2	[8, 2]
5	*	Pop 2, Pop 8; 8*2=16; Push 16	[16]
6	End	Pop result	16

Verification (infix): (5 + 3) * 2 = 8 * 2 = 16 ✓

Detailed Example 2: Evaluate `6 2 3 + - 3 8 2 / + *`

Step	Token	Action	Stack
1	6	Push	[6]
2	2	Push	[6, 2]
3	3	Push	[6, 2, 3]
4	+	Pop 3,2; 2+3=5; Push	[6, 5]
5	-	Pop 5,6; 6-5=1; Push	[1]
6	3	Push	[1, 3]
7	8	Push	[1, 3, 8]
8	2	Push	[1, 3, 8, 2]
9	/	Pop 2,8; 8/2=4; Push	[1, 3, 4]
10	+	Pop 4,3; 3+4=7; Push	[1, 7]
11	*	Pop 7,1; 1*7=7; Push	[7]
12	End	Pop result	7

Verification: (6 - (2+3)) * (3 + 8/2) = (6-5) * (3+4) = 1 * 7 = 7 ✓

C Program — Postfix Evaluation:

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define MAX 50

float stack[MAX];
int top = -1;

void push(float item) { stack[++top] = item; }
float pop()           { return stack[top--]; }

float evaluatePostfix(char* expr) {
    float op1, op2, result;

    for (int i = 0; expr[i] != '\0'; i++) {
        char token = expr[i];

        if (token == ' ') continue;     // Skip spaces

        if (isdigit(token)) {
            push(token - '0');           // Convert char to number
        } else {
            op2 = pop();                 // Right operand
            op1 = pop();                 // Left operand
            switch (token) {
                case '+': push(op1 + op2); break;
                case '-': push(op1 - op2); break;
                case '*': push(op1 * op2); break;
                case '/': push(op1 / op2); break;
            }
        }
    }
    return pop();   // Final result
}

int main() {
    char expr[] = "5 3 + 2 *";
    printf("Expression: %s\n", expr);
    printf("Result: %.2f\n", evaluatePostfix(expr));
    return 0;
}
// Output: Result: 16.00

Java Program — Postfix Evaluation:

import java.util.Stack;

public class PostfixEvaluation {

    static double evaluate(String expr) {
        Stack<Double> stack = new Stack<>();
        String[] tokens = expr.split(" ");

        for (String token : tokens) {
            if (token.matches("-?\\d+(\\.\\d+)?")) {
                stack.push(Double.parseDouble(token));  // Operand
            } else {
                double op2 = stack.pop();   // Right operand
                double op1 = stack.pop();   // Left operand
                switch (token) {
                    case "+": stack.push(op1 + op2); break;
                    case "-": stack.push(op1 - op2); break;
                    case "*": stack.push(op1 * op2); break;
                    case "/": stack.push(op1 / op2); break;
                }
            }
        }
        return stack.pop();
    }

    public static void main(String[] args) {
        String expr = "5 3 + 2 *";
        System.out.println("Expression: " + expr);
        System.out.println("Result: " + evaluate(expr));
        // Output: Result: 16.0
    }
}

3.6 Algorithm for Converting Infix Expression to Postfix

Why Convert?

Computers cannot directly evaluate infix expressions efficiently because of:

Operator precedence rules (e.g., * before +).
Parentheses for overriding precedence.
Associativity rules (left-to-right vs right-to-left).

Postfix eliminates all these issues and is evaluated with a simple stack scan.

The Shunting-Yard Algorithm (Infix to Postfix)

Developed by Edsger Dijkstra.

Data Structure needed: One stack (for operators), one output queue/string.

Algorithm INFIX_TO_POSTFIX(infix_expression)
Input:  Infix expression
Output: Postfix expression

Step 1: Create an empty STACK and empty OUTPUT string
Step 2: Scan the infix expression from LEFT to RIGHT
Step 3: For each token:

        CASE 1: Token is an OPERAND (letter or digit)
                → Append directly to OUTPUT

        CASE 2: Token is '(' (left parenthesis)
                → PUSH onto STACK

        CASE 3: Token is ')' (right parenthesis)
                → POP from STACK and append to OUTPUT
                   until '(' is found on stack
                → Discard both '(' and ')'

        CASE 4: Token is an OPERATOR (+, -, *, /, ^)
                → WHILE stack is NOT empty
                        AND top of stack is NOT '('
                        AND precedence(top of stack) >= precedence(token):
                      POP and append to OUTPUT
                → PUSH current operator onto STACK

Step 4: After scanning all tokens:
        POP all remaining operators from STACK and append to OUTPUT

Step 5: OUTPUT is the postfix expression

Precedence Function

precedence('^') = 3
precedence('*') = precedence('/') = 2
precedence('+') = precedence('-') = 1
precedence('(') = 0  (lowest priority on stack)

Detailed Conversion Examples

Example 1: `A + B * C`

Step	Token	Action	Stack	Output
1	A	Operand → Output	[]	A
2	+	Stack empty, Push +	[+]	A
3	B	Operand → Output	[+]	A B
4	*	prec()>prec(+), Push	[+, *]	A B
5	C	Operand → Output	[+, *]	A B C
6	End	Pop * → Output	[+]	A B C *
7	End	Pop + → Output	[]	A B C * +

Result: A B C * + Verification: A + BC = A + (BC*) = ABC+** ✓

Example 2: `(A + B) * C`

Step	Token	Action	Stack	Output
1	(	Push (	[(]
2	A	Operand	[(]	A
3	+	Push +	[(, +]	A
4	B	Operand	[(, +]	A B
5	)	Pop until (; pop +	[]	A B +
6	*	Push *	[*]	A B +
7	C	Operand	[*]	A B + C
8	End	Pop *	[]	A B + C *

Result: A B + C * *Verification: (A+B)C = (AB+)C = AB+C ✓

Example 3: `A * B + C / D` (Detailed Step-by-Step)

Step	Token	Action	Stack	Output
1	A	Operand	[]	A
2	*	Push * (empty stack)	[*]	A
3	B	Operand	[*]	A B
4	+	prec()>=prec(+), Pop	[]	A B *
		Push +	[+]	A B *
5	C	Operand	[+]	A B * C
6	/	prec(/)>prec(+), Push /	[+, /]	A B * C
7	D	Operand	[+, /]	A B * C D
8	End	Pop / → Output	[+]	A B * C D /
9	End	Pop + → Output	[]	A B * C D / +

Result: A B * C D / + Verification: AB + C/D = (AB) + (CD/) = AB*CD/+ ✓

Example 4: `(A + B) * (C - D)` (Parentheses on both sides)

Step	Token	Action	Stack	Output
1	(	Push (	[(]
2	A	Operand	[(]	A
3	+	Push +	[(, +]	A
4	B	Operand	[(, +]	A B
5	)	Pop until (; pop +	[]	A B +
6	*	Push *	[*]	A B +
7	(	Push (	[*, (]	A B +
8	C	Operand	[*, (]	A B + C
9	-	Push -	[*, (, -]	A B + C
10	D	Operand	[*, (, -]	A B + C D
11	)	Pop until (; pop -	[*]	A B + C D -
12	End	Pop *	[]	A B + C D - *

Result: A B + C D - *

C Program — Infix to Postfix:

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MAX 50

char stack[MAX];
int top = -1;

void push(char c)  { stack[++top] = c; }
char pop()         { return stack[top--]; }
char peek()        { return stack[top]; }
int isEmpty()      { return top == -1; }

int precedence(char op) {
    if (op == '^') return 3;
    if (op == '*' || op == '/') return 2;
    if (op == '+' || op == '-') return 1;
    return 0;
}

int isOperator(char c) {
    return (c == '+' || c == '-' || c == '*' || c == '/' || c == '^');
}

void infixToPostfix(char* infix, char* postfix) {
    int j = 0;

    for (int i = 0; infix[i] != '\0'; i++) {
        char token = infix[i];

        if (isalnum(token)) {
            // CASE 1: Operand → directly to output
            postfix[j++] = token;
            postfix[j++] = ' ';

        } else if (token == '(') {
            // CASE 2: Left parenthesis → push
            push(token);

        } else if (token == ')') {
            // CASE 3: Right parenthesis → pop until '('
            while (!isEmpty() && peek() != '(') {
                postfix[j++] = pop();
                postfix[j++] = ' ';
            }
            pop();  // Discard '('

        } else if (isOperator(token)) {
            // CASE 4: Operator
            while (!isEmpty() && precedence(peek()) >= precedence(token)) {
                postfix[j++] = pop();
                postfix[j++] = ' ';
            }
            push(token);
        }
    }

    // Pop remaining operators
    while (!isEmpty()) {
        postfix[j++] = pop();
        postfix[j++] = ' ';
    }
    postfix[j] = '\0';
}

int main() {
    char infix[MAX], postfix[MAX];

    char tests[][MAX] = {
        "A+B*C",
        "(A+B)*C",
        "A*B+C/D",
        "(A+B)*(C-D)"
    };

    for (int i = 0; i < 4; i++) {
        top = -1;  // Reset stack
        infixToPostfix(tests[i], postfix);
        printf("Infix:   %s\n", tests[i]);
        printf("Postfix: %s\n\n", postfix);
    }
    return 0;
}

Output:

Infix:   A+B*C
Postfix: A B C * +

Infix:   (A+B)*C
Postfix: A B + C *

Infix:   A*B+C/D
Postfix: A B * C D / +

Infix:   (A+B)*(C-D)
Postfix: A B + C D - *

Java Program — Infix to Postfix:

import java.util.Stack;

public class InfixToPostfix {

    static int precedence(char op) {
        if (op == '^') return 3;
        if (op == '*' || op == '/') return 2;
        if (op == '+' || op == '-') return 1;
        return 0;
    }

    static boolean isOperator(char c) {
        return "+-*/^".indexOf(c) != -1;
    }

    static String convert(String infix) {
        Stack<Character> stack = new Stack<>();
        StringBuilder postfix = new StringBuilder();

        for (char token : infix.toCharArray()) {
            if (Character.isLetterOrDigit(token)) {
                postfix.append(token).append(' ');    // Operand → output

            } else if (token == '(') {
                stack.push(token);                    // Push '('

            } else if (token == ')') {
                while (!stack.isEmpty() && stack.peek() != '(')
                    postfix.append(stack.pop()).append(' ');
                stack.pop();                          // Discard '('

            } else if (isOperator(token)) {
                while (!stack.isEmpty() && precedence(stack.peek()) >= precedence(token))
                    postfix.append(stack.pop()).append(' ');
                stack.push(token);
            }
        }
        while (!stack.isEmpty())
            postfix.append(stack.pop()).append(' ');

        return postfix.toString().trim();
    }

    public static void main(String[] args) {
        String[] tests = {"A+B*C", "(A+B)*C", "A*B+C/D", "(A+B)*(C-D)"};
        for (String infix : tests) {
            System.out.println("Infix:   " + infix);
            System.out.println("Postfix: " + convert(infix));
            System.out.println();
        }
    }
}

Chapter Summary

Key Concepts at a Glance

╔══════════════════════════════════════════════════════════════╗
║                    UNIT III: STACKS — SUMMARY                ║
╠══════════════════════════════════════════════════════════════╣
║  Definition:  Linear DS with LIFO (Last In First Out) order  ║
║  TOP:         Pointer to current topmost element             ║
║  PUSH:        Insert element (check Overflow first)          ║
║  POP:         Remove element (check Underflow first)         ║
║  PEEK:        View top without removing                      ║
║  Overflow:    PUSH on full stack (TOP == MAX-1)              ║
║  Underflow:   POP on empty stack (TOP == -1)                 ║
╠══════════════════════════════════════════════════════════════╣
║  Applications:                                               ║
║  1. Stack Frame — Function call mechanism (activation record)║
║  2. Reverse String — Push all chars, pop to reverse          ║
║  3. Postfix Evaluation — Operand→push, Operator→pop,compute  ║
║  4. Infix to Postfix — Shunting-Yard Algorithm               ║
╠══════════════════════════════════════════════════════════════╣
║  Notations:                                                  ║
║  Infix:   A + B       (operator between operands)            ║
║  Prefix:  + A B       (operator before operands)             ║
║  Postfix: A B +       (operator after operands)              ║
╠══════════════════════════════════════════════════════════════╣
║  Time Complexity:   O(1) for PUSH, POP, PEEK                 ║
║  Space Complexity:  O(n) for n elements                      ║
╚══════════════════════════════════════════════════════════════╝

📋 IMPORTANT QUESTIONS WITH ANSWERS

Section A: Short Answer (2-4 Marks)

Q1. Define stack and state its principle. Give one real-world example.

Answer:

A stack is a linear data structure in which all insertions and deletions are performed at one end called the TOP. It follows the LIFO (Last In, First Out) principle — the element inserted last is the first one to be removed.

Real-world example: A stack of plates in a cafeteria. The last plate placed on the stack is the first one taken (LIFO). You can only add or remove plates from the top.

Q2. Define the following: (a) PUSH (b) POP (c) OVERFLOW (d) UNDERFLOW

Answer:

(a) PUSH: The operation of inserting a new element onto the top of the stack. Before pushing, we check if the stack is full to avoid overflow.

(b) POP: The operation of removing and returning the topmost element from the stack. Before popping, we check if the stack is empty to avoid underflow.

(c) OVERFLOW: An error condition that occurs when a PUSH operation is attempted on a full stack (TOP = MAX - 1). No more elements can be added.

(d) UNDERFLOW: An error condition that occurs when a POP operation is attempted on an empty stack (TOP = -1). No elements exist to remove.

Q3. What is a stack frame? How is it used in function calls?

Answer:

A stack frame (or activation record) is a block of memory allocated on the call stack when a function is invoked. It stores:

Return address (where to resume after function ends)
Function parameters
Local variables
Saved CPU registers

When a function is called, its stack frame is pushed onto the call stack. When the function returns, its frame is popped. This mechanism supports:

Nested function calls
Recursion
Local variable management

Q4. Differentiate between infix, prefix, and postfix notations.

Answer:

Notation	Operator Position	Example
Infix	Between operands	A + B
Prefix	Before operands	+ A B
Postfix	After operands	A B +

Infix is human-readable but requires precedence and parentheses rules.
Postfix is computer-friendly — no parentheses needed, evaluated left-to-right using a stack.
Prefix is evaluated right-to-left using a stack.

Q5. Write the postfix equivalent of the following infix expressions: (a) A + B * C (b) (A + B) * C (c) A * B + C * D

Answer:

(a) A + B * C Postfix: A B C * + (* has higher precedence than +, so B*C is evaluated first)

(b) (A + B) * C Postfix: **A B + C *** (Parentheses force A+B first, then multiply by C)

(c) A * B + C * D Postfix: A B * C D * + (Both * have equal precedence, left-to-right: AB first, then CD, then add)

Section B: Long Answer (6-10 Marks)

Q6. Write the algorithm for PUSH and POP operations on a stack. Show the state of the stack after each operation: Push(10), Push(20), Push(30), Pop(), Push(40), Pop().

Answer:

PUSH Algorithm:

Algorithm PUSH(STACK, TOP, MAX, ITEM):
  IF TOP = MAX - 1 THEN
      Print "OVERFLOW"
  ELSE
      TOP = TOP + 1
      STACK[TOP] = ITEM
  END IF

POP Algorithm:

Algorithm POP(STACK, TOP):
  IF TOP = -1 THEN
      Print "UNDERFLOW"
  ELSE
      ITEM = STACK[TOP]
      TOP = TOP - 1
      Return ITEM
  END IF

Stack Trace:

Operation	TOP	Stack (bottom→top)	Notes
Initial	-1	[]	Empty
Push(10)	0	[10]
Push(20)	1	[10, 20]
Push(30)	2	[10, 20, 30]
Pop() → 30	1	[10, 20]	30 removed
Push(40)	2	[10, 20, 40]
Pop() → 40	1	[10, 20]	40 removed

Q7. Evaluate the following postfix expression using a stack and show all steps: 8 2 3 + - 3 *

Answer:

Expression: 8 2 3 + - 3 *

Step	Token	Action	Stack
1	8	Push	[8]
2	2	Push	[8, 2]
3	3	Push	[8, 2, 3]
4	+	Pop 3 and 2; 2+3=5; Push 5	[8, 5]
5	-	Pop 5 and 8; 8-5=3; Push 3	[3]
6	3	Push	[3, 3]
7	*	Pop 3 and 3; 3*3=9; Push 9	[9]
8	End	Final result = 9

Result = 9 Verification: 8 - (2+3) = 8 - 5 = 3; 3 × 3 = 9 ✓

Q8. Convert the following infix expression to postfix using a stack. Show all steps: (A + B) * (C - D) / E

Answer:

Operator precedences: * = / = 2, + = - = 1

Step	Token	Action	Stack	Output
1	(	Push (	[(]
2	A	Operand	[(]	A
3	+	Push +	[(, +]	A
4	B	Operand	[(, +]	A B
5	)	Pop till (; pop +	[]	A B +
6	*	Push *	[*]	A B +
7	(	Push (	[*, (]	A B +
8	C	Operand	[*, (]	A B + C
9	-	Push -	[*, (, -]	A B + C
10	D	Operand	[*, (, -]	A B + C D
11	)	Pop till (; pop -	[*]	A B + C D -
12	/	prec()=prec(/), Pop ; Push /	[/]	A B + C D - *
13	E	Operand	[/]	A B + C D - * E
14	End	Pop /	[]	A B + C D - * E /

Result: A B + C D - * E /

Another example fot infix to postfix conversion

(A+B) * (C-D) / E + F * G

Operator Precedence

Operator	Precedence
( )	Highest (Special)
* , /	2
+ , -	1

Trace Table

Step	Symbol	Action	Stack (Bottom → Top)	Postfix
1	(	Push `(`	`(`
2	A	Add operand to postfix	`(`	A
3	+	Push `+`	`(, +`	A
4	B	Add operand to postfix	`(, +`	AB
5	)	Pop until (	Empty	AB+
6	*	Push `*`	`*`	AB+
7	(	Push `(`	`*, (`	AB+
8	C	Add operand to postfix	`*, (`	AB+C
9	-	Push `-`	`*, (, -`	AB+C
10	D	Add operand to postfix	`*, (, -`	AB+CD
11	)	Pop until (	`*`	AB+CD-
12	/	Pop * (same precedence) then push /	`/`	AB+CD-*
13	E	Add operand to postfix	`/`	AB+CD-*E
14	+	Pop / (higher precedence) then push +	`+`	AB+CD-*E/
15	F	Add operand to postfix	`+`	AB+CD-*E/F
16	*	Push * (* > +)	`+, *`	AB+CD-*E/F
17	G	Add operand to postfix	`+, *`	AB+CD-*E/FG
18	End	Pop `*`	`+`	`AB+CD-E/FG`
19	End	Pop `+`	Empty	`AB+CD-E/FG+`

Final Postfix Expression

AB+CD-*E/FG*+

Section C: Practical Questions

Practical Question 1: Implement a Stack with all operations and demonstrate them.

C Program:

#include <stdio.h>
#define MAX 10

int stack[MAX], top = -1;

void push(int item) {
    if (top == MAX - 1) { printf("Overflow!\n"); return; }
    stack[++top] = item;
    printf("Pushed %d\n", item);
}

int pop() {
    if (top == -1) { printf("Underflow!\n"); return -1; }
    printf("Popped %d\n", stack[top]);
    return stack[top--];
}

void display() {
    if (top == -1) { printf("Stack Empty\n"); return; }
    printf("Stack: ");
    for (int i = top; i >= 0; i--) printf("[%d] ", stack[i]);
    printf("<-- TOP\n");
}

int main() {
    push(5); push(10); push(15); push(20);
    display();
    pop(); pop();
    display();
    printf("Top element: %d\n", stack[top]);
    return 0;
}

Expected Output:

Pushed 5
Pushed 10
Pushed 15
Pushed 20
Stack: [20] [15] [10] [5] <-- TOP
Popped 20
Popped 15
Stack: [10] [5] <-- TOP
Top element: 10

Practical Question 2: Use a stack to check if a string is a palindrome.

C Program:

#include <stdio.h>
#include <string.h>
#define MAX 100

char stack[MAX];
int top = -1;

void push(char c) { stack[++top] = c; }
char pop()        { return stack[top--]; }

int isPalindrome(char* str) {
    int len = strlen(str);

    // Push first half
    for (int i = 0; i < len / 2; i++)
        push(str[i]);

    // Compare second half with popped elements
    int start = (len % 2 == 0) ? len / 2 : len / 2 + 1;
    for (int i = start; i < len; i++) {
        if (str[i] != pop())
            return 0;  // Not a palindrome
    }
    return 1;  // Palindrome
}

int main() {
    char words[][20] = {"MADAM", "RACECAR", "HELLO", "LEVEL"};
    for (int i = 0; i < 4; i++) {
        top = -1;
        printf("%s → %s\n", words[i],
               isPalindrome(words[i]) ? "Palindrome" : "Not Palindrome");
    }
    return 0;
}

Output:

MADAM   → Palindrome
RACECAR → Palindrome
HELLO   → Not Palindrome
LEVEL   → Palindrome

Practical Question 3: Check balanced parentheses using a stack.

Java Program:

import java.util.Stack;

public class BalancedParentheses {

    static boolean isBalanced(String expr) {
        Stack<Character> stack = new Stack<>();

        for (char c : expr.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);                    // Push opening bracket
            } else if (c == ')' || c == ']' || c == '}') {
                if (stack.isEmpty()) return false; // No matching opener

                char top = stack.pop();
                if ((c == ')' && top != '(') ||
                    (c == ']' && top != '[') ||
                    (c == '}' && top != '{'))
                    return false;                 // Mismatch
            }
        }
        return stack.isEmpty();                   // Should be empty at end
    }

    public static void main(String[] args) {
        String[] tests = {"(A+B)", "{[A+B]*C}", "((A+B)", "{A+[B*C)}"};
        for (String t : tests)
            System.out.println(t + " → " + (isBalanced(t) ? "Balanced" : "Not Balanced"));
    }
}

Output:

(A+B)       → Balanced
{[A+B]*C}   → Balanced
((A+B)      → Not Balanced
{A+[B*C)}   → Not Balanced

Practical Question 4: Full infix to postfix converter with multi-digit number support.

Java Program:

import java.util.Stack;

public class FullConverter {

    static int prec(char op) {
        if (op == '^') return 3;
        if (op == '*' || op == '/') return 2;
        if (op == '+' || op == '-') return 1;
        return -1;
    }

    static String toPostfix(String infix) {
        Stack<Character> st = new Stack<>();
        StringBuilder out = new StringBuilder();

        for (int i = 0; i < infix.length(); i++) {
            char c = infix.charAt(i);

            if (Character.isLetterOrDigit(c)) {
                out.append(c).append(' ');
            } else if (c == '(') {
                st.push(c);
            } else if (c == ')') {
                while (!st.isEmpty() && st.peek() != '(')
                    out.append(st.pop()).append(' ');
                st.pop();
            } else {
                while (!st.isEmpty() && prec(st.peek()) >= prec(c))
                    out.append(st.pop()).append(' ');
                st.push(c);
            }
        }
        while (!st.isEmpty()) out.append(st.pop()).append(' ');
        return out.toString().trim();
    }

    public static void main(String[] args) {
        String[] exprs = {
            "A+B*C",
            "(A+B)*C",
            "A*B+C/D",
            "(A+B)*(C-D)/E",
            "A^B^C"
        };
        System.out.printf("%-25s %s%n", "Infix", "Postfix");
        System.out.println("-".repeat(45));
        for (String e : exprs)
            System.out.printf("%-25s %s%n", e, toPostfix(e));
    }
}

Output:

Infix                     Postfix
---------------------------------------------
A+B*C                     A B C * +
(A+B)*C                   A B + C *
A*B+C/D                   A B * C D / +
(A+B)*(C-D)/E             A B + C D - * E /
A^B^C                     A B C ^ ^

Practical Question 5: Evaluate postfix expression with two-digit numbers.

C Program:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX 50

float stack[MAX];
int top = -1;

void push(float v) { stack[++top] = v; }
float pop()        { return stack[top--]; }

float evaluatePostfix(char tokens[][10], int count) {
    for (int i = 0; i < count; i++) {
        char* token = tokens[i];
        if (isdigit(token[0])) {
            push(atof(token));
        } else {
            float b = pop(), a = pop();
            switch (token[0]) {
                case '+': push(a + b); break;
                case '-': push(a - b); break;
                case '*': push(a * b); break;
                case '/': push(a / b); break;
            }
        }
    }
    return pop();
}

int main() {
    // Expression: 15 7 1 1 + - / 3 * 2 1 1 + + -
    // Infix:      15 / (7 - (1 + 1)) * 3 - (2 + (1 + 1))
    // Result:     5
    char tokens[][10] = {"15","7","1","1","+","-","/","3","*","2","1","1","+","+","-"};
    int count = 15;

    printf("Result: %.2f\n", evaluatePostfix(tokens, count));
    return 0;
}
// Output: Result: 5.00

📌 Possible Exam Questions Table

#	Question	Expected Marks
1	Define stack and LIFO with example	2
2	List and explain all stack operations	4
3	Write PUSH and POP algorithms	5
4	Implement complete stack in C or Java	8
5	What is stack overflow and underflow?	2
6	Explain stack frame with diagram	4
7	Define infix, prefix, postfix with examples	4
8	Convert given infix to postfix (step-by-step)	6-8
9	Evaluate given postfix expression with steps	6
10	Write C/Java program to reverse a string using stack	6
11	Write C/Java program for infix to postfix conversion	10
12	Write program for postfix evaluation	8
13	List applications of stack with brief explanation	5
14	Compare infix and postfix notation	3
15	Write algorithm to check balanced parentheses	6

Lab Question

Describe the Stack data structure with its array representation and working principle, write the algorithms for PUSH and POP operations, and implement a Java program using Stack (array or built-in) to reverse a string, check balanced parentheses, convert an infix expression to postfix, and evaluate a postfix expression, and also convert the given infix expression into postfix form showing step-by-step process:

(A + B) * (C - D) / E + F * G

Part - 3 Stack, Data Structure & Algorithm

📘 Unit III: Stacks

Complete Exam & Teaching Notes | BCA / BIT / MCA / BSc.CSIT

Full Theory + Terminology + Algorithms + Applications + Programs + Q&A

3.1 Introduction to Stack

What is a Stack?

Why Stack?

Stack as an Abstract Data Type (ADT)

Visual Representation

3.2 Operations on Stack

Operation 1: PUSH

Operation 2: POP

Operation 3: PEEK / TOP

Operation 4: isEmpty

Operation 5: isFull

Operation 6: size

3.3 Stack Terminology

LIFO Explained

3.4 Algorithms for PUSH and POP

Stack Implementation — Array-Based

3.4.1 Algorithm for PUSH

3.4.2 Algorithm for POP

3.4.3 Algorithm for PEEK

Complete Stack Program in C

Complete Stack Program in Java

3.5 Stack Applications

3.5.1 Stack Frame (Function Call Stack)

What is a Stack Frame?

Structure of a Stack Frame

Example

Recursive Function Call Stack

3.5.2 Reverse a String using Stack

Concept

3.5.3 Notation Systems — Prefix, Infix, Postfix

What is a Notation?

Three Notations

Examples

Why Postfix?

Operator Precedence (for conversions)

3.5.4 Evaluation of Postfix Expression

Algorithm

Detailed Example 1: Evaluate 5 3 + 2 *

Detailed Example 2: Evaluate 6 2 3 + - 3 8 2 / + *

3.6 Algorithm for Converting Infix Expression to Postfix

Why Convert?

The Shunting-Yard Algorithm (Infix to Postfix)

Precedence Function

Detailed Conversion Examples

Example 1: A + B * C

Example 2: (A + B) * C

Example 3: A * B + C / D (Detailed Step-by-Step)

Example 4: (A + B) * (C - D) (Parentheses on both sides)

Chapter Summary

Key Concepts at a Glance

📋 IMPORTANT QUESTIONS WITH ANSWERS

Section A: Short Answer (2-4 Marks)

Section B: Long Answer (6-10 Marks)

Another example fot infix to postfix conversion

Operator Precedence

Trace Table

Final Postfix Expression

Section C: Practical Questions

Practical Question 1: Implement a Stack with all operations and demonstrate them.

Practical Question 2: Use a stack to check if a string is a palindrome.

Practical Question 3: Check balanced parentheses using a stack.

Practical Question 4: Full infix to postfix converter with multi-digit number support.

Practical Question 5: Evaluate postfix expression with two-digit numbers.

📌 Possible Exam Questions Table

Lab Question

(A + B) * (C - D) / E + F * G

Detailed Example 1: Evaluate `5 3 + 2 *`

Detailed Example 2: Evaluate `6 2 3 + - 3 8 2 / + *`

Example 1: `A + B * C`

Example 2: `(A + B) * C`

Example 3: `A * B + C / D` (Detailed Step-by-Step)

Example 4: `(A + B) * (C - D)` (Parentheses on both sides)