Published on

Implementing Stacks and Queues in C Intermediate C Concepts Part 3

Authors

Welcome back to our Intermediate C series! Having tackled dynamic memory allocation and explored the flexibility of linked lists, we're now ready to implement two crucial Abstract Data Types (ADTs): Stacks and Queues. These aren't specific data structures themselves, but rather concepts defining how data can be stored and accessed, often relying on arrays or linked lists for their underlying implementation. Let's dive into the worlds of LIFO and FIFO!

Table of Contents

What are Stacks and Queues?

Stacks and Queues are linear data structures that restrict how elements can be added or removed.

  • Stack: Follows the LIFO (Last-In, First-Out) principle. Imagine a stack of plates – the last plate you put on top is the first one you take off.
  • Queue: Follows the FIFO (First-In, First-Out) principle. Think of a queue or line for tickets – the first person in line is the first person served.

They are called Abstract Data Types because we define what they do (their operations and behavior) separately from how they are implemented (using arrays, linked lists, etc.).

I. Stacks (LIFO)

A stack primarily supports two main operations: pushing (adding) an element onto the top and popping (removing) an element from the top.

Core Stack Operations:

  • push(item): Add an item to the top of the stack.
  • pop(): Remove and return the item from the top of the stack.
  • peek() or top(): Return the top item without removing it.
  • isEmpty(): Check if the stack is empty.
  • isFull(): (Relevant for array-based implementation) Check if the stack is full.

Applications: Function call management (the call stack), expression evaluation (infix to postfix conversion), backtracking algorithms (like solving mazes), undo/redo features in software.

Stack Implementation using Arrays

This is often the simplest implementation if the maximum size is known beforehand.

Structure:

#include <stdio.h>
#include <stdlib.h> // For malloc/free if creating dynamically
#include <limits.h> // For INT_MIN or other error indicators

#define MAX_SIZE 100 // Example fixed size

typedef struct {
    int items[MAX_SIZE]; // Array to hold stack elements
    int top;             // Index of the top element (-1 means empty)
    // Optionally add 'capacity' if using dynamic arrays
} StackArray;

// Function to create/initialize a stack
StackArray* createStackArray() {
    // Could allocate dynamically: StackArray* stack = malloc(sizeof(StackArray));
    // For simplicity here, we'll use a static/global or local instance
    // If allocated dynamically, remember to check for NULL and free later.
    static StackArray stack; // Example using static storage
    stack.top = -1; // Initialize stack as empty
    return &stack;
}

// Check if the stack is full
int isFull_Array(StackArray* stack) {
    return stack->top == MAX_SIZE - 1;
}

// Check if the stack is empty
int isEmpty_Array(StackArray* stack) {
    return stack->top == -1;
}

// Push operation
void push_Array(StackArray* stack, int item) {
    if (isFull_Array(stack)) {
        fprintf(stderr, "Stack Overflow! Cannot push %d.\n", item);
        return;
    }
    // Increment top, then add item
    stack->items[++(stack->top)] = item;
    printf("Pushed %d onto the array stack.\n", item);
}

// Pop operation
int pop_Array(StackArray* stack) {
    if (isEmpty_Array(stack)) {
        fprintf(stderr, "Stack Underflow! Cannot pop.\n");
        return INT_MIN; // Or some other error indicator
    }
    // Return item at top, then decrement top
    printf("Popped %d from the array stack.\n", stack->items[stack->top]);
    return stack->items[(stack->top)--];
}

// Peek operation
int peek_Array(StackArray* stack) {
     if (isEmpty_Array(stack)) {
        fprintf(stderr, "Stack is empty! Cannot peek.\n");
        return INT_MIN; // Error indicator
    }
    return stack->items[stack->top];
}

// Example Usage (Array Stack)
void exampleArrayStack() {
    printf("\n--- Array Stack Example ---\n");
    StackArray* myStack = createStackArray();

    push_Array(myStack, 10);
    push_Array(myStack, 20);
    push_Array(myStack, 30);

    printf("Top element is: %d\n", peek_Array(myStack)); // Should be 30

    pop_Array(myStack); // Popped 30
    pop_Array(myStack); // Popped 20

    printf("Is stack empty? %s\n", isEmpty_Array(myStack) ? "Yes" : "No"); // No

    pop_Array(myStack); // Popped 10
    printf("Is stack empty? %s\n", isEmpty_Array(myStack) ? "Yes" : "No"); // Yes

    pop_Array(myStack); // Stack Underflow!
    printf("--- End Array Stack Example ---\n");
}

