Stack Implementation Using Array in DSA C

Mental Model

A stack is like a pile where you add and remove items only from the top. Using an array, we keep track of the top position to add or remove elements.

Analogy: Imagine a stack of plates: you can only put a new plate on top or take the top plate off. The array holds the plates in order, and a pointer shows which plate is on top.

Array: [ _ , _ , _ , _ , _ ]
Top index: -1 (empty stack)

Visual:
Bottom -> [ _ , _ , _ , _ , _ ] <- Top
                 ↑ top = -1 (no plates)

Dry Run Walkthrough

Input: Create stack of size 5, push 10, push 20, pop, push 30

Goal: Show how the stack changes after each push and pop operation using an array

Step 1: Initialize stack with size 5, top = -1 (empty)

Array: [ _ , _ , _ , _ , _ ]
Top = -1

Why: Start with empty stack, top points before first element

Step 2: Push 10 onto stack, increment top to 0, store 10 at index 0

Array: [ 10 , _ , _ , _ , _ ]
Top = 0

Why: Add first element at bottom (index 0), top moves up

Step 3: Push 20 onto stack, increment top to 1, store 20 at index 1

Array: [ 10 , 20 , _ , _ , _ ]
Top = 1

Why: Add next element on top of previous, top moves up

Step 4: Pop from stack, remove element at top index 1 (20), decrement top to 0

Array: [ 10 , 20 , _ , _ , _ ]
Top = 0

Why: Remove top element by moving top pointer down, element 20 ignored

Step 5: Push 30 onto stack, increment top to 1, store 30 at index 1

Array: [ 10 , 30 , _ , _ , _ ]
Top = 1

Why: Add new element on top, top moves up

Result:

Array: [ 10 , 30 , _ , _ , _ ]
Top = 1
Stack content from bottom to top: 10 -> 30 -> null

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#define MAX 5

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

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

int isFull(Stack* s) {
    return s->top == MAX - 1; // top at last index means full
}

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

void push(Stack* s, int val) {
    if (isFull(s)) {
        printf("Stack Overflow\n");
        return;
    }
    s->top++; // move top up
    s->arr[s->top] = val; // place value at new top
}

int pop(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack Underflow\n");
        return -1; // error value
    }
    int val = s->arr[s->top]; // get top value
    s->top--; // move top down
    return val;
}

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

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

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

    int popped = pop(&s);
    printf("Popped: %d\n", popped);
    printStack(&s);

    push(&s, 30);
    printStack(&s);

    return 0;
}

s->top = -1; // start empty

initialize top pointer to -1 to mark empty stack

return s->top == MAX - 1; // top at last index means full

check if stack is full by comparing top to max index

return s->top == -1; // top -1 means empty

check if stack is empty by top pointer

s->top++; // move top up

increment top to add new element

s->arr[s->top] = val; // place value at new top

store pushed value at current top index

int val = s->arr[s->top]; // get top value

retrieve value at top before popping

s->top--; // move top down

decrement top to remove element

for (int i = 0; i <= s->top; i++) {

iterate from bottom to top to print stack

Output

10 -> 20 -> null

Popped: 20

10 -> null

10 -> 30 -> null

Complexity Analysis

Time: O(1) for push and pop because we only move the top pointer and access one array element

Space: O(n) where n is the max size of the stack because we allocate fixed array space

vs Alternative: Compared to linked list stack, array stack uses fixed memory but has faster access and simpler code

Edge Cases

Push on full stack

Prints 'Stack Overflow' and does not add element

DSA C

if (isFull(s)) { printf("Stack Overflow\n"); return; }

Pop on empty stack

Prints 'Stack Underflow' and returns -1

DSA C

if (isEmpty(s)) { printf("Stack Underflow\n"); return -1; }

Print empty stack

Prints 'Stack is empty'

DSA C

if (isEmpty(s)) { printf("Stack is empty\n"); return; }

When to Use This Pattern

When you need last-in-first-out order and fixed maximum size, use stack with array for simple and fast push/pop operations.

Common Mistakes

Mistake: Incrementing top after storing value causes off-by-one error
Fix: Always increment top before storing new value in push

Mistake: Not checking for stack overflow before push
Fix: Check isFull() before pushing to avoid writing outside array

Mistake: Not checking for stack underflow before pop
Fix: Check isEmpty() before popping to avoid invalid access

Summary

Implements a stack using a fixed-size array with a top pointer to add/remove elements.

Use when you want a simple stack with known maximum size and fast operations.

The top index tracks the current top element, moving up on push and down on pop.