October 17, 2026

Stack in C — Complete DSA Tutorial with Examples and Programs

Course: Param Classes — Data Structures & Algorithms in C
Module: 06 — Stack

SEO Details

SEO Title: Stack in C: Complete Tutorial with Push, Pop, LIFO & Expression Evaluation

URL Slug: /stack-in-c/

Meta Description: Learn Stack in C with examples and programs. Understand LIFO, stack implementation using arrays and linked lists, Push, Pop, Peek, overflow, underflow, infix, prefix, postfix, and expression evaluation.

1. Introduction to Stack

What Is a Stack?

A stack is a linear data structure in which insertion and deletion take place at the same end, called the TOP.

A stack follows the LIFO (Last In, First Out) principle. This means the last element inserted is the first element removed.

Think of a stack of plates: the plate placed on top most recently is the first one you take off.

Example:

       TOP
        |
      [30]  <- Last inserted
      [20]
      [10]  <- First inserted

If we remove one element, 30 is removed first.

Basic Stack Operations

Applications of Stack

Stacks are used in:

• Function calls and recursion.

• Undo and redo features.

• Browser history and navigation.

• Expression conversion and evaluation.

• Parentheses matching.

• Depth-First Search (DFS).

• Backtracking algorithms.

2. LIFO Concept

LIFO stands for Last In, First Out.

Suppose we push three elements in this order:

PUSH(10)
PUSH(20)
PUSH(30)

The stack becomes:

       TOP
        |
      [30]
      [20]
      [10]

Now perform two pop operations:

POP() -> 30
POP() -> 20

The remaining stack is:

       TOP
        |
      [10]

The most recently inserted element is removed first.

Real-Life Example

Imagine placing three books on top of one another:

1. Place Book A.

2. Place Book B on top of A.

3. Place Book C on top of B.

You must remove Book C before you can remove Book B. This is the LIFO principle.

Important: A stack only allows direct access to its top element. To reach an element lower in the stack, you generally have to remove the elements above it first.

3. Stack Using Arrays

An array can implement a stack using a variable called top, which stores the index of the top element.

For a stack with capacity 5:

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

When top == -1, the stack is empty.

When top == 4, the stack is full.

How Array-Based Stack Works

Initially:

Stack: [ _ ][ _ ][ _ ][ _ ][ _ ]
top = -1

After push(10):

Stack: [10 ][ _ ][ _ ][ _ ][ _ ]
top = 0

After push(20):

Stack: [10 ][20 ][ _ ][ _ ][ _ ]
top = 1

After pop():

Stack: [10 ][ _ ][ _ ][ _ ][ _ ]
top = 0

Complete Stack Program Using an Array

This program implements Push, Pop, Peek, and Display operations.

#include 

#define MAX 5

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

int push(int value) {
    if (top == MAX - 1) {
        printf("Stack Overflow\n");
        return 0;
    }

    stack[++top] = value;
    printf("%d pushed\n", value);
    return 1;
}

int pop(int *removed) {
    if (top == -1) {
        printf("Stack Underflow\n");
        return 0;
    }

    *removed = stack[top--];
    return 1;
}

int peek(int *value) {
    if (top == -1) {
        printf("Stack is empty\n");
        return 0;
    }

    *value = stack[top];
    return 1;
}

void display(void) {
    int i;

    if (top == -1) {
        printf("Stack is empty\n");
        return;
    }

    printf("Stack from TOP to bottom: ");

    for (i = top; i >= 0; i--) {
        printf("%d ", stack[i]);
    }

    printf("\n");
}

int main(void) {
    int value;

    push(10);
    push(20);
    push(30);

    display();

    if (peek(&value)) {
        printf("Top element: %d\n", value);
    }

    if (pop(&value)) {
        printf("Popped element: %d\n", value);
    }

    display();

    return 0;
}

Output:

10 pushed
20 pushed
30 pushed
Stack from TOP to bottom: 30 20 10
Top element: 30
Popped element: 30
Stack from TOP to bottom: 20 10

Complexity of Array-Based Stack

Advantages: Simple implementation, fast operations, and good memory locality.

Limitation: A fixed-size array stack has a maximum capacity. Pushing onto a full stack causes overflow.

4. Stack Using Linked Lists

A stack can also be implemented using a linked list. Each node stores a value and a pointer to the next node.

The head pointer represents the top of the stack.

TOP
 |
 v
[30 | *] -> [20 | *] -> [10 | NULL]

Here, 30 is the top element.

Unlike a fixed-size array stack, a linked-list stack can grow dynamically until memory allocation fails or another system limit is reached.

Complete Stack Program Using a Linked List

#include 
#include 

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

struct Node *top = NULL;

int push(int value) {
    struct Node *node = malloc(sizeof *node);

    if (node == NULL) {
        printf("Memory allocation failed\n");
        return 0;
    }

    node->data = value;
    node->next = top;
    top = node;

    printf("%d pushed\n", value);
    return 1;
}

