Stack

A stack is a LIFO (Last In, First Out) structure. Insertion (push) and deletion (pop) both happen at the top.

Stack: push and pop both happen at the top (LIFO)

#include <stdio.h>
#define MAX 100
int stack[MAX], top = -1;

void push(int x) {
    if (top == MAX - 1) { printf("Overflow\n"); return; }
    stack[++top] = x;
}
int pop() {
    if (top == -1) { printf("Underflow\n"); return -1; }
    return stack[top--];
}

int main() {
    push(10); push(20); push(30);
    printf("%d popped\n", pop());
    printf("Top is %d\n", stack[top]);
    return 0;
}

30 popped Top is 20

Applications

Function calls and recursion (the call stack)
Undo/redo, browser back button
Balanced-parentheses checking
Infix → postfix conversion and postfix evaluation

Infix to Postfix Example

Text

Infix:  A + B * C - D

Symbol  Stack   Postfix
A               A
+       +       A
B       +       AB
*       + *     AB
C       + *     ABC
-       -       ABC*+      (pop * and + : higher/equal precedence)
D       -       ABC*+D
end             ABC*+D-

Postfix: A B C * + D -

Track your progress through the Data Structures course

← Prev Next →