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.

Practice

1. What is the main purpose of using an array in stack implementation?

easy

A. To store elements in a fixed-size linear structure

B. To allow random access to elements anywhere in the stack

C. To automatically resize the stack when full

D. To sort elements in ascending order

Solution

1. Step 1: Understand stack storage

   A stack stores elements in a linear order where the last added element is accessed first.

2. Step 2: Role of array in stack

   An array provides a fixed-size linear structure to hold stack elements in order.

3. Final Answer:

   To store elements in a fixed-size linear structure -> Option A

4. Quick Check:

   Array = fixed-size linear storage [OK]

Hint: Stack uses array for fixed-size linear storage [OK]

Common Mistakes:

• Thinking array allows automatic resizing
• Confusing stack with random access structures
• Assuming array sorts elements automatically

2. Which of the following is the correct way to declare a stack array of size 5 in C?

easy

A. int[5] stack;

B. int stack[5];

C. stack int[5];

D. array stack = int[5];

Solution

1. Step 1: Recall C array declaration syntax

   In C, arrays are declared as: type name[size];

2. Step 2: Match syntax with options

   int stack[5]; matches correct syntax: int stack[5];

3. Final Answer:

   int stack[5]; -> Option B

4. Quick Check:

   C array declaration = int stack[5]; [OK]

Hint: C arrays declared as type name[size]; [OK]

Common Mistakes:

• Placing type after variable name
• Using incorrect keywords like 'array'
• Misplacing brackets in declaration

3. What will be the output after executing the following code?

int stack[3];
int top = -1;
// Push 10
stack[++top] = 10;
// Push 20
stack[++top] = 20;
// Pop
int x = stack[top--];
printf("%d", stack[top]);

medium

A. Runtime error

B. 20

C. 10

D. Garbage value

Solution

1. Step 1: Trace push operations

   Initially top = -1.
   Push 10: top becomes 0, stack[0] = 10.
   Push 20: top becomes 1, stack[1] = 20.

2. Step 2: Trace pop and print

   Pop: x = stack[1] = 20, then top becomes 0.
   Print stack[top] = stack[0] = 10.

3. Final Answer:

   10 -> Option C

4. Quick Check:

   After pop, top points to 10 [OK]

Hint: Pop decreases top, print uses updated top [OK]

Common Mistakes:

• Printing popped element instead of current top
• Confusing pre-increment and post-decrement
• Assuming top points beyond last element

4. Identify the error in this stack push function and select the fix:

void push(int stack[], int *top, int size, int value) {
    if (*top == size) {
        printf("Stack Overflow\n");
        return;
    }
    stack[++(*top)] = value;
}

medium

A. No error, code is correct

B. Change condition to *top == size + 1

C. Change stack[++(*top)] to stack[(*top)++]

D. Change condition to *top == size - 1

Solution

1. Step 1: Understand top indexing in stack

   Top starts at -1, max index is size - 1.
   When top == size - 1, stack is full.

2. Step 2: Analyze overflow condition

   Condition *top == size is wrong; it should be *top == size - 1 to detect full stack.

3. Final Answer:

   Change condition to *top == size - 1 -> Option D

4. Quick Check:

   Overflow when top reaches size-1 [OK]

Hint: Top max index is size-1, not size [OK]

Common Mistakes:

• Checking top == size instead of size-1
• Misusing increment operators in array indexing
• Ignoring zero-based indexing

5. Given a stack implemented using an array of size 4, initially empty, what will be the stack content after these operations?

push(5);
push(10);
pop();
push(15);
push(20);
pop();
push(25);

Assume top starts at -1 and push/pop update top accordingly. Choose the correct final stack content from bottom to top.

hard

A. 5 -> 15 -> 25 -> null

B. 5 -> 10 -> 15 -> 25 -> null

C. 10 -> 15 -> 25 -> null

D. 5 -> 15 -> 20 -> 25 -> null

Solution

1. Step 1: Trace each operation step-by-step

   Start: top = -1, stack empty.
   push(5): top=0, stack[0]=5
   push(10): top=1, stack[1]=10
   pop(): removes 10, top=0
   push(15): top=1, stack[1]=15
   push(20): top=2, stack[2]=20
   pop(): removes 20, top=1
   push(25): top=2, stack[2]=25

2. Step 2: Final stack content

   Stack from bottom (index 0) to top (index 2): 5, 15, 25

3. Final Answer:

   5 -> 15 -> 25 -> null -> Option A

4. Quick Check:

   Push/pop update top correctly [OK]

Hint: Track top index after each push/pop [OK]

Common Mistakes:

• Forgetting to update top after pop
• Assuming pop removes bottom element
• Mixing order of elements after operations