C Language Series #166: Stacks and Queues in C

Welcome to another installment of our C Language Series! In this guide, we dive deep into two fundamental linear data structures: Stacks and Queues. As Abstract Data Types (ADTs), they provide specific ways to store and retrieve data, making them indispensable tools in algorithm design and system programming. Understanding their principles and various implementations in C is crucial for any aspiring programmer.

Understanding Stacks

What is a Stack?

A Stack is a linear data structure that follows the LIFO (Last In, First Out) principle. Imagine a stack of plates: you can only add a new plate on top, and you can only remove the topmost plate. The last plate added is always the first one to be removed.

Core Stack Operations

Stacks typically support the following operations:

• push: Adds an element to the top of the stack.
• pop: Removes and returns the element from the top of the stack.
• peek (or top): Returns the top element without removing it.
• isEmpty: Checks if the stack is empty.
• isFull: (For array-based stacks) Checks if the stack has reached its maximum capacity.

Implementing a Stack in C

Array-Based Stack

An array-based stack uses a fixed-size array to store elements. A top index keeps track of the topmost element. When the stack is full, push operations will result in an overflow. When empty, pop or peek operations result in an underflow.

Pros: Simple to implement, efficient memory access (cache friendly).

Cons: Fixed size (potential for overflow), requires resizing if more capacity is needed.

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

#define MAX_SIZE 10 // Maximum capacity of the stack

// Structure to represent an array-based stack
typedef struct {
    int arr[MAX_SIZE];
    int top; // Index of the top element
} ArrayStack;

// Function to initialize a stack
void initArrayStack(ArrayStack* stack) {
    stack->top = -1; // -1 indicates an empty stack
}

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

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

// Function to push an element onto the stack
void pushArrayStack(ArrayStack* stack, int data) {
    if (isArrayStackFull(stack)) {
        printf("Stack Overflow! Cannot push %d.\n", data);
        return;
    }
    stack->arr[++stack->top] = data;
    printf("%d pushed to stack.\n", data);
}

// Function to pop an element from the stack
int popArrayStack(ArrayStack* stack) {
    if (isArrayStackEmpty(stack)) {
        printf("Stack Underflow! Cannot pop from empty stack.\n");
        exit(EXIT_FAILURE); // Or return a sentinel value
    }
    int popped = stack->arr[stack->top--];
    printf("%d popped from stack.\n", popped);
    return popped;
}

// Function to peek the top element of the stack
int peekArrayStack(ArrayStack* stack) {
    if (isArrayStackEmpty(stack)) {
        printf("Stack is empty! No element to peek.\n");
        exit(EXIT_FAILURE); // Or return a sentinel value
    }
    return stack->arr[stack->top];
}

int main() {
    ArrayStack s;
    initArrayStack(&s);

    pushArrayStack(&s, 10);
    pushArrayStack(&s, 20);
    pushArrayStack(&s, 30);

    printf("Top element is: %d\n", peekArrayStack(&s));

    popArrayStack(&s);
    printf("Top element is: %d\n", peekArrayStack(&s));

    popArrayStack(&s);
    popArrayStack(&s);

    if (isArrayStackEmpty(&s)) {
        printf("Stack is now empty.\n");
    }

    pushArrayStack(&s, 40);
    printf("Top element is: %d\n", peekArrayStack(&s));

    return 0;
}

Linked List-Based Stack

A linked list-based stack uses dynamically allocated nodes, where each node contains data and a pointer to the next node. The top of the stack is represented by a pointer to the first node in the list. This implementation avoids the fixed-size limitation of array-based stacks.

Pros: Dynamic size (no overflow issues until memory runs out), efficient insertion/deletion at the top.

Cons: Slightly more complex to implement, uses more memory per element (due to pointers), less cache friendly.

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

// Structure for a node in the linked list
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Structure to represent a linked list-based stack
typedef struct {
    Node* top; // Pointer to the top node
} LinkedListStack;

