Chapter 6: Stacks

Introduction

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle: the last element added is the first one removed. Think of a stack of plates—you add plates to the top and remove them from the top. This simple yet powerful abstraction appears throughout computer science, from function calls to expression evaluation to undo mechanisms.

Why This Matters

Stacks are fundamental to computing:

Function calls: Call stack manages function execution
Expression evaluation: Convert and evaluate mathematical expressions
Backtracking: Undo operations, maze solving, game state
Syntax parsing: Compilers check balanced parentheses
Browser history: Back button navigation
Memory management: Stack vs heap allocation

Understanding stacks teaches:

LIFO ordering and its applications
How recursion works under the hood
Efficient implementation trade-offs
Foundation for more complex structures

How to Study This Chapter

Visualize operations - Draw stack state after each push/pop
Implement both ways - Array-based and linked-list-based
Solve problems - Practice with expression evaluation, parentheses matching
Trace execution - Follow stack changes step by step
Compare implementations - Understand trade-offs

Stack Operations

Core Operations

push(x) - Add element to top - O(1)
pop() - Remove and return top element - O(1)
peek()/top() - View top element without removing - O(1)
isEmpty() - Check if stack is empty - O(1)
size() - Get number of elements - O(1)

Visualization

Push operations:        Pop operations:

push(10):  [10]        pop(): [10, 20, 30]
push(20):  [10, 20]           [10, 20]  (returns 30)
push(30):  [10, 20, 30]       [10]      (returns 20)
           └─ TOP              └─ TOP

Array-Based Stack Implementation

C Implementation

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_SIZE 100

typedef struct {
    int items[MAX_SIZE];
    int top;
} Stack;

void initStack(Stack* s) {
    s->top = -1;
}

bool isEmpty(Stack* s) {
    return s->top == -1;
}

bool isFull(Stack* s) {
    return s->top == MAX_SIZE - 1;
}

void push(Stack* s, int value) {
    if (isFull(s)) {
        printf("Stack Overflow\n");
        return;
    }
    s->items[++(s->top)] = value;
}

int pop(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack Underflow\n");
        return -1;
    }
    return s->items[(s->top)--];
}

int peek(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack is empty\n");
        return -1;
    }
    return s->items[s->top];
}

int size(Stack* s) {
    return s->top + 1;
}

void display(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack is empty\n");
        return;
    }
    printf("Stack: ");
    for (int i = 0; i <= s->top; i++) {
        printf("%d ", s->items[i]);
    }
    printf("(top: %d)\n", s->items[s->top]);
}

int main() {
    Stack s;
    initStack(&s);

    push(&s, 10);
    push(&s, 20);
    push(&s, 30);

    display(&s);  // Stack: 10 20 30 (top: 30)

    printf("Popped: %d\n", pop(&s));  // 30
    printf("Peek: %d\n", peek(&s));   // 20

    display(&s);  // Stack: 10 20 (top: 20)

    return 0;
}

C++ Implementation

#include <iostream>
#include <vector>
using namespace std;

class Stack {
private:
    vector<int> items;

public:
    void push(int value) {
        items.push_back(value);
    }

    int pop() {
        if (isEmpty()) {
            throw runtime_error("Stack Underflow");
        }
        int value = items.back();
        items.pop_back();
        return value;
    }

    int peek() {
        if (isEmpty()) {
            throw runtime_error("Stack is empty");
        }
        return items.back();
    }

    bool isEmpty() {
        return items.empty();
    }

    int size() {
        return items.size();
    }

    void display() {
        if (isEmpty()) {
            cout << "Stack is empty" << endl;
            return;
        }
        cout << "Stack: ";
        for (int item : items) {
            cout << item << " ";
        }
        cout << "(top: " << items.back() << ")" << endl;
    }
};

int main() {
    Stack s;

    s.push(10);
    s.push(20);
    s.push(30);

    s.display();  // Stack: 10 20 30 (top: 30)

    cout << "Popped: " << s.pop() << endl;  // 30
    cout << "Peek: " << s.peek() << endl;   // 20

    s.display();  // Stack: 10 20 (top: 20)

    return 0;
}

Java Implementation

import java.util.ArrayList;
import java.util.EmptyStackException;

class Stack {
    private ArrayList<Integer> items;

    public Stack() {
        items = new ArrayList<>();
    }

    public void push(int value) {
        items.add(value);
    }

    public int pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return items.remove(items.size() - 1);
    }

    public int peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return items.get(items.size() - 1);
    }

    public boolean isEmpty() {
        return items.isEmpty();
    }

    public int size() {
        return items.size();
    }

    public void display() {
        if (isEmpty()) {
            System.out.println("Stack is empty");
            return;
        }
        System.out.print("Stack: ");
        for (int item : items) {
            System.out.print(item + " ");
        }
        System.out.println("(top: " + peek() + ")");
    }

    public static void main(String[] args) {
        Stack s = new Stack();

        s.push(10);
        s.push(20);
        s.push(30);

        s.display();  // Stack: 10 20 30 (top: 30)

        System.out.println("Popped: " + s.pop());  // 30
        System.out.println("Peek: " + s.peek());   // 20

        s.display();  // Stack: 10 20 (top: 20)
    }
}