int pop(int *removed) {
    if (top == NULL) {
        printf("Stack Underflow\n");
        return 0;
    }

    struct Node *temp = top;
    *removed = temp->data;

    top = top->next;
    free(temp);

    return 1;
}

int peek(int *value) {
    if (top == NULL) {
        printf("Stack is empty\n");
        return 0;
    }

    *value = top->data;
    return 1;
}

void display(void) {
    struct Node *current = top;

    if (current == NULL) {
        printf("Stack is empty\n");
        return;
    }

    printf("Stack from TOP to bottom: ");

    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }

    printf("\n");
}

void clearStack(void) {
    while (top != NULL) {
        struct Node *temp = top;
        top = top->next;
        free(temp);
    }
}

int main(void) {
    int value;

    if (!push(10) || !push(20) || !push(30)) {
        clearStack();
        return 1;
    }

    display();

    if (peek(&value)) {
        printf("Top element: %d\n", value);
    }

    if (pop(&value)) {
        printf("Popped element: %d\n", value);
    }

    display();

    clearStack();
    return 0;
}

Output:

10 pushed
20 pushed
30 pushed
Stack from TOP to bottom: 30 20 10
Top element: 30
Popped element: 30
Stack from TOP to bottom: 20 10

Array Stack vs Linked-List Stack

Both implementations provide constant-time Push and Pop operations. The right choice depends on capacity requirements and memory constraints.

5. Push, Pop and Peek Operations

These are the three most important stack operations.

A. Push

Push adds a new element to the top of the stack.

For an array-based stack, the operation is:

stack[++top] = value;

The capacity check must happen first.

Example:

Before: TOP -> 20, 10
PUSH(30)
After:  TOP -> 30, 20, 10

Time complexity: (O(1)).

B. Pop

Pop removes and returns the top element.

For an array-based stack:

value = stack[top--];

Again, the empty-stack check must happen first.

Example:

Before: TOP -> 30, 20, 10
POP() returns 30
After:  TOP -> 20, 10

Time complexity: (O(1)).

C. Peek

Peek reads the top element without removing it.

value = stack[top];

Example:

TOP -> 20, 10
PEEK() returns 20
TOP -> 20, 10

The stack remains unchanged.

Time complexity: (O(1)).

Remember: Push adds, Pop removes, and Peek only reads the top element.

6. Stack Overflow and Underflow

Stack Overflow

Stack overflow occurs when a push operation is attempted on a full fixed-capacity stack.

For example, if the capacity is 3:

[30]
[20]
[10]

A fourth push cannot fit in the array.

PUSH(40) -> Stack Overflow

Check the condition before inserting:

if (top == MAX - 1) {
    printf("Stack Overflow\n");
    return 0;
}

A dynamically allocated linked-list stack does not have the same fixed-capacity limit, but memory allocation can still fail.

Stack Underflow

Stack underflow occurs when Pop is attempted on an empty stack.

top = -1
POP() -> Stack Underflow

Check the condition before removing:

if (top == -1) {
    printf("Stack Underflow\n");
    return 0;
}

For a linked-list stack, check top == NULL.

Why Are These Checks Important?

Without proper checks, a program might read invalid memory, access outside an array, or dereference a null pointer.

Best practice: Always check whether the operation is valid before modifying the stack.

7. Infix, Prefix and Postfix Expressions

Stacks are frequently used to convert and evaluate mathematical expressions.

There are three common expression notations.

A. Infix Notation

In infix notation, the operator appears between its operands.

A + B

Examples:

A + B * C
(A + B) * C

This is the notation commonly used in everyday mathematics.

B. Prefix Notation

In prefix notation, the operator appears before its operands.

+ A B

Examples:

+ A * B C
* + A B C

C. Postfix Notation

In postfix notation, the operator appears after its operands.

A B +

Examples:

A B C * +
A B + C *

Comparing the Three Notations

Consider:

A + B * C

Multiplication has higher precedence than addition.

Now consider:

(A + B) * C

Parentheses can change the evaluation order of an infix expression. Prefix and postfix notations encode that order through the positions of their operators.

Operator Precedence

For the basic operators used in this tutorial:

1. Parentheses control grouping.

2. ^ represents exponentiation in our conversion examples.

3. * and / have higher precedence than + and -.

4. + and - have the lowest precedence among these operators.

C-specific note: In C, ^ means bitwise XOR, not exponentiation. Here, ^ is used as a mathematical operator in expression-notation examples only.

8. Expression Conversion and Evaluation

A stack can convert infix expressions into postfix or prefix notation and evaluate postfix or prefix expressions.

A. Infix to Postfix Conversion

Consider:

A + B * C

Because multiplication has higher precedence than addition, the postfix expression is:

A B C * +

The conversion process uses an operator stack:

1. Output operands immediately.

2. Push opening parentheses onto the stack.

3. When an operator appears, pop operators with higher precedence, and with equal precedence when the incoming operator is left-associative.

4. Push the incoming operator.

5. On a closing parenthesis, pop operators until the matching opening parenthesis is found.

6. At the end, pop the remaining operators.

Infix-to-Postfix Program in C