// Function to initialize a stack
void initLinkedListStack(LinkedListStack* stack) {
    stack->top = NULL;
}

// Function to check if the stack is empty
int isLinkedListStackEmpty(LinkedListStack* stack) {
    return stack->top == NULL;
}

// Function to push an element onto the stack
void pushLinkedListStack(LinkedListStack* stack, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed! Cannot push %d.\n", data);
        return;
    }
    newNode->data = data;
    newNode->next = stack->top; // New node points to the current top
    stack->top = newNode;       // New node becomes the top
    printf("%d pushed to stack.\n", data);
}

// Function to pop an element from the stack
int popLinkedListStack(LinkedListStack* stack) {
    if (isLinkedListStackEmpty(stack)) {
        printf("Stack Underflow! Cannot pop from empty stack.\n");
        exit(EXIT_FAILURE);
    }
    Node* temp = stack->top;
    int popped = temp->data;
    stack->top = stack->top->next; // Move top to the next node
    free(temp); // Free the popped node's memory
    printf("%d popped from stack.\n", popped);
    return popped;
}

// Function to peek the top element of the stack
int peekLinkedListStack(LinkedListStack* stack) {
    if (isLinkedListStackEmpty(stack)) {
        printf("Stack is empty! No element to peek.\n");
        exit(EXIT_FAILURE);
    }
    return stack->top->data;
}

int main() {
    LinkedListStack s;
    initLinkedListStack(&s);

    pushLinkedListStack(&s, 100);
    pushLinkedListStack(&s, 200);
    pushLinkedListStack(&s, 300);

    printf("Top element is: %d\n", peekLinkedListStack(&s));

    popLinkedListStack(&s);
    printf("Top element is: %d\n", peekLinkedListStack(&s));

    popLinkedListStack(&s);
    popLinkedListStack(&s);

    if (isLinkedListStackEmpty(&s)) {
        printf("Stack is now empty.\n");
    }

    pushLinkedListStack(&s, 400);
    printf("Top element is: %d\n", peekLinkedListStack(&s));

    // Clean up remaining nodes if any (good practice)
    while(!isLinkedListStackEmpty(&s)) {
        popLinkedListStack(&s);
    }

    return 0;
}

Understanding Queues

What is a Queue?

A Queue is a linear data structure that follows the FIFO (First In, First Out) principle. Think of a line of people waiting for a service: the first person in line is the first one to be served, and new people join at the end of the line.

Core Queue Operations

Queues typically support the following operations:

• enqueue: Adds an element to the rear (back) of the queue.
• dequeue: Removes and returns the element from the front of the queue.
• front (or peek): Returns the front element without removing it.
• rear: Returns the rear element without removing it.
• isEmpty: Checks if the queue is empty.
• isFull: (For array-based queues) Checks if the queue has reached its maximum capacity.

Implementing a Queue in C

Array-Based Queue (Circular Queue)

A simple linear array-based queue suffers from an issue where dequeue operations lead to unused space at the front of the array. To overcome this, we use a circular array. In a circular queue, the last element is connected to the first element, forming a circle. This allows efficient reuse of array slots.

Pros: Efficient memory utilization in a circular buffer, good performance for fixed-size scenarios.

Cons: Fixed size (potential for overflow), slightly more complex index management (modulo arithmetic) than a simple linear array.

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

#define MAX_SIZE 5 // Maximum capacity of the queue

// Structure to represent a circular array-based queue
typedef struct {
    int arr[MAX_SIZE];
    int front; // Index of the front element
    int rear;  // Index of the rear element
    int count; // Number of elements currently in the queue
} CircularArrayQueue;

// Function to initialize a queue
void initCircularArrayQueue(CircularArrayQueue* q) {
    q->front = -1; // -1 can indicate empty, or handle with count
    q->rear = -1;
    q->count = 0;
}

// Function to check if the queue is empty
int isCircularArrayQueueEmpty(CircularArrayQueue* q) {
    return q->count == 0;
}

