Stack in C - Implementation & Applications

Stack Basics

A stack is a linear data structure that follows the LIFO (Last In First Out) principle. The last element added is the first one to be removed. Think of a stack of plates - you can only add or remove from the top.

Stack Operations

Push - Add element to top of stack
Pop - Remove and return element from top
Peek/Top - View top element without removing
IsEmpty - Check if stack is empty
IsFull - Check if stack is full (array implementation)

📊 Stack Visualization (LIFO)

Operation    Stack State          Description
---------    -----------          -----------
Push(10)     | 10 |  ← TOP       Add 10 to empty stack
Push(20)     | 20 |  ← TOP       Add 20 on top
             | 10 |
Push(30)     | 30 |  ← TOP       Add 30 on top
             | 20 |
             | 10 |
Pop()        | 20 |  ← TOP       Remove 30 (returns 30)
             | 10 |
Pop()        | 10 |  ← TOP       Remove 20 (returns 20)

Array Implementation

stack_array.c

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

typedef struct {
    int arr[MAX];
    int top;
} Stack;

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

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

// Check if full
bool isFull(Stack* s) {
    return s->top == MAX - 1;
}

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

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

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

// Display stack
void display(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack is empty!\n");
        return;
    }
    printf("Stack elements (top to bottom): ");
    for (int i = s->top; i >= 0; i--)
        printf("%d ", s->arr[i]);
    printf("\n");
}

int main() {
    Stack s;
    initStack(&s);
    
    int choice, value;
    
    while (1) {
        printf("\n--- Stack Operations ---\n");
        printf("1. Push\n2. Pop\n3. Peek\n4. Display\n5. Exit\n");
        printf("Enter choice: ");
        scanf("%d", &choice);
        
        switch (choice) {
            case 1:
                printf("Enter value: ");
                scanf("%d", &value);
                push(&s, value);
                break;
            case 2:
                value = pop(&s);
                if (value != -1)
                    printf("Popped: %d\n", value);
                break;
            case 3:
                value = peek(&s);
                if (value != -1)
                    printf("Top element: %d\n", value);
                break;
            case 4:
                display(&s);
                break;
            case 5:
                return 0;
            default:
                printf("Invalid choice!\n");
        }
    }
    return 0;
}

Complexity Analysis

Operation	Time Complexity	Space Complexity
Push	O(1)	O(1)
Pop	O(1)	O(1)
Peek	O(1)	O(1)
IsEmpty	O(1)	O(1)

Linked List Implementation

stack_linked_list.c

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

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

typedef struct {
    Node* top;
} StackLL;

// Initialize stack
void initStack(StackLL* s) {
    s->top = NULL;
}

// Check if empty
bool isEmpty(StackLL* s) {
    return s->top == NULL;
}

// Push element
void push(StackLL* s, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        return;
    }
    newNode->data = value;
    newNode->next = s->top;
    s->top = newNode;
}

// Pop element
int pop(StackLL* 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);
    return value;
}

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