Linked List-Based Stack Implementation

C Implementation

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct {
    Node* top;
    int size;
} Stack;

void initStack(Stack* s) {
    s->top = NULL;
    s->size = 0;
}

bool isEmpty(Stack* s) {
    return s->top == NULL;
}

void push(Stack* s, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = s->top;
    s->top = newNode;
    s->size++;
}

int pop(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack Underflow\n");
        return -1;
    }
    Node* temp = s->top;
    int value = temp->data;
    s->top = s->top->next;
    free(temp);
    s->size--;
    return value;
}

int peek(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack is empty\n");
        return -1;
    }
    return s->top->data;
}

int getSize(Stack* s) {
    return s->size;
}

int main() {
    Stack s;
    initStack(&s);

    push(&s, 10);
    push(&s, 20);
    push(&s, 30);

    printf("Size: %d\n", getSize(&s));
    printf("Top: %d\n", peek(&s));
    printf("Popped: %d\n", pop(&s));
    printf("New top: %d\n", peek(&s));

    return 0;
}

Stack Applications

1. Balanced Parentheses Checker

Problem: Check if parentheses/brackets are balanced.

Algorithm:

For each character:
- If opening bracket, push to stack
- If closing bracket, pop and check if it matches
Stack should be empty at the end

C Implementation:

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool isMatchingPair(char open, char close) {
    return (open == '(' && close == ')') ||
           (open == '{' && close == '}') ||
           (open == '[' && close == ']');
}

bool areParenthesesBalanced(const char* expr) {
    char stack[100];
    int top = -1;

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

        if (ch == '(' || ch == '{' || ch == '[') {
            stack[++top] = ch;
        }
        else if (ch == ')' || ch == '}' || ch == ']') {
            if (top == -1 || !isMatchingPair(stack[top], ch)) {
                return false;
            }
            top--;
        }
    }

    return top == -1;
}

int main() {
    printf("%d\n", areParenthesesBalanced("({[]})"));     // 1 (true)
    printf("%d\n", areParenthesesBalanced("([)]"));       // 0 (false)
    printf("%d\n", areParenthesesBalanced("{[}"));        // 0 (false)
    printf("%d\n", areParenthesesBalanced("((()))"));     // 1 (true)

    return 0;
}

Test Cases:

"()" -> true
"()[]{}" -> true
"(]" -> false
"([)]" -> false
"{[]}" -> true

2. Infix to Postfix Conversion

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

Algorithm:

Scan expression left to right
If operand, add to output
If operator, pop operators with higher/equal precedence, then push
If '(', push to stack
If ')', pop until '('

C Implementation:

#include <stdio.h>
#include <string.h>
#include <ctype.h>

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

void infixToPostfix(const char* infix, char* postfix) {
    char stack[100];
    int top = -1;
    int k = 0;

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

        if (isalnum(ch)) {
            postfix[k++] = ch;
        }
        else if (ch == '(') {
            stack[++top] = ch;
        }
        else if (ch == ')') {
            while (top != -1 && stack[top] != '(') {
                postfix[k++] = stack[top--];
            }
            top--;  // Remove '('
        }
        else {
            while (top != -1 && precedence(stack[top]) >= precedence(ch)) {
                postfix[k++] = stack[top--];
            }
            stack[++top] = ch;
        }
    }

    while (top != -1) {
        postfix[k++] = stack[top--];
    }

    postfix[k] = '\0';
}

int main() {
    char postfix[100];

    infixToPostfix("A+B*C", postfix);
    printf("%s\n", postfix);  // ABC*+

    infixToPostfix("(A+B)*C", postfix);
    printf("%s\n", postfix);  // AB+C*

    infixToPostfix("A+B*C-D", postfix);
    printf("%s\n", postfix);  // ABC*+D-

    return 0;
}

3. Postfix Expression Evaluation

Example: 2 3 + 5 * = (2 + 3) * 5 = 25

Algorithm:

Scan expression left to right
If operand, push to stack
If operator, pop two operands, apply operator, push result
Final result is top of stack

C Implementation:

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>

int evaluatePostfix(const char* expr) {
    int stack[100];
    int top = -1;

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

        if (ch == ' ') continue;

        if (isdigit(ch)) {
            stack[++top] = ch - '0';
        }
        else {
            int val2 = stack[top--];
            int val1 = stack[top--];

            switch (ch) {
                case '+': stack[++top] = val1 + val2; break;
                case '-': stack[++top] = val1 - val2; break;
                case '*': stack[++top] = val1 * val2; break;
                case '/': stack[++top] = val1 / val2; break;
            }
        }
    }

    return stack[top];
}

