Stack · Data Structures

A stack is a collection where you can only add or remove at one end, called the top. The last item pushed is the first one popped: LIFO (Last In, First Out). Think of a pile of plates, the browser Back button, or Undo in a text editor.

Items are pushed and popped at the top. 40 was pushed last, so it will be popped first.

Operations

Operation	Meaning	Cost
`push(x)`	put `x` on top	O(1)
`pop()`	remove and return the top item	O(1)
`peek()` / `top()`	look at the top item without removing it	O(1)
`isEmpty()`	is the stack empty?	O(1)
`isFull()`	(array version) is it at capacity?	O(1)

Pushing onto a full array stack is overflow; popping from an empty stack is underflow.

Try it

Array implementation

Keep an array and an index top of the current top element. An empty stack has top = -1.

#include <stdio.h>
#define MAX 5

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

int isEmpty(void) { return top == -1; }
int isFull(void)  { return top == MAX - 1; }

void push(int x) {
    if (isFull()) { printf("Overflow: cannot push %d\n", x); return; }
    stack[++top] = x;
    printf("pushed %d\n", x);
}

int pop(void) {
    if (isEmpty()) { printf("Underflow\n"); return -1; }
    return stack[top--];
}

int peek(void) { return isEmpty() ? -1 : stack[top]; }

int main(void) {
    for (int i = 1; i <= 6; i++) push(i * 10);    // the 6th push overflows
    printf("top is %d\n", peek());
    printf("popped %d\n", pop());
    printf("popped %d\n", pop());
    printf("top is now %d\n", peek());
    return 0;
}

Output

pushed 10
pushed 20
pushed 30
pushed 40
pushed 50
Overflow: cannot push 60
top is 50
popped 50
popped 40
top is now 30

Try it Yourself

Linked-list implementation

Push and pop at the head of a linked list — both O(1) — and the stack never overflows (until memory runs out):

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

typedef struct Node { int data; struct Node *next; } Node;
Node *top = NULL;

void push(int x) {
    Node *n = malloc(sizeof(Node));
    n->data = x;
    n->next = top;
    top = n;
}

int pop(void) {
    if (top == NULL) { printf("Underflow\n"); return -1; }
    Node *t = top;
    int x = t->data;
    top = t->next;
    free(t);
    return x;
}

int main(void) {
    const char *word = "STACK";
    for (int i = 0; word[i]; i++) push(word[i]);
    printf("Reversed: ");
    while (top != NULL) printf("%c", pop());     // LIFO reverses the order
    printf("\n");
    pop();
    return 0;
}

Output

Reversed: KCATS
Underflow

Try it Yourself

Array vs linked-list stack

	Array	Linked list
Size	fixed (overflow possible)	grows as needed
Memory per item	just the data	data + pointer
Speed	very fast, cache-friendly	`malloc` per push

Where stacks are used

Function calls — the call stack stores each function's local variables and return address.
Undo/redo and the browser Back button.
Expression evaluation and bracket matching — next lesson.
Depth-first search and backtracking (mazes, Sudoku).
Reversing anything: strings, lists, the digits of a number.

Test yourself

4 questions · pick an answer to check it instantly

1
A stack follows which order?
2
Push 1, 2, 3, then pop twice, then push 4. What is on top?
3
In the array implementation, what does top == -1 mean?
4
What is popping from an empty stack called?

#Operations

#Try it

#Array implementation

#Linked-list implementation

#Array vs linked-list stack

#Where stacks are used