// Function to check if the queue is full
int isCircularArrayQueueFull(CircularArrayQueue* q) {
    return q->count == MAX_SIZE;
}

// Function to add an element to the rear of the queue
void enqueueCircularArrayQueue(CircularArrayQueue* q, int data) {
    if (isCircularArrayQueueFull(q)) {
        printf("Queue Overflow! Cannot enqueue %d.\n", data);
        return;
    }
    if (isCircularArrayQueueEmpty(q)) {
        q->front = 0; // First element, so front is 0
    }
    q->rear = (q->rear + 1) % MAX_SIZE; // Move rear circularly
    q->arr[q->rear] = data;
    q->count++;
    printf("%d enqueued to queue.\n", data);
}

// Function to remove an element from the front of the queue
int dequeueCircularArrayQueue(CircularArrayQueue* q) {
    if (isCircularArrayQueueEmpty(q)) {
        printf("Queue Underflow! Cannot dequeue from empty queue.\n");
        exit(EXIT_FAILURE);
    }
    int dequeued = q->arr[q->front];
    q->front = (q->front + 1) % MAX_SIZE; // Move front circularly
    q->count--;
    if (isCircularArrayQueueEmpty(q)) { // If queue becomes empty, reset front and rear
        q->front = -1;
        q->rear = -1;
    }
    printf("%d dequeued from queue.\n", dequeued);
    return dequeued;
}

// Function to peek the front element of the queue
int frontCircularArrayQueue(CircularArrayQueue* q) {
    if (isCircularArrayQueueEmpty(q)) {
        printf("Queue is empty! No element at front.\n");
        exit(EXIT_FAILURE);
    }
    return q->arr[q->front];
}

// Function to peek the rear element of the queue
int rearCircularArrayQueue(CircularArrayQueue* q) {
    if (isCircularArrayQueueEmpty(q)) {
        printf("Queue is empty! No element at rear.\n");
        exit(EXIT_FAILURE);
    }
    return q->arr[q->rear];
}

int main() {
    CircularArrayQueue q;
    initCircularArrayQueue(&q);

    enqueueCircularArrayQueue(&q, 10);
    enqueueCircularArrayQueue(&q, 20);
    enqueueCircularArrayQueue(&q, 30);

    printf("Front element is: %d\n", frontCircularArrayQueue(&q));
    printf("Rear element is: %d\n", rearCircularArrayQueue(&q));

    dequeueCircularArrayQueue(&q);
    printf("Front element is: %d\n", frontCircularArrayQueue(&q));
    
    enqueueCircularArrayQueue(&q, 40);
    enqueueCircularArrayQueue(&q, 50);
    enqueueCircularArrayQueue(&q, 60); // This should cause overflow

    printf("Current queue elements count: %d\n", q.count);
    
    dequeueCircularArrayQueue(&q);
    dequeueCircularArrayQueue(&q);
    dequeueCircularArrayQueue(&q);
    dequeueCircularArrayQueue(&q); // This should make it empty

    if (isCircularArrayQueueEmpty(&q)) {
        printf("Queue is now empty.\n");
    }

    return 0;
}

Linked List-Based Queue

A linked list-based queue uses dynamic memory allocation. We maintain two pointers: front (pointing to the first node) and rear (pointing to the last node). This allows for constant-time enqueue and dequeue operations without the fixed-size limitation.

Pros: Dynamic size (no overflow), efficient insertion/deletion (O(1) for both ends).

Cons: More memory overhead per element (due to pointers), slightly more complex implementation.

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

// Structure for a node in the linked list
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Structure to represent a linked list-based queue
typedef struct {
    Node* front; // Pointer to the front node
    Node* rear;  // Pointer to the rear node
} LinkedListQueue;

// Function to initialize a queue
void initLinkedListQueue(LinkedListQueue* q) {
    q->front = NULL;
    q->rear = NULL;
}

// Function to check if the queue is empty
int isLinkedListQueueEmpty(LinkedListQueue* q) {
    return q->front == NULL;
}