int main() {
    printf("%d\n", evaluatePostfix("23+5*"));     // 25
    printf("%d\n", evaluatePostfix("23*54*+"));   // 26
    printf("%d\n", evaluatePostfix("82/53*+"));   // 19

    return 0;
}

4. Next Greater Element

Problem: For each element, find the next greater element to its right.

Example: [4, 5, 2, 10] → [5, 10, 10, -1]

C Implementation:

void nextGreaterElement(int arr[], int n, int result[]) {
    int stack[100];
    int top = -1;

    // Traverse from right to left
    for (int i = n - 1; i >= 0; i--) {
        // Pop elements smaller than current
        while (top != -1 && stack[top] <= arr[i]) {
            top--;
        }

        result[i] = (top == -1) ? -1 : stack[top];

        stack[++top] = arr[i];
    }
}

int main() {
    int arr[] = {4, 5, 2, 10};
    int n = 4;
    int result[4];

    nextGreaterElement(arr, n, result);

    for (int i = 0; i < n; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");  // Output: 5 10 10 -1

    return 0;
}

5. Stock Span Problem

Problem: Calculate stock span—number of consecutive days before current day with price ≤ current price.

Example:

Price: [100, 80, 60, 70, 60, 75, 85]
Span:  [1,   1,  1,  2,  1,  4,  6]

C Implementation:

void calculateSpan(int price[], int n, int span[]) {
    int stack[100];
    int top = -1;

    stack[++top] = 0;
    span[0] = 1;

    for (int i = 1; i < n; i++) {
        while (top != -1 && price[stack[top]] <= price[i]) {
            top--;
        }

        span[i] = (top == -1) ? (i + 1) : (i - stack[top]);

        stack[++top] = i;
    }
}

int main() {
    int price[] = {100, 80, 60, 70, 60, 75, 85};
    int n = 7;
    int span[7];

    calculateSpan(price, n, span);

    for (int i = 0; i < n; i++) {
        printf("%d ", span[i]);
    }
    printf("\n");  // Output: 1 1 1 2 1 4 6

    return 0;
}

Complexity Analysis

Operation	Array-Based	Linked List-Based
Push	O(1)	O(1)
Pop	O(1)	O(1)
Peek	O(1)	O(1)
isEmpty	O(1)	O(1)
Space	O(n), fixed capacity	O(n), dynamic
Cache locality	Better	Worse

Array vs Linked List Stack

Array-Based:

✓ Better cache performance
✓ Simple implementation
✗ Fixed size (or reallocation needed)
✗ Wasted memory if not full

Linked List-Based:

✓ Dynamic size
✓ No wasted space
✗ Extra memory for pointers
✗ Worse cache performance

Common Mistakes

Not checking underflow - Popping from empty stack
Not checking overflow - Pushing to full array-based stack
Memory leaks - Not freeing nodes in linked list stack
Wrong index - Off-by-one errors with top pointer
Modifying while iterating - Causes unexpected behavior
Not handling empty stack - Peek on empty stack
Parentheses mismatch - Not checking all bracket types

Debugging Tips

Visualize stack state - Draw stack after each operation
Print top element - Verify correct value at top
Check size - Ensure size matches expected
Test edge cases - Empty stack, single element, full stack
Trace operations - Follow push/pop sequence
Use assertions - Verify preconditions
Test with examples - Walk through manually first

Mini Exercises

Implement getMin() that returns minimum element in O(1)
Reverse a string using a stack
Implement two stacks using one array
Sort a stack using another stack
Evaluate prefix expressions
Check for duplicate parentheses
Implement browser back/forward using stacks
Find maximum in each window of size k
Simplify Unix-style file paths
Implement stack with middle element operations

Review Questions

Why are push and pop O(1) operations?
How does the call stack relate to recursion?
What's the difference between infix, postfix, and prefix notation?
When should you use an array-based vs linked-list-based stack?
How would you implement getMin() in O(1) time?

Reference Checklist

By the end of this chapter, you should be able to:

Implement stack using arrays and linked lists
Understand LIFO principle
Check balanced parentheses
Convert infix to postfix
Evaluate postfix expressions
Solve next greater element problems
Apply stacks to real-world problems
Analyze time and space complexity

Next Steps

Now that you understand stacks (LIFO), Chapter 7 explores queues—a First-In-First-Out (FIFO) data structure. You'll learn queue implementations, circular queues, priority queues, and applications like task scheduling and breadth-first search.

Key Takeaway: Stacks implement LIFO ordering with O(1) operations. They're fundamental to recursion, expression evaluation, and backtracking. Understanding when and how to use stacks is essential for many algorithmic problems.