Stack Implementation

Implementing the Stack

A stack is a fundamental data structure that operates on a simple principle: Last-In, First-Out (LIFO). Imagine a stack of plates. You can only add a new plate to the top, and you can only take a plate from the top. The last plate you put on is the first one you take off. In programming, this structure is incredibly useful for managing tasks like function calls, parsing expressions, and implementing undo features.

As an Abstract Data Type (ADT), a stack is defined by its behaviour, not its specific implementation. The core operations are:

Push: Add an element to the top of the stack.
Pop: Remove the element from the top of the stack.
Peek (or Top): Look at the top element without removing it.

We'll explore two common ways to build a stack in C: using a static array and using a dynamic linked list.

Array-Based Implementation

The simplest way to create a stack is with an array. We'll also need a variable, often called top, to keep track of the index of the top-most element. When the stack is created, top is initialized to -1, indicating that the stack is empty.

#define MAX_SIZE 100

typedef struct {
    int items[MAX_SIZE];
    int top;
} Stack;

void initialize(Stack *s) {
    s->top = -1; // -1 indicates an empty stack
}

To push an item, we first check if the stack is full. This condition is known as a stack overflow. If there's space, we increment top and place the new item at that index.

#include <stdio.h>

void push(Stack *s, int value) {
    if (s->top == MAX_SIZE - 1) {
        printf("Error: Stack Overflow\n");
        return;
    }
    s->top++;
    s->items[s->top] = value;
}

To pop an item, we do the reverse. First, we check if the stack is empty, a condition called stack underflow. If it's not empty, we retrieve the item at the top index and then decrement top.

int pop(Stack *s) {
    if (s->top == -1) {
        printf("Error: Stack Underflow\n");
        return -1; // Return an error code
    }
    int item = s->items[s->top];
    s->top--;
    return item;
}

The main advantage of an array-based stack is its simplicity and speed. Accessing elements is fast because memory is contiguous. However, its fixed size is a major drawback. If you don't know the maximum number of items you'll need, you risk either wasting memory or running out of space.

Linked List Implementation

A more flexible approach uses a linked list. This method avoids the fixed-size limitation by allocating memory dynamically as needed. Each element, or node, contains data and a pointer to the next node in the stack.

We start by defining the structure for a node. The stack itself is simply a pointer to the top node. If this pointer is NULL, the stack is empty.

#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

// The stack is represented by a pointer to the top node.
// Node* top = NULL; // An empty stack

Pushing an element involves creating a new node using malloc and linking it to the current top of the stack. The new node then becomes the new top.

void push(Node** top_ref, int new_data) {
    // 1. Allocate memory for the new node
    Node* new_node = (Node*)malloc(sizeof(Node));

    // 2. Assign data
    new_node->data = new_data;

    // 3. Link it to the old top
    new_node->next = (*top_ref);

    // 4. Make the new node the new top
    (*top_ref) = new_node;
}

Notice we use a pointer to a pointer (Node** top_ref). This allows the push function to modify the top pointer in the calling function, ensuring the change persists.

Popping an element is the reverse process. We check for a stack underflow (top == NULL), save the top node's data, move the top pointer to the next node, and then free the memory of the old top node.

int pop(Node** top_ref) {
    if (*top_ref == NULL) {
        printf("Error: Stack Underflow\n");
        return -1; // Error code
    }
    Node* temp = *top_ref;
    int popped_data = temp->data;

    // Move top to the next node
    *top_ref = temp->next;

    // Free the old top node's memory
    free(temp);

    return popped_data;
}

The linked list implementation elegantly handles a variable number of elements without the risk of stack overflow, limited only by available system memory. The tradeoff is a slight performance overhead due to and pointer dereferencing. Each push and pop requires a call to malloc or free, which can be slower than simple array index manipulation.

Choosing the Right Implementation

So, which one should you use? The choice depends on your application's needs.

Feature	Array-Based Stack	Linked List-Based Stack
Memory	Static, fixed-size	Dynamic, grows as needed
Performance	Faster (no system calls for allocation)	Slower (overhead from `malloc`/`free`)
Overflow	Can happen if `MAX_SIZE` is exceeded	Unlikely (limited only by system memory)
Complexity	Simpler to implement	More complex due to pointers
Use Case	When max size is known and small	When size is unknown or can vary greatly

If you are working in a memory-constrained environment like embedded systems, or if you know for certain that your stack will never exceed a specific size, the array-based approach is efficient and reliable. For general-purpose applications where the data volume is unpredictable, a linked list provides the necessary flexibility to avoid arbitrary limits.

Quiz Questions 1/5

What is the fundamental operating principle of a stack data structure?

Quiz Questions 2/5

In an array-based implementation of a stack, what is the condition called when you try to add an element to a full stack?

Linear Data Structures and Implementations