C DSA Stacks

What is a Stack?

A stack is a data structure where you add and remove items at the same end: the top.

The last item you add is the first item you remove. This rule is called LIFO (Last In, First Out).

You use stacks every day, maybe without knowing it:

• The Undo button in a text editor removes your last change first.
• The Back button in a web browser goes to the page you visited last.
• C itself uses a stack to remember which function to return to when a function call ends.

Stack Operations

A stack has a few basic operations:

Try it! In C, we build a stack with an array. Push adds a value after the last one (on the top), and pop removes the last value:

The yellow box is the top of the stack. The array has room for 6 values. Push until the stack is full, or pop until it is empty. What happens?

Create a Stack With an Array

The easiest way to make a stack in C is with an array and one extra variable, for example top.

top stores the index of the item on the top. When the stack is empty, top is -1:

#include <stdio.h>

int main() {
  int stack[5];
  int top = -1; // -1 means the stack is empty

  // Push 10, 20 and 30
  top++;
  stack[top] = 10;
  top++;
  stack[top] = 20;
  top++;
  stack[top] = 30;

  printf("Top item: %d\n", stack[top]);

  // Pop the top item
  printf("Popped: %d\n", stack[top]);
  top--;

  printf("Top item now: %d\n", stack[top]);

  return 0;
}

Top item: 30
Popped: 30
Top item now: 20

Did you notice? Pop does not erase the number 30. It only moves top down. The value is still in the array, but it is no longer part of the stack.

Stack Functions

Writing top++ again and again gets messy. It is better to put each operation in its own function.

In the example below:

• #define MAX 5 gives the number 5 a name, so the size is easy to change (see C Macros).
• stack and top are created outside main(), so all the functions can use them (see C Scope).

#include <stdio.h>
#define MAX 5

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

void push(int value) {
  if (top == MAX - 1) {
    printf("Stack is full!\n");
    return;
  }
  top++;
  stack[top] = value;
}

int pop() {
  if (top == -1) {
    printf("Stack is empty!\n");
    return -1;
  }
  int value = stack[top];
  top--;
  return value;
}

int peek() {
  if (top == -1) {
    printf("Stack is empty!\n");
    return -1;
  }
  return stack[top];
}

// Returns 1 (true) if the stack is empty
int isEmpty() {
  return top == -1;
}

int main() {
  push(10);
  push(20);
  push(30);

  printf("Top item: %d\n", peek());

  // Pop items until the stack is empty
  while (!isEmpty()) {
    printf("Popped: %d\n", pop());
  }

  return 0;
}

Top item: 30
Popped: 30
Popped: 20
Popped: 10

Example Explained

• push() first checks if the stack is full. If not, it moves top up and stores the value.
• pop() first checks if the stack is empty. If not, it saves the top value, moves top down, and returns the value.
• peek() returns the top value, but does not change top.
• isEmpty() returns 1 (true) when top is -1.

We pushed 10, 20, 30, and got them back as 30, 20, 10. Last in, first out!

Stack Overflow and Underflow

Two things can go wrong with a stack:

• Overflow - you push onto a stack that is already full.
• Underflow - you pop from a stack that is already empty.

Without a check, the program would read or write outside the array. This is a serious bug that can crash your program. That is why push() and pop() always check first.

In this example, the stack only has room for 3 items:

#include <stdio.h>
#define MAX 3

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

void push(int value) {
  if (top == MAX - 1) {
    printf("Overflow! Cannot push %d\n", value);
    return;
  }
  top++;
  stack[top] = value;
  printf("Pushed %d\n", value);
}

int pop() {
  if (top == -1) {
    printf("Underflow! The stack is empty\n");
    return -1;
  }
  int value = stack[top];
  top--;
  printf("Popped %d\n", value);
  return value;
}

int main() {
  push(1);
  push(2);
  push(3);
  push(4); // The stack is full

  pop();
  pop();
  pop();
  pop(); // The stack is empty

  return 0;
}

Pushed 1
Pushed 2
Pushed 3
Overflow! Cannot push 4
Popped 3
Popped 2
Popped 1
Underflow! The stack is empty

Real-Life Example: Reverse a Word

A stack gives items back in reverse order. That makes it perfect for reversing things!

Push every letter of a word onto the stack. Then pop them all off again:

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

int main() {
  char word[] = "HELLO";
  int length = strlen(word);
  char stack[20];
  int top = -1;

  // Push every letter
  for (int i = 0; i < length; i++) {
    top++;
    stack[top] = word[i];
  }

  // Pop every letter
  printf("Reversed: ");
  while (top != -1) {
    printf("%c", stack[top]);
    top--;
  }
  printf("\n");

  return 0;
}

Reversed: OLLEH

Run the simulation below to see how the code above works, one step at a time:

Summary

• A stack adds and removes items at the top: Last In, First Out (LIFO).
• push adds an item, pop removes an item, and peek looks at the top item.
• You can build a stack with an array and a top index.
• Always check for overflow (full stack) and underflow (empty stack).

A stack always takes the newest item. What if you want the oldest item instead? Then you need a queue. That is the next chapter!