// Function to add an element to the rear of the queue
void enqueueLinkedListQueue(LinkedListQueue* q, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed! Cannot enqueue %d.\n", data);
        return;
    }
    newNode->data = data;
    newNode->next = NULL; // New node is always at the end

    if (isLinkedListQueueEmpty(q)) {
        q->front = newNode;
        q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
    printf("%d enqueued to queue.\n", data);
}

// Function to remove an element from the front of the queue
int dequeueLinkedListQueue(LinkedListQueue* q) {
    if (isLinkedListQueueEmpty(q)) {
        printf("Queue Underflow! Cannot dequeue from empty queue.\n");
        exit(EXIT_FAILURE);
    }
    Node* temp = q->front;
    int dequeued = temp->data;
    q->front = q->front->next; // Move front to the next node

    if (q->front == NULL) { // If queue becomes empty, rear also becomes NULL
        q->rear = NULL;
    }
    free(temp); // Free the dequeued node's memory
    printf("%d dequeued from queue.\n", dequeued);
    return dequeued;
}

// Function to peek the front element of the queue
int frontLinkedListQueue(LinkedListQueue* q) {
    if (isLinkedListQueueEmpty(q)) {
        printf("Queue is empty! No element at front.\n");
        exit(EXIT_FAILURE);
    }
    return q->front->data;
}

// Function to peek the rear element of the queue
int rearLinkedListQueue(LinkedListQueue* q) {
    if (isLinkedListQueueEmpty(q)) {
        printf("Queue is empty! No element at rear.\n");
        exit(EXIT_FAILURE);
    }
    return q->rear->data;
}

int main() {
    LinkedListQueue q;
    initLinkedListQueue(&q);

    enqueueLinkedListQueue(&q, 100);
    enqueueLinkedListQueue(&q, 200);
    enqueueLinkedListQueue(&q, 300);

    printf("Front element is: %d\n", frontLinkedListQueue(&q));
    printf("Rear element is: %d\n", rearLinkedListQueue(&q));

    dequeueLinkedListQueue(&q);
    printf("Front element is: %d\n", frontLinkedListQueue(&q));
    
    enqueueLinkedListQueue(&q, 400);
    printf("Rear element is: %d\n", rearLinkedListQueue(&q));

    dequeueLinkedListQueue(&q);
    dequeueLinkedListQueue(&q);
    dequeueLinkedListQueue(&q);

    if (isLinkedListQueueEmpty(&q)) {
        printf("Queue is now empty.\n");
    }

    // Clean up remaining nodes if any (good practice, though theoretically empty here)
    while(!isLinkedListQueueEmpty(&q)) {
        dequeueLinkedListQueue(&q);
    }

    return 0;
}

Real-World Applications

Applications of Stacks

• Function Call Stack: When a program calls a function, its local variables and return address are pushed onto the call stack. When the function finishes, they are popped.
• Undo/Redo Mechanisms: Most software uses stacks to keep track of operations for undoing or redoing actions.
• Expression Evaluation: Converting infix expressions to postfix/prefix and evaluating them.
• Backtracking Algorithms: Used in solving mazes, puzzles (like N-Queens), where you try a path and, if it fails, backtrack to a previous state.

Applications of Queues

• Task Scheduling: Operating systems use queues to manage processes (e.g., CPU scheduling, print spooling).
• Data Buffering: Used in I/O operations, network communication, and streaming to handle data flow between processes with different speeds.
• Breadth-First Search (BFS): A graph traversal algorithm that explores all neighbor nodes at the current depth before moving to nodes at the next depth.
• Simulation: Modeling real-world waiting lines, such as customer service or traffic flow.

Conclusion

Stacks and Queues are fundamental building blocks in computer science. Their distinct LIFO and FIFO behaviors, respectively, make them suitable for a wide array of problems. While array-based implementations offer simplicity and memory locality for fixed-size requirements, linked list-based approaches provide dynamic sizing and flexibility. Mastering both their conceptual understanding and practical implementation in C will significantly enhance your problem-solving toolkit.