Stack using array

An array-based stack stores elements in a contiguous block of memory and tracks the top with an integer index. Push and pop at the top are O(1) time. The trade-off is a fixed maximum capacity (unless you switch to a dynamic array). This page uses the common convention top == -1 for an empty stack and top == capacity - 1 when full.

1) Array representation

You need a place to hold values, a record of where the top is, and a limit on how many items fit. At its simplest that is just an array and an integer top (you can group both in a struct later for convenience).

2) Mapping operations to the array

All mutations adjust top by one and read or write items[top]. Always check full before push and empty before pop or peek.

3) Example in C

Below, the stack is a fixed int array plus an index top, both kept at file scope with static so helpers need no struct, no pointer parameters, and no & in main. Functions return 1 on success and 0 on overflow or underflow; after a successful peek or pop, read the value from stack_last.

#include <stdio.h>

#define MAX 100

/* One stack for this file: elements live in stack[0..top], top == -1 when empty. */
static int stack[MAX];
static int top;

/* After stack_peek or stack_pop returns 1, the top value is here (no extra out-parameters). */
static int stack_last;

void stack_init(void) {
    top = -1;
}

int stack_is_empty(void) {
    return top < 0;
}

int stack_is_full(void) {
    /* Last valid index is MAX - 1, so full when top sits there. */
    return top >= MAX - 1;
}

/* Returns 1 on success, 0 if overflow (array full). */
int stack_push(int value) {
    if (stack_is_full())
        return 0;
    top++;
    stack[top] = value;
    return 1;
}

/* Returns 1 on success, 0 if underflow (empty). Popped value is stored in stack_last. */
int stack_pop(void) {
    if (stack_is_empty())
        return 0;
    stack_last = stack[top];
    top--;
    return 1;
}

/* Returns 1 on success, 0 if underflow. Current top (without removing) is stack_last. */
int stack_peek(void) {
    if (stack_is_empty())
        return 0;
    stack_last = stack[top];
    return 1;
}

int main(void) {
    stack_init();

    stack_push(10);
    stack_push(20);

    if (stack_peek())
        printf("peek: %d\n", stack_last);

    if (stack_pop())
        printf("pop: %d\n", stack_last);

    return 0;
}

This layout is easy to read; larger programs usually pass the array and top explicitly or wrap them in a type so you can have more than one stack.

Explanation of the program output

Here’s the explanation of the program’s output in table format:

Key points

4) Trade-offs

• Pros — Very fast and simple; excellent cache locality; no malloc per push if the array is static or allocated once.
• Cons — Fixed cap causes overflow unless you resize; wasted space if you allocate huge MAX but use little.

For unbounded growth from an array, use a dynamic array stack; for no fixed cap without contiguous resizing, compare with a linked-list stack. Operation definitions are summarized on Stack operations.