Implementing a Stack Using Arrays in C

In the realm of data structures, a stack stands out as one of the most fundamental and intuitive concepts. It's a linear data structure that follows a particular order in which operations are performed. Think of it like a pile of plates: you can only add a new plate to the top, and you can only remove the topmost plate. This behavior is formally known as LIFO (Last-In, First-Out).

This entry in our C Language Series delves into the practical implementation of a stack using arrays, a common and straightforward approach for fixed-size requirements.

Understanding the Stack's Core Principles

Before diving into code, let's solidify the core operations associated with a stack:

• Push: Adds an element to the top of the stack.
• Pop: Removes the topmost element from the stack.
• Peek (or Top): Returns the value of the topmost element without removing it.
• isEmpty: Checks if the stack has any elements.
• isFull: Checks if the stack has reached its maximum capacity (relevant for array-based implementations).

Why Use Arrays for Stack Implementation?

Arrays offer a simple and efficient way to implement a stack due to their contiguous memory allocation and direct access capabilities. We'll use a single integer variable, typically named top, to keep track of the index of the topmost element in the array. Initially, when the stack is empty, top is set to -1.

Stack Data Structure Representation

To implement a stack using an array in C, we'll need:

1. An integer array to store the elements.
2. An integer variable, top, to point to the index of the last inserted element.
3. A macro or constant for the maximum size of the stack.

#include <stdio.h>
#include <stdlib.h> // For exit()

#define MAX_SIZE 5 // Define the maximum size of the stack

int stack[MAX_SIZE]; // Array to store stack elements
int top = -1;        // top pointer initialized to -1 (empty stack)

Implementing Core Stack Operations

1. `isEmpty()` Function

This function checks if the stack is empty. An empty stack is indicated when the top pointer is -1.

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

2. `isFull()` Function

This function checks if the stack is full. For an array-based stack, it's full when top reaches MAX_SIZE - 1.

int isFull() {
    return top == MAX_SIZE - 1;
}

3. `push()` Operation

The push operation adds an element to the top of the stack. Before adding, we must check if the stack is already full to prevent "stack overflow." If not full, we increment top and then place the new element at stack[top].

void push(int data) {
    if (isFull()) {
        printf("Error: Stack Overflow! Cannot push %d.\n", data);
        return;
    }
    top++;
    stack[top] = data;
    printf("Pushed %d onto the stack.\n", data);
}

4. `pop()` Operation

The pop operation removes and returns the topmost element from the stack. We first check if the stack is empty to prevent "stack underflow." If not empty, we retrieve the element at stack[top] and then decrement top.

int pop() {
    if (isEmpty()) {
        printf("Error: Stack Underflow! Cannot pop from an empty stack.\n");
        // In a real application, you might return a special error value
        // or handle it differently. For simplicity, we'll exit here.
        exit(EXIT_FAILURE); 
    }
    int data = stack[top];
    top--;
    printf("Popped %d from the stack.\n", data);
    return data;
}

5. `peek()` (or `topElement()`) Operation

The peek operation returns the topmost element without removing it. Similar to pop, it requires a check for an empty stack.

int peek() {
    if (isEmpty()) {
        printf("Error: Stack is Empty! No top element to peek.\n");
        exit(EXIT_FAILURE);
    }
    printf("Top element is %d.\n", stack[top]);
    return stack[top];
}

6. `display()` Operation (Optional but Useful)

A simple function to print all elements of the stack, from top to bottom.

void display() {
    if (isEmpty()) {
        printf("Stack is empty.\n");
        return;
    }
    printf("Stack elements (top to bottom): ");
    for (int i = top; i >= 0; i--) {
        printf("%d ", stack[i]);
    }
    printf("\n");
}

Complete C Code Example

Here's the complete C program combining all the stack operations with a main function to demonstrate their usage:

#include <stdio.h>
#include <stdlib.h> // For exit()

#define MAX_SIZE 5 // Define the maximum size of the stack

int stack[MAX_SIZE]; // Array to store stack elements
int top = -1;        // top pointer initialized to -1 (empty stack)

// Function to check if the stack is empty
int isEmpty() {
    return top == -1;
}

// Function to check if the stack is full
int isFull() {
    return top == MAX_SIZE - 1;
}

// Function to push an element onto the stack
void push(int data) {
    if (isFull()) {
        printf("Error: Stack Overflow! Cannot push %d.\n", data);
        return;
    }
    top++;
    stack[top] = data;
    printf("Pushed %d onto the stack.\n", data);
}

// Function to pop an element from the stack
int pop() {
    if (isEmpty()) {
        printf("Error: Stack Underflow! Cannot pop from an empty stack.\n");
        exit(EXIT_FAILURE); 
    }
    int data = stack[top];
    top--;
    printf("Popped %d from the stack.\n", data);
    return data;
}

// Function to peek the top element of the stack
int peek() {
    if (isEmpty()) {
        printf("Error: Stack is Empty! No top element to peek.\n");
        exit(EXIT_FAILURE);
    }
    printf("Top element is %d.\n", stack[top]);
    return stack[top];
}

// Function to display stack elements
void display() {
    if (isEmpty()) {
        printf("Stack is empty.\n");
        return;
    }
    printf("Stack elements (top to bottom): ");
    for (int i = top; i >= 0; i--) {
        printf("%d ", stack[i]);
    }
    printf("\n");
}

int main() {
    printf("--- Stack Operations Demonstration ---\n");

    display(); // Should show "Stack is empty."

    push(10);
    push(20);
    push(30);
    display();

    peek(); // Should show top element is 30

    push(40);
    push(50);
    display();

    push(60); // Should show "Stack Overflow!"

    pop(); // Should pop 50
    display();

    peek(); // Should show top element is 40

    pop(); // Should pop 40
    pop(); // Should pop 30
    display();

    pop(); // Should pop 20
    pop(); // Should pop 10
    display(); // Should show "Stack is empty."

    // Attempt to pop from an empty stack (will cause Underflow error and exit)
    // pop(); 

    return 0;
}

Time and Space Complexity

• Time Complexity: All stack operations (push, pop, peek, isEmpty, isFull) take O(1) constant time. This is because they involve only a few basic operations like incrementing/decrementing a pointer and array access, regardless of the number of elements in the stack.
• Space Complexity: The space complexity for an array-based stack is O(N), where N is the maximum size of the array. The space is pre-allocated and fixed.

Advantages and Disadvantages of Array-Based Stacks

Advantages:

• Simplicity: Easy to understand and implement.
• Efficiency: Constant time complexity (O(1)) for all basic operations due to direct array access.
• Memory Locality: Elements are stored contiguously, which can lead to better cache performance.

Disadvantages:

• Fixed Size: The most significant drawback is its fixed capacity. Once declared, the array size cannot be changed. This leads to the risk of "Stack Overflow" if more elements than capacity are pushed.
• Underutilization/Waste: If the allocated size is much larger than the actual number of elements used, memory can be wasted.

Conclusion

Implementing a stack using arrays is an excellent starting point for understanding this fundamental data structure. It's simple, efficient for basic operations, and suitable when the maximum size of the stack is known and relatively small. However, for scenarios requiring dynamic resizing or where the stack size cannot be easily predicted, alternative implementations like linked lists might be more appropriate. Mastering array-based stacks lays a solid foundation for more complex data structure concepts in C programming.