Explanation:

  • We use an array items to store data.
  • An integer top tracks the index of the last inserted element. top = -1 indicates an empty stack.
  • push: Increments top, then places the item at items[top]. Checks for overflow first.
  • pop: Returns the item at items[top], then decrements top. Checks for underflow first.
  • peek: Returns the item at items[top] without modifying top.
  • Limitation: Fixed size (MAX_SIZE). You could use malloc/realloc for a dynamic array, but that adds complexity.

Stack Implementation using Linked Lists

This leverages the efficiency of adding/removing from the beginning of a linked list.

Structure: We need the Node structure from the previous tutorial.

// Re-using or redefining Node structure
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Stack structure only needs a pointer to the top node (head of the list)
typedef struct {
    Node* top; // Points to the top node (head of the linked list)
} StackLL;

// Function to create an empty stack
StackLL* createStackLL() {
    StackLL* stack = (StackLL*)malloc(sizeof(StackLL));
    if (!stack) {
        perror("Failed to allocate stack");
        return NULL;
    }
    stack->top = NULL; // Initialize stack as empty
    return stack;
}

// Check if the stack is empty
int isEmpty_LL(StackLL* stack) {
    return stack->top == NULL;
}

// Push operation (equivalent to inserting at the beginning of LL)
void push_LL(StackLL* stack, int data) {
    // Create a new node
    Node* newNode = (Node*)malloc(sizeof(Node));
     if (!newNode) {
        perror("Failed to allocate node for push");
        return; // Or handle error more gracefully
    }
    newNode->data = data;

    // Link the new node to the current top
    newNode->next = stack->top;

    // Update the top to point to the new node
    stack->top = newNode;
    printf("Pushed %d onto the linked list stack.\n", data);
}

// Pop operation (equivalent to deleting the first node of LL)
int pop_LL(StackLL* stack) {
    if (isEmpty_LL(stack)) {
        fprintf(stderr, "Stack Underflow! Cannot pop from linked list stack.\n");
        return INT_MIN; // Error indicator
    }

    // Store the current top node
    Node* temp = stack->top;
    int poppedData = temp->data;

    // Update the top to the next node
    stack->top = stack->top->next;

    // Free the old top node
    free(temp);
    temp = NULL;

    printf("Popped %d from the linked list stack.\n", poppedData);
    return poppedData;
}

// Peek operation
int peek_LL(StackLL* stack) {
    if (isEmpty_LL(stack)) {
        fprintf(stderr, "Stack is empty! Cannot peek linked list stack.\n");
        return INT_MIN; // Error indicator
    }
    return stack->top->data;
}

// Function to free the entire stack (essential!)
void freeStackLL(StackLL* stack) {
    Node* current = stack->top;
    Node* nextNode;
    printf("Freeing linked list stack...\n");
    while (current != NULL) {
        nextNode = current->next;
        free(current);
        current = nextNode;
    }
    free(stack); // Free the stack structure itself
    printf("Linked list stack freed.\n");
}


// Example Usage (Linked List Stack)
void exampleLLStack() {
    printf("\n--- Linked List Stack Example ---\n");
    StackLL* myStack = createStackLL();
     if (!myStack) return; // Allocation check

    push_LL(myStack, 100);
    push_LL(myStack, 200);
    push_LL(myStack, 300);

    printf("Top element is: %d\n", peek_LL(myStack)); // Should be 300

    pop_LL(myStack); // Popped 300
    pop_LL(myStack); // Popped 200

    printf("Is stack empty? %s\n", isEmpty_LL(myStack) ? "Yes" : "No"); // No

    pop_LL(myStack); // Popped 100
    printf("Is stack empty? %s\n", isEmpty_LL(myStack) ? "Yes" : "No"); // Yes

    pop_LL(myStack); // Stack Underflow!

    // IMPORTANT: Free the stack memory
    freeStackLL(myStack);
    printf("--- End Linked List Stack Example ---\n");
}

Explanation:

  • The stack only needs a top pointer, which functions exactly like the head pointer in our basic linked list.
  • push: Creates a new node and inserts it at the beginning of the list (updating top). This is O(1).
  • pop: Removes the first node (the one top points to), updates top to the next node, and frees the removed node. This is O(1).
  • peek: Returns the data from the top node.
  • Advantage: Dynamic size, no artificial limit (only available memory).

II. Queues (FIFO)

A queue primarily supports adding elements to the rear (back) and removing elements from the front.

Core Queue Operations:

  • enqueue(item): Add an item to the rear of the queue.
  • dequeue(): Remove and return the item from the front of the queue.
  • peek() or front(): Return the front item without removing it.
  • isEmpty(): Check if the queue is empty.
  • isFull(): (Relevant for array-based implementation) Check if the queue is full.

Applications: Scheduling tasks (CPU scheduling, print queues), handling asynchronous requests (web server requests), Breadth-First Search (BFS) in graphs, buffers in data streaming.

Queue Implementation using Linked Lists

This is often the most intuitive way to implement a queue, directly modeling the "line" concept. We need pointers to both the front and rear of the list for efficiency.

Structure:

// Re-using or redefining Node structure
// typedef struct Node { ... } Node; (Assuming defined above)

// Queue structure needs pointers to both front and rear nodes
typedef struct {
    Node* front; // Points to the front node (head of the list)
    Node* rear;  // Points to the rear node (tail of the list)
} QueueLL;

// Function to create an empty queue
QueueLL* createQueueLL() {
    QueueLL* queue = (QueueLL*)malloc(sizeof(QueueLL));
     if (!queue) {
        perror("Failed to allocate queue");
        return NULL;
    }
    queue->front = NULL;
    queue->rear = NULL;
    return queue;
}

// Check if the queue is empty
int isEmpty_QueueLL(QueueLL* queue) {
    return queue->front == NULL; // If front is NULL, queue is empty
}

// Enqueue operation (add to the rear/tail)
void enqueue_LL(QueueLL* queue, int data) {
    // Create a new node
    Node* newNode = (Node*)malloc(sizeof(Node));
     if (!newNode) {
        perror("Failed to allocate node for enqueue");
        return;
    }
    newNode->data = data;
    newNode->next = NULL; // Node added at the end always points to NULL

    // If queue is empty, new node is both front and rear
    if (queue->rear == NULL) { // or check isEmpty_QueueLL(queue)
        queue->front = newNode;
        queue->rear = newNode;
        printf("Enqueued %d (first element).\n", data);
        return;
    }

    // Link the current rear node to the new node
    queue->rear->next = newNode;

    // Update the rear pointer to the new node
    queue->rear = newNode;
    printf("Enqueued %d to the rear.\n", data);
}

// Dequeue operation (remove from the front/head)
int dequeue_LL(QueueLL* queue) {
    if (isEmpty_QueueLL(queue)) {
        fprintf(stderr, "Queue Underflow! Cannot dequeue.\n");
        return INT_MIN; // Error indicator
    }

    // Store the current front node
    Node* temp = queue->front;
    int dequeuedData = temp->data;

    // Move front pointer to the next node
    queue->front = queue->front->next;

    // VERY IMPORTANT: If front becomes NULL, the queue is now empty,
    // so rear must also become NULL!
    if (queue->front == NULL) {
        queue->rear = NULL;
    }

    // Free the old front node
    free(temp);
    temp = NULL;

    printf("Dequeued %d from the front.\n", dequeuedData);
    return dequeuedData;
}

// Peek/Front operation
int peek_QueueLL(QueueLL* queue) {
     if (isEmpty_QueueLL(queue)) {
        fprintf(stderr, "Queue is empty! Cannot peek.\n");
        return INT_MIN; // Error indicator
    }
    return queue->front->data;
}

// Function to free the entire queue
void freeQueueLL(QueueLL* queue) {
     Node* current = queue->front;
    Node* nextNode;
    printf("Freeing linked list queue...\n");
    while (current != NULL) {
        nextNode = current->next;
        free(current);
        current = nextNode;
    }
    free(queue); // Free the queue structure itself
     printf("Linked list queue freed.\n");
}

// Example Usage (Linked List Queue)
void exampleLLQueue() {
     printf("\n--- Linked List Queue Example ---\n");
    QueueLL* myQueue = createQueueLL();
    if (!myQueue) return;

    enqueue_LL(myQueue, 10);
    enqueue_LL(myQueue, 20);
    enqueue_LL(myQueue, 30);

    printf("Front element is: %d\n", peek_QueueLL(myQueue)); // Should be 10

    dequeue_LL(myQueue); // Dequeued 10
    printf("Front element is: %d\n", peek_QueueLL(myQueue)); // Should be 20

    enqueue_LL(myQueue, 40);

    dequeue_LL(myQueue); // Dequeued 20
    dequeue_LL(myQueue); // Dequeued 30
    printf("Is queue empty? %s\n", isEmpty_QueueLL(myQueue) ? "Yes" : "No"); // No

    dequeue_LL(myQueue); // Dequeued 40
    printf("Is queue empty? %s\n", isEmpty_QueueLL(myQueue) ? "Yes" : "No"); // Yes

    dequeue_LL(myQueue); // Queue Underflow!

    // IMPORTANT: Free the queue memory
    freeQueueLL(myQueue);
     printf("--- End Linked List Queue Example ---\n");
}

Explanation:

  • The queue structure holds two pointers: front (like head) and rear (points to the last node).
  • enqueue: Creates a new node. If the queue is empty, sets both front and rear to the new node. Otherwise, appends the node after the current rear and updates rear. This is O(1).
  • dequeue: Removes the node pointed to by front. Updates front to the next node. Crucially, if front becomes NULL after the update (meaning the last element was dequeued), rear must also be set to NULL. Frees the old front node. This is O(1).
  • peek: Returns data from the front node.
  • Advantage: Efficient O(1) time complexity for both enqueue and dequeue, fully dynamic size.

Queue Implementation using Arrays (Circular Queue - Conceptual)

Implementing a queue efficiently with a standard array is tricky because dequeuing from the front requires shifting all other elements (O(n)). A Circular Array (or Ring Buffer) solves this.

Concept:

  • Use an array and two indices: front (index of the first element) and rear (index after the last element).
  • When front or rear reach the end of the array, they wrap around to the beginning using the modulo operator (% capacity).
  • Special conditions are needed to distinguish between a full queue and an empty queue (e.g., keeping a count of elements, or leaving one slot unused).

While powerful, the index management and full/empty checks in circular queues can be complex to implement correctly compared to the linked list approach. For brevity and clarity, we focused on the linked list queue implementation above, which is often preferred for its simplicity and dynamic nature in C when fixed capacity isn't a strict requirement.

Choosing Between Array and Linked List Implementations

  • Stack:
    • Array: Simpler if max size is known, potentially slightly faster due to memory locality. Risk of overflow if max size is underestimated.
    • Linked List: More flexible (dynamic size), no overflow risk (besides running out of memory), O(1) push/pop are naturally efficient. Generally preferred unless performance is absolutely critical and size is fixed.
  • Queue:
    • Circular Array: Can be very efficient if implemented correctly, good memory locality. Fixed size, complex index management.
    • Linked List: Much simpler logic for enqueue/dequeue, dynamic size, O(1) operations are straightforward. Often the preferred implementation in C for general-purpose queues.

Conclusion

Stacks (LIFO) and Queues (FIFO) are fundamental abstract data types with numerous applications in computer science. We've seen how to implement them in C using both fixed-size arrays and, more flexibly, dynamic linked lists. Understanding the underlying principles and the trade-offs between implementation methods allows you to choose the right tool for the job. Mastering these is another key step in becoming a proficient C programmer.

Next up, we'll venture into non-linear structures as we get an Introduction to Trees and Graphs in C!

Further Reading & Related Posts

Discuss on Twitter • View on GitHub