This example supports single-character operands, parentheses, and the operators +, -, *, /, and ^. It assumes ^ is right-associative exponentiation for notation purposes.

#include 
#include 

#define MAX 100

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

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

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

int infixToPostfix(const char *infix, char *postfix) {
    char stack[MAX];
    int top = -1;
    int out = 0;
    int i;

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

        if (isspace((unsigned char)c)) {
            continue;
        }

        if (isalnum((unsigned char)c)) {
            postfix[out++] = c;
        } else if (c == '(') {
            if (top == MAX - 1) return 0;
            stack[++top] = c;
        } else if (c == ')') {
            while (top >= 0 && stack[top] != '(') {
                postfix[out++] = stack[top--];
            }

            if (top < 0) return 0;
            top--;
        } else if (isOperator(c)) {
            while (top >= 0 && isOperator(stack[top]) &&
                   (precedence(stack[top]) > precedence(c) ||
                    (precedence(stack[top]) == precedence(c) &&
                     !isRightAssociative(c)))) {
                postfix[out++] = stack[top--];
            }

            if (top == MAX - 1) return 0;
            stack[++top] = c;
        } else {
            return 0;
        }

        if (out >= MAX - 1) return 0;
    }

    while (top >= 0) {
        if (stack[top] == '(') return 0;
        postfix[out++] = stack[top--];
        if (out >= MAX) return 0;
    }

    postfix[out] = '\0';
    return 1;
}

int main(void) {
    char infix[] = "A+B*C";
    char postfix[MAX];

    if (infixToPostfix(infix, postfix)) {
        printf("Infix: %s\n", infix);
        printf("Postfix: %s\n", postfix);
    } else {
        printf("Invalid expression or expression too long\n");
    }

    return 0;
}

Output:

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

Limitations: This educational converter handles single-character operands, not multi-digit numbers or unary operators. It checks for unmatched parentheses and invalid characters, but it is not a complete mathematical-expression parser.

B. Evaluating a Postfix Expression

Postfix expressions can be evaluated using a stack of numbers.

Example:

Postfix: 2 3 4 * +

Process the expression from left to right:

1. Push 2.

2. Push 3.

3. Push 4.

4. Encounter *: pop 4 and 3, calculate 3 * 4 = 12, then push 12.

5. Encounter +: pop 12 and 2, calculate 2 + 12 = 14, then push 14.

Final result:

14

Postfix Evaluation Program in C

This program evaluates postfix expressions containing single-digit non-negative integers and the operators +, -, *, and /. The input must contain no spaces.

#include 
#include 

#define MAX 100

int evaluatePostfix(const char *expr, int *result) {
    int stack[MAX];
    int top = -1;
    int i;

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

        if (isspace((unsigned char)c)) {
            continue;
        }

        if (isdigit((unsigned char)c)) {
            if (top == MAX - 1) return 0;
            stack[++top] = c - '0';
        } else if (c == '+' || c == '-' ||
                   c == '*' || c == '/') {
            if (top < 1) return 0;

            int b = stack[top--];
            int a = stack[top--];
            int value;

            switch (c) {
                case '+': value = a + b; break;
                case '-': value = a - b; break;
                case '*': value = a * b; break;
                case '/':
                    if (b == 0) return 0;
                    value = a / b;
                    break;
                default: return 0;
            }

            stack[++top] = value;
        } else {
            return 0;
        }
    }

    if (top != 0) return 0;

    *result = stack[top];
    return 1;
}

int main(void) {
    const char expr[] = "234*+";
    int result;

    if (evaluatePostfix(expr, &result)) {
        printf("Postfix: %s\n", expr);
        printf("Result: %d\n", result);
    } else {
        printf("Invalid expression\n");
    }

    return 0;
}

Output:

Postfix: 234*+
Result: 14

Integer division is used in this program. For example, 7 / 2 produces 3.

C. Prefix Evaluation

Prefix expressions place operators before their operands.

Example:

Prefix: + 2 * 3 4

To evaluate prefix notation:

1. Scan the expression from right to left.

2. Push operands onto the stack.

3. When an operator appears, pop the first operand, then the second operand.

4. Apply the operator in the correct order and push the result.

5. The final stack value is the answer.

For the example above:

+ 2 * 3 4
= 2 + (3 * 4)
= 14

Important: For subtraction and division, operand order matters. When scanning prefix from right to left, the first popped operand is the left operand of the operator.

Final Summary

In Module 06, we learned:

1. Introduction to Stack.

2. LIFO Concept.

3. Stack Using Arrays.

4. Stack Using Linked Lists.

5. Push, Pop and Peek Operations.

6. Stack Overflow and Underflow.

7. Infix, Prefix and Postfix Expressions.

8. Expression Conversion and Evaluation.

A stack is a fundamental data structure that follows the Last In, First Out principle. Its Push, Pop, and Peek operations are generally (O(1)), and it plays a major role in recursion, expression processing, and many algorithms.

Module 06 complete: Stack in C.

Next in the Param Classes DSA curriculum: Module 07 — Queue.