Stack; Stack Applications

Stack

What is a Stack?

A Stack is a linear data structure that follows the LIFO (Last In, First Out) principle.

The last element inserted is the first one to be removed.

Real-world analogy: Stack of plates — last plate placed is the first one taken off.

         TOP
          ↓
    +---------+
    |   50    |   ← Pushed last; Popped first
    +---------+
    |   30    |
    +---------+
    |   20    |
    +---------+
    |   10    |   ← Pushed first; Popped last
    +---------+
        BOTTOM

Stack Operations

Stack Conditions

// Stack is FULL when:
if (p->top == SIZE - 1)     // top at last index
    // Stack overflow!

// Stack is EMPTY when:
if (p->top == -1)           // top is -1 (initial/empty state)
    // Stack underflow!

Array-Based Stack Implementation in C

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

#define SIZE 100

typedef struct {
    int eles[SIZE];    // array to store elements
    int top;           //
index of top element (-1 = empty)
} stack_t;

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

// Check if stack is full
int is_full(stack_t *s) {
    return (s->top == SIZE - 1);
}

// Check if stack is empty
int is_empty(stack_t *s) {
    return (s->top == -1);
}

// Push element
void push(stack_t *s, int value) {
    if (is_full(s)) {
printf("Stack Overflow! Cannot push %d\n", value);
        return;
    }
    s->top++;
// increment top
    s->eles[s->top] = value;    // store value at new top
}

// Pop element
int pop(stack_t *s) {
    if (is_empty(s)) {
        printf("Stack Underflow!
Stack is empty.\n");
        return -1;
    }
    int value = s->eles[s->top];  // retrieve
top element
    s->top--;                      // decrement top
    return value;
}

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

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

int main() {
    stack_t s1;
    init_stack(&s1);

    push(&s1, 10);
    push(&s1, 20);
    push(&s1, 30);
    push(&s1, 50);

    display(&s1);     // 50 30 20 10

    printf("Top: %d\n", peek(&s1));   // 50
    printf("Popped: %d\n", pop(&s1)); // 50

    display(&s1);     // 30 20 10

    return 0;
}

Linked-List Based Stack

typedef struct node {
    int data;
    struct node *next;
} node_t;

typedef struct {
    node_t *top;
} lstack_t;

void push(lstack_t *s, int value) {
    node_t *new_node = (node_t*)malloc(sizeof(node_t));
new_node->data = value;
    new_node->next = s->top;
    s->top = new_node;
}

int pop(lstack_t *s) {
    if (s->top == NULL) {
        printf("Stack underflow!\n");
        return -1;
    }
    node_t *temp = s->top;
    int value = temp->data;
    s->top = s->top->next;
    free(temp);
    return value;
}

Stack Applications

5.1 Expression Notations

Mathematical expressions can be written in 3 notations:

Conversions:

• Infix → Postfix
• Infix → Prefix
• Prefix → Postfix
• Prefix → Infix

Postfix → Prefix

• Postfix → Infix
• Prefix → Evaluate
• Postfix → Evaluate

Operators for conversion:
+ - / * % ^ $

Operators for evaluation:
+ - / * % (meaning will be mentioned)

Operator Precedence

Infix to Postfix Conversion Algorithm

Rule:
1. Scan expression left to right
2. If operand → append to output
3. If '(' → push to stack
4. If ')' → pop stack to output until '(' found; discard both parentheses
5. If operator → pop higher or equal precedence operators to output; push current
6. End → pop all remaining operators to output

Example:

Infix: (2 + (3 * 6))
Postfix conversion:
  '(' → push stack: [( ]
  '2' → output: "2"
  '+' → push (no higher prec on stack): stack=[( +]
  '(' → push: stack=[ ( + ( ]
  '3' → output: "2 3"
  '*' → push: stack=[ ( + ( * ]
  '6' → output: "2 3 6"
  ')' → pop until '(': output "2 3 6 *"; stack=[ ( + ]
  ')' → pop until '(': output "2 3 6 * +"; stack=[]

Postfix: 2 3 6 * +
Evaluate: 3*6=18, 2+18=20 = 20 ✓

Complex Example:

Infix:   ((A + ((B / C) * (D ^ E))) - (F $ G))
Postfix: A B C / D E ^ * + F G $ -

Infix to Postfix in C

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

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

void push_char(char c) { stack[++top] = c; }
char pop_char() { return stack[top--]; }
char
peek_char() { return stack[top]; }
int is_empty() { return top == -1; }

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

void infix_to_postfix(char *infix) {
    printf("Postfix: ");
    for (int i = 0; infix[i]
!= '\0'; i++) {
        char c = infix[i];
        if (c == ' ') continue;
if (isalnum(c)) {
            printf("%c ", c);          // operand → output
        } else
if (c == '(') {
            push_char(c);              // '(' → push
        } else if (c ==
')') {
            while (!is_empty() && peek_char() != '(')
                printf("%c ",
pop_char());  // pop until '('
            pop_char();                    // discard '('
} else {  // operator
            while (!is_empty() && precedence(peek_char()) >=
precedence(c))
                printf("%c ", pop_char());
            push_char(c);
}
    }
    while (!is_empty()) printf("%c ", pop_char());
    printf("\n");
}

int main() {
    char infix[] = "A+B*C";
    infix_to_postfix(infix);   // Output: A B C * +
    return 0;
}

Postfix Evaluation in C

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

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

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

int evaluate_postfix(char *expr) {
    int i = 0;
    while (expr[i] != '\0') {
        if
(isdigit(expr[i])) {
            push(expr[i] - '0');    // convert char to int
        }
else if (expr[i] != ' ') {
            int b = pop();          // second operand
int a = pop();          // first operand
            switch (expr[i]) {
                case
'+': push(a + b); break;
                case '-': push(a - b); break;
                case
'*': push(a * b); break;
                case '/': push(a / b); break;
                case
'%': push(a % b); break;
            }
        }
        i++;
    }
    return pop();
}

int main() {
    // 5 - 2 * 6 / 3 = 5 - 12/3 = 5 - 4 = 1
    char postfix[] = "526*3/-";
    printf("Result: %d\n", evaluate_postfix(postfix));  // 1
    return 0;
}

5.2 Prefix Evaluation

Prefix string: 5 - 2 * 6 / 3
Prefix notation: -5/*263

Rule: Read prefix string from RIGHT to LEFT (or reverse it and read left to right)
When operator found: pop two operands, apply operator, push result

5.3 Other Stack Applications

Parenthesis Matching using Stack

int is_balanced(char *str) {
    char stack[100];
    int top = -1;

    for (int i = 0; str[i] != '\0'; i++) {
        char c = str[i];
        if (c == '(' || c == '[' || c == '{') {
            stack[++top] = c;
        } else if (c == ')' || c == ']' || c == '}') {
            if (top == -1) return 0;  // empty stack = unmatched
            char open = stack[top--];
            if ((c == ')' && open != '(') ||
                (c == ']' && open != '[') ||
                (c == '}' && open != '{')) {
                return 0;  // mismatched
            }
        }
    }
    return top == -1;  // 1 if balanced, 0 if unmatched opens
}