Unit 1 · Lesson 518 minAcademic review pending

Last in, first out

A stack restricts access to one end. That single restriction is what makes it exactly the right tool for undo history, function calls, and matching brackets.

Choose explanation

After this lesson

You should be able to

Implement push, pop, and peek using an array.
Detect and handle stack overflow and underflow.
Explain LIFO order with a traced example.

Try it before you read

Try it live

stack.ctop = -1

Stack is empty — top = -1. pop() has nothing to remove.

One end, two operations

A stack allows insertion and removal only at one end, called the top. push adds there; pop removes from there. The last value pushed is always the first popped — last in, first out — because nothing can reach past the top to touch an older value.

An array implements this naturally: keep an index called top pointing at the most recently pushed slot, and push and pop become one increment or decrement plus one array access each.

top = -1 is the empty-stack convention

#define CAPACITY 100

int data[CAPACITY];
int top = -1;              /* -1 means empty: no valid index yet */

int is_empty(void) { return top == -1; }
int is_full(void)  { return top == CAPACITY - 1; }

push and pop, guarded

An unguarded push past capacity silently writes outside the array — the same out-of-bounds bug your C course covered, just wearing a new name: stack overflow. An unguarded pop on an empty stack reads a slot that was never written. Both checks are one line and both are compulsory.

peek returns the top value without removing it — useful whenever you need to look before deciding whether to pop.

++top before writing; data[top--] reads then steps back

void push(int value)
{
    if (is_full()) { printf("Stack overflow\n"); return; }
    data[++top] = value;
}

int pop(void)
{
    if (is_empty()) { printf("Stack underflow\n"); return -1; }
    return data[top--];
}

int peek(void)
{
    return data[top];   /* caller must check is_empty first */
}

Same ADT, a different implementation waiting

Notice that push, pop, and peek here have exactly the signatures Lesson 1 promised for the stack ADT. Nothing about how a caller uses this stack would change if you rebuilt it internally as a linked list with insert_front instead of an array with top — which is precisely the point of separating the ADT from its implementation.

An array-based stack has a fixed capacity, which a linked-list-based one avoids — the same trade-off from Lesson 2, now applied one layer up.

Try it yourself

Read a line of digits and print them in reverse order using a stack, then report if the digits happen to be the same forwards and backwards.

Need a hint?

Pushing every digit and then popping all of them gives you the reverse for free, because of LIFO order.

Check the worked solution

The reversal needs no explicit reversing logic at all — LIFO order does it, which is the whole reason a stack is the natural tool here rather than, say, a queue. Comparing the popped sequence against the original characters checks the palindrome property in the same pass.

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

#define CAPACITY 100
char data[CAPACITY];
int  top = -1;

void push(char c) { if (top < CAPACITY - 1) data[++top] = c; }
char pop(void)     { return data[top--]; }
int  is_empty(void){ return top == -1; }

int main(void)
{
    char line[CAPACITY];
    int  n, palindrome = 1;

    printf("Enter digits: ");
    scanf("%s", line);
    n = strlen(line);

    for (int i = 0; i < n; i++) push(line[i]);

    printf("Reversed: ");
    for (int i = 0; i < n; i++) {
        char c = pop();
        printf("%c", c);
        if (c != line[i]) palindrome = 0;
    }

    printf("\n%s\n", palindrome ? "Palindrome" : "Not a palindrome");
    return 0;
}

Quick check

In the array-based stack with top starting at -1, what does is_full() check?

Select an answer to check your thinking.

Why this lesson exists

Syllabus mapping

Stacks- Operations · Stack algorithm · Stack ADT

Maps to course outcomes CO1, CO3, CO4.