// Display stack
void display(StackLL* s) {
    if (isEmpty(s)) {
        printf("Stack is empty!\n");
        return;
    }
    printf("Stack elements (top to bottom): ");
    Node* temp = s->top;
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int main() {
    StackLL s;
    initStack(&s);
    
    push(&s, 10);
    push(&s, 20);
    push(&s, 30);
    display(&s);
    
    printf("Top element: %d\n", peek(&s));
    printf("Popped: %d\n", pop(&s));
    display(&s);
    
    return 0;
}

Expression Notations

Different ways to write arithmetic expressions:

📝 Types of Notations

Type	Format	Example (A + B)	Operator Position
Infix	operand operator operand	A + B	Between operands
Prefix	operator operand operand	+ A B	Before operands
Postfix	operand operand operator	A B +	After operands

Why Convert Expressions?

Computer evaluation: Postfix/Prefix are easier for computers to evaluate (no parentheses needed)
No ambiguity: Postfix/Prefix have unique representations, no need for precedence rules
Stack-friendly: Can be evaluated using a single stack

Infix to Postfix Conversion

🔄 Algorithm Steps

Scan the infix expression from left to right
If operand → add to output
If '(' → push to stack
If ')' → pop and add to output until '(' is found
If operator → pop from stack and add to output while operators with higher or equal precedence are on top, then push current operator
After scanning, pop all remaining operators from stack

📊 Operator Precedence

Operator	Precedence	Associativity
^ (Exponent)	3	Right to Left
* , / , %	2	Left to Right
+ , -	1	Left to Right

infix_to_postfix.c

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

#define MAX 100

typedef struct {
    char arr[MAX];
    int top;
} Stack;

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

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

void push(Stack* s, char c) {
    s->arr[++s->top] = c;
}

char pop(Stack* s) {
    return s->arr[s->top--];
}

char peek(Stack* s) {
    return s->arr[s->top];
}

int precedence(char op) {
    switch(op) {
        case '^': return 3;
        case '*':
        case '/':
        case '%': return 2;
        case '+':
        case '-': return 1;
        default: return 0;
    }
}

int isRightAssociative(char op) {
    return op == '^';
}

void infixToPostfix(char* infix, char* postfix) {
    Stack s;
    init(&s);
    int i, j = 0;
    
    for (i = 0; infix[i] != '\0'; i++) {
        char c = infix[i];
        
        // Operand (letter or digit)
        if (isalnum(c)) {
            postfix[j++] = c;
        }
        // Opening parenthesis
        else if (c == '(') {
            push(&s, c);
        }
        // Closing parenthesis
        else if (c == ')') {
            while (!isEmpty(&s) && peek(&s) != '(')
                postfix[j++] = pop(&s);
            pop(&s); // Remove '('
        }
        // Operator
        else {
            while (!isEmpty(&s) && peek(&s) != '(' &&
                   (precedence(peek(&s)) > precedence(c) ||
                    (precedence(peek(&s)) == precedence(c) && !isRightAssociative(c)))) {
                postfix[j++] = pop(&s);
            }
            push(&s, c);
        }
    }
    
    // Pop remaining operators
    while (!isEmpty(&s))
        postfix[j++] = pop(&s);
    
    postfix[j] = '\0';
}

int main() {
    char infix[MAX], postfix[MAX];
    
    printf("Enter infix expression: ");
    scanf("%s", infix);
    
    infixToPostfix(infix, postfix);
    
    printf("Postfix expression: %s\n", postfix);
    
    return 0;
}

Example Walkthrough

Expression: A + B * C

Step	Symbol	Stack	Output
1	A	Empty	A
2	+	+	A
3	B	+	AB
4	*	+*	AB
5	C	+*	ABC
6	End	Empty	ABC*+

Infix to Prefix Conversion

🔄 Algorithm Steps

Reverse the infix expression
Swap '(' with ')' and vice versa
Convert to postfix using the standard algorithm
Reverse the result to get prefix

infix_to_prefix.c

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

#define MAX 100

typedef struct {
    char arr[MAX];
    int top;
} Stack;

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

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

void push(Stack* s, char c) {
    s->arr[++s->top] = c;
}

char pop(Stack* s) {
    return s->arr[s->top--];
}

char peek(Stack* s) {
    return s->arr[s->top];
}

int precedence(char op) {
    switch(op) {
        case '^': return 3;
        case '*':
        case '/':
        case '%': return 2;
        case '+':
        case '-': return 1;
        default: return 0;
    }
}

void reverse(char* str) {
    int len = strlen(str);
    for (int i = 0; i < len / 2; i++) {
        char temp = str[i];
        str[i] = str[len - i - 1];
        str[len - i - 1] = temp;
    }
}

void swapParentheses(char* str) {
    for (int i = 0; str[i] != '\0'; i++) {
        if (str[i] == '(') str[i] = ')';
        else if (str[i] == ')') str[i] = '(';
    }
}

void infixToPostfix(char* infix, char* postfix) {
    Stack s;
    init(&s);
    int i, j = 0;
    
    for (i = 0; infix[i] != '\0'; i++) {
        char c = infix[i];
        
        if (isalnum(c)) {
            postfix[j++] = c;
        }
        else if (c == '(') {
            push(&s, c);
        }
        else if (c == ')') {
            while (!isEmpty(&s) && peek(&s) != '(')
                postfix[j++] = pop(&s);
            pop(&s);
        }
        else {
            while (!isEmpty(&s) && peek(&s) != '(' &&
                   precedence(peek(&s)) > precedence(c)) {
                postfix[j++] = pop(&s);
            }
            push(&s, c);
        }
    }
    
    while (!isEmpty(&s))
        postfix[j++] = pop(&s);
    
    postfix[j] = '\0';
}

void infixToPrefix(char* infix, char* prefix) {
    char temp[MAX];
    strcpy(temp, infix);
    
    reverse(temp);
    swapParentheses(temp);
    
    char postfix[MAX];
    infixToPostfix(temp, postfix);
    
    reverse(postfix);
    strcpy(prefix, postfix);
}

int main() {
    char infix[MAX], prefix[MAX];
    
    printf("Enter infix expression: ");
    scanf("%s", infix);
    
    infixToPrefix(infix, prefix);
    
    printf("Prefix expression: %s\n", prefix);
    
    return 0;
}

Example

Infix: A + B * C

Step 1 - Reverse: C * B + A

Step 2 - Postfix: CB*A+

Step 3 - Reverse: +A*BC

Prefix: + A * B C

Postfix Expression Evaluation

🔄 Algorithm Steps

Create a stack for operands
Scan the postfix expression from left to right
If operand → push to stack
If operator → pop two operands, apply operator, push result
Final result is the only element left in stack

postfix_evaluation.c

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

#define MAX 100

typedef struct {
    int arr[MAX];
    int top;
} Stack;

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

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

void push(Stack* s, int val) {
    s->arr[++s->top] = val;
}

int pop(Stack* s) {
    return s->arr[s->top--];
}

int evaluatePostfix(char* expr) {
    Stack s;
    init(&s);
    
    for (int i = 0; expr[i] != '\0'; i++) {
        char c = expr[i];
        
        // Skip spaces
        if (c == ' ') continue;
        
        // Operand (single digit)
        if (isdigit(c)) {
            push(&s, c - '0');
        }
        // Operator
        else {
            int b = pop(&s);  // Second operand
            int a = pop(&s);  // First operand
            int result;
            
            switch(c) {
                case '+': result = a + b; break;
                case '-': result = a - b; break;
                case '*': result = a * b; break;
                case '/': 
                    if (b == 0) {
                        printf("Division by zero!\n");
                        return -1;
                    }
                    result = a / b; 
                    break;
                case '%': result = a % b; break;
                case '^': result = (int)pow(a, b); break;
                default: 
                    printf("Invalid operator: %c\n", c);
                    return -1;
            }
            push(&s, result);
        }
    }
    
    return pop(&s);
}

int main() {
    char expr[MAX];
    
    printf("Enter postfix expression (single digits): ");
    scanf("%s", expr);
    
    int result = evaluatePostfix(expr);
    printf("Result: %d\n", result);
    
    return 0;
}

Example Walkthrough

Expression: 53+82-* (which is (5+3)*(8-2))

Step	Symbol	Action	Stack
1	5	Push	5
2	3	Push	5, 3
3	+	Pop 3,5; Push 8	8
4	8	Push	8, 8
5	2	Push	8, 8, 2
6	-	Pop 2,8; Push 6	8, 6
7	*	Pop 6,8; Push 48	48

Result: 48

Tower of Hanoi

🎯 Problem Statement

Move n disks from source peg to destination peg using auxiliary peg, following rules:

Only one disk can be moved at a time
Only the top disk can be moved
No larger disk may be placed on top of a smaller disk

🧠 Recursive Approach

To move n disks from source to destination:

Move n-1 disks from source to auxiliary peg
Move the nth (largest) disk from source to destination
Move n-1 disks from auxiliary to destination peg

tower_of_hanoi.c

#include <stdio.h>

// Recursive Tower of Hanoi
void towerOfHanoi(int n, char source, char auxiliary, char destination) {
    // Base case: only one disk
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", source, destination);
        return;
    }
    
    // Move n-1 disks from source to auxiliary
    towerOfHanoi(n - 1, source, destination, auxiliary);
    
    // Move nth disk from source to destination
    printf("Move disk %d from %c to %c\n", n, source, destination);
    
    // Move n-1 disks from auxiliary to destination
    towerOfHanoi(n - 1, auxiliary, source, destination);
}

int main() {
    int n;
    
    printf("Enter number of disks: ");
    scanf("%d", &n);
    
    printf("\nTower of Hanoi Solution for %d disks:\n", n);
    printf("========================================\n");
    
    towerOfHanoi(n, 'A', 'B', 'C');
    
    printf("\nTotal moves required: %d\n", (1 << n) - 1);
    
    return 0;
}

Example Output (3 disks)

Tower of Hanoi Solution for 3 disks:
========================================
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Total moves required: 7

Complexity Analysis

Recurrence	T(n) = 2T(n-1) + 1
Time Complexity	O(2ⁿ)
Space Complexity	O(n) - recursion stack
Minimum Moves	2ⁿ - 1

Balanced Parentheses

🔄 Algorithm

Create an empty stack
Scan the expression
If opening bracket → push to stack
If closing bracket → pop from stack and check if it matches
Expression is balanced if stack is empty at the end

balanced_parentheses.c

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

#define MAX 100

typedef struct {
    char arr[MAX];
    int top;
} Stack;

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

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

void push(Stack* s, char c) {
    s->arr[++s->top] = c;
}

char pop(Stack* s) {
    return s->arr[s->top--];
}

bool isMatchingPair(char opening, char closing) {
    if (opening == '(' && closing == ')') return true;
    if (opening == '[' && closing == ']') return true;
    if (opening == '{' && closing == '}') return true;
    return false;
}

bool isBalanced(char* expr) {
    Stack s;
    init(&s);
    
    for (int i = 0; expr[i] != '\0'; i++) {
        char c = expr[i];
        
        // Opening bracket
        if (c == '(' || c == '[' || c == '{') {
            push(&s, c);
        }
        // Closing bracket
        else if (c == ')' || c == ']' || c == '}') {
            if (isEmpty(&s))
                return false;
            
            char top = pop(&s);
            if (!isMatchingPair(top, c))
                return false;
        }
    }
    
    return isEmpty(&s);
}

int main() {
    char expr[MAX];
    
    printf("Enter expression: ");
    scanf("%s", expr);
    
    if (isBalanced(expr))
        printf("Balanced!\n");
    else
        printf("Not Balanced!\n");
    
    return 0;
}

Applications of Stack

🔄 Expression Conversion

Infix to Postfix, Infix to Prefix conversion using operator precedence

📊 Expression Evaluation

Evaluating postfix and prefix expressions without parentheses

🎯 Tower of Hanoi

Classic recursive problem solved using stack concept

📋 Function Calls

Managing function call stack in programming languages

↩️ Undo Operations

Browser history, text editor undo functionality

🔍 DFS Algorithm

Depth First Search in graph traversal

✅ Syntax Checking

Balanced parentheses in compilers and IDEs

🔙 Backtracking

Maze solving, puzzle solutions using stack

Summary Table

Topic	Key Concept	Time Complexity
Stack Operations	Push, Pop, Peek - LIFO principle	O(1) for all
Infix to Postfix	Operator precedence and stack	O(n)
Infix to Prefix	Reverse → Postfix → Reverse	O(n)
Postfix Evaluation	Stack of operands	O(n)
Tower of Hanoi	Recursive divide and conquer	O(2ⁿ)
Parentheses Matching	Stack to track opening brackets	O(n)