C Stacks and Queues: LIFO and FIFO Data Structures

In the world of computer programming, data structures play a crucial role in organizing and managing information efficiently. Two fundamental data structures that every C programmer should master are stacks and queues. These structures follow different principles for data access and manipulation, making them suitable for various applications. In this comprehensive guide, we'll dive deep into the world of stacks and queues, exploring their implementations, operations, and real-world use cases in C programming.

Table of Contents

Understanding Stacks: Last-In-First-Out (LIFO)

🏗️ A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. This means that the last element added to the stack will be the first one to be removed. Think of a stack of plates in a cafeteria – you add plates to the top and remove them from the top as well.

Key Operations on Stacks

Push: Add an element to the top of the stack
Pop: Remove the top element from the stack
Peek: View the top element without removing it
isEmpty: Check if the stack is empty
isFull: Check if the stack is full (for array-based implementations)

Implementing a Stack in C

Let's implement a simple stack using an array in C:

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

#define MAX_SIZE 100

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

void initializeStack(Stack *s) {
    s->top = -1;
}

bool isEmpty(Stack *s) {
    return s->top == -1;
}

bool isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

void push(Stack *s, int value) {
    if (isFull(s)) {
        printf("Stack Overflow! Cannot push %d\n", value);
    } else {
        s->top++;
        s->items[s->top] = value;
        printf("Pushed %d\n", value);
    }
}

int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack Underflow! Cannot pop from an empty stack\n");
        return -1;
    } else {
        int value = s->items[s->top];
        s->top--;
        printf("Popped %d\n", value);
        return value;
    }
}

int peek(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty\n");
        return -1;
    } else {
        return s->items[s->top];
    }
}

int main() {
    Stack s;
    initializeStack(&s);

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

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

    pop(&s);
    pop(&s);

    printf("Is stack empty? %s\n", isEmpty(&s) ? "Yes" : "No");

    pop(&s);
    pop(&s);  // This will cause underflow

    return 0;
}

Let's break down this implementation:

We define a Stack structure that contains an array items to store the elements and an integer top to keep track of the top of the stack.
initializeStack sets the top to -1, indicating an empty stack.
isEmpty and isFull check if the stack is empty or full, respectively.
push adds an element to the top of the stack, incrementing top.
pop removes and returns the top element, decrementing top.
peek returns the top element without removing it.
In the main function, we demonstrate the usage of these operations.

When you run this program, you'll see the following output:

Pushed 10
Pushed 20
Pushed 30
Top element: 30
Popped 30
Popped 20
Is stack empty? No
Popped 10
Stack Underflow! Cannot pop from an empty stack

This output shows the stack operations in action, including pushing elements, peeking at the top, popping elements, and handling stack underflow.

Understanding Queues: First-In-First-Out (FIFO)

🚶‍♂️🚶‍♀️🚶‍♂️ A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. This means that the first element added to the queue will be the first one to be removed. Think of a queue of people waiting in line – the first person to join the line is the first to be served.

Key Operations on Queues

Enqueue: Add an element to the rear of the queue
Dequeue: Remove an element from the front of the queue
Front: View the front element without removing it
Rear: View the rear element without removing it
isEmpty: Check if the queue is empty
isFull: Check if the queue is full (for array-based implementations)

Implementing a Queue in C

Let's implement a simple queue using an array in C:

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

#define MAX_SIZE 5

typedef struct {
    int items[MAX_SIZE];
    int front;
    int rear;
    int size;
} Queue;

void initializeQueue(Queue *q) {
    q->front = 0;
    q->rear = -1;
    q->size = 0;
}

bool isEmpty(Queue *q) {
    return q->size == 0;
}

bool isFull(Queue *q) {
    return q->size == MAX_SIZE;
}

void enqueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("Queue is full! Cannot enqueue %d\n", value);
    } else {
        q->rear = (q->rear + 1) % MAX_SIZE;
        q->items[q->rear] = value;
        q->size++;
        printf("Enqueued %d\n", value);
    }
}

int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty! Cannot dequeue\n");
        return -1;
    } else {
        int value = q->items[q->front];
        q->front = (q->front + 1) % MAX_SIZE;
        q->size--;
        printf("Dequeued %d\n", value);
        return value;
    }
}

int front(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    return q->items[q->front];
}

int rear(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    return q->items[q->rear];
}

void displayQueue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return;
    }
    printf("Queue: ");
    for (int i = 0; i < q->size; i++) {
        int index = (q->front + i) % MAX_SIZE;
        printf("%d ", q->items[index]);
    }
    printf("\n");
}

int main() {
    Queue q;
    initializeQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    displayQueue(&q);

    printf("Front: %d, Rear: %d\n", front(&q), rear(&q));

    dequeue(&q);
    enqueue(&q, 40);
    displayQueue(&q);

    enqueue(&q, 50);
    enqueue(&q, 60);  // This will cause overflow
    displayQueue(&q);

    return 0;
}

Let's break down this implementation:

We define a Queue structure that contains an array items to store the elements, integers front and rear to keep track of the front and rear of the queue, and size to store the current number of elements.
initializeQueue sets the initial values for an empty queue.
isEmpty and isFull check if the queue is empty or full, respectively.
enqueue adds an element to the rear of the queue, using modulo arithmetic to wrap around the array.
dequeue removes and returns the front element, also using modulo arithmetic.
front and rear return the front and rear elements without removing them.
displayQueue shows the current state of the queue.
In the main function, we demonstrate the usage of these operations.

When you run this program, you'll see the following output:

Enqueued 10
Enqueued 20
Enqueued 30
Queue: 10 20 30 
Front: 10, Rear: 30
Dequeued 10
Enqueued 40
Queue: 20 30 40 
Enqueued 50
Queue is full! Cannot enqueue 60
Queue: 20 30 40 50

This output demonstrates the queue operations, including enqueuing elements, dequeuing, displaying the queue state, and handling queue overflow.

Practical Applications of Stacks and Queues

Now that we understand how stacks and queues work, let's explore some practical applications:

Stack Applications

Function Call Management: 📞 The call stack in programming languages uses a stack to manage function calls and returns.
Expression Evaluation: 🧮 Stacks are used to evaluate arithmetic expressions, especially in postfix notation.
Undo Mechanism: ↩️ The undo functionality in text editors often uses a stack to keep track of changes.
Backtracking Algorithms: 🔍 Many backtracking algorithms use stacks to keep track of the current state and backtrack when needed.

Let's implement a simple postfix expression evaluator using a stack:

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

#define MAX_SIZE 100

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

void initializeStack(Stack *s) {
    s->top = -1;
}

void push(Stack *s, int value) {
    s->top++;
    s->items[s->top] = value;
}

int pop(Stack *s) {
    int value = s->items[s->top];
    s->top--;
    return value;
}

int evaluatePostfix(char* expression) {
    Stack s;
    initializeStack(&s);

    for (int i = 0; expression[i]; i++) {
        if (isdigit(expression[i])) {
            push(&s, expression[i] - '0');
        } else {
            int val1 = pop(&s);
            int val2 = pop(&s);
            switch (expression[i]) {
                case '+': push(&s, val2 + val1); break;
                case '-': push(&s, val2 - val1); break;
                case '*': push(&s, val2 * val1); break;
                case '/': push(&s, val2 / val1); break;
            }
        }
    }
    return pop(&s);
}

int main() {
    char expr[] = "23*5+";
    printf("Postfix Expression: %s\n", expr);
    printf("Result: %d\n", evaluatePostfix(expr));
    return 0;
}

This program evaluates the postfix expression "235+" (which is equivalent to (23)+5 in infix notation). The output will be:

Postfix Expression: 23*5+
Result: 11

Queue Applications

Task Scheduling: 📅 Operating systems use queues for task scheduling and process management.
Breadth-First Search: 🌳 Graph algorithms like BFS use queues to explore nodes level by level.
Printer Spooling: 🖨️ Print jobs are typically managed using a queue.
Buffering: 🔄 Queues are used in various buffering scenarios, such as in streaming applications.

Let's implement a simple task scheduler using a queue:

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

#define MAX_TASKS 10
#define MAX_NAME_LENGTH 50

typedef struct {
    char name[MAX_NAME_LENGTH];
    int priority;
} Task;

typedef struct {
    Task tasks[MAX_TASKS];
    int front;
    int rear;
    int size;
} TaskQueue;

void initializeTaskQueue(TaskQueue *q) {
    q->front = 0;
    q->rear = -1;
    q->size = 0;
}

void enqueueTask(TaskQueue *q, const char* name, int priority) {
    if (q->size == MAX_TASKS) {
        printf("Task queue is full! Cannot add task: %s\n", name);
        return;
    }
    q->rear = (q->rear + 1) % MAX_TASKS;
    strncpy(q->tasks[q->rear].name, name, MAX_NAME_LENGTH - 1);
    q->tasks[q->rear].name[MAX_NAME_LENGTH - 1] = '\0';
    q->tasks[q->rear].priority = priority;
    q->size++;
    printf("Task added: %s (Priority: %d)\n", name, priority);
}

Task dequeueTask(TaskQueue *q) {
    Task emptyTask = {"", 0};
    if (q->size == 0) {
        printf("Task queue is empty!\n");
        return emptyTask;
    }
    Task task = q->tasks[q->front];
    q->front = (q->front + 1) % MAX_TASKS;
    q->size--;
    return task;
}

void displayTasks(TaskQueue *q) {
    if (q->size == 0) {
        printf("No tasks in the queue.\n");
        return;
    }
    printf("Current tasks in the queue:\n");
    for (int i = 0; i < q->size; i++) {
        int index = (q->front + i) % MAX_TASKS;
        printf("%d. %s (Priority: %d)\n", i+1, q->tasks[index].name, q->tasks[index].priority);
    }
}

int main() {
    TaskQueue taskQueue;
    initializeTaskQueue(&taskQueue);

    enqueueTask(&taskQueue, "Send email", 2);
    enqueueTask(&taskQueue, "Write report", 1);
    enqueueTask(&taskQueue, "Call client", 3);

    displayTasks(&taskQueue);

    Task nextTask = dequeueTask(&taskQueue);
    printf("Executing task: %s\n", nextTask.name);

    displayTasks(&taskQueue);

    return 0;
}

This program simulates a simple task scheduler using a queue. When you run it, you'll see output similar to this:

Task added: Send email (Priority: 2)
Task added: Write report (Priority: 1)
Task added: Call client (Priority: 3)
Current tasks in the queue:
1. Send email (Priority: 2)
2. Write report (Priority: 1)
3. Call client (Priority: 3)
Executing task: Send email
Current tasks in the queue:
1. Write report (Priority: 1)
2. Call client (Priority: 3)

Advanced Concepts and Variations

While we've covered the basics of stacks and queues, there are several advanced concepts and variations worth mentioning:

1. Double-Ended Queue (Deque)

A deque (pronounced "deck") is a queue that allows insertion and deletion at both ends. It combines the features of both stacks and queues.

2. Priority Queue

A priority queue is a type of queue where elements have associated priorities. Elements with higher priority are dequeued before elements with lower priority.

3. Circular Queue

A circular queue is an efficient implementation of a queue using a fixed-size array. It uses modulo arithmetic to wrap around the array, making better use of space.

4. Stack and Queue using Linked Lists

While we implemented stacks and queues using arrays, they can also be implemented using linked lists, which offer dynamic sizing.

Performance Considerations

When working with stacks and queues, it's important to consider their performance characteristics:

Operation	Stack (Array)	Stack (Linked List)	Queue (Array)	Queue (Linked List)
Push/Enqueue	O(1)	O(1)	O(1)	O(1)
Pop/Dequeue	O(1)	O(1)	O(1)	O(1)
Peek/Front	O(1)	O(1)	O(1)	O(1)
isEmpty	O(1)	O(1)	O(1)	O(1)
isFull	O(1)	N/A	O(1)	N/A

As you can see, most operations on stacks and queues have constant time complexity, making them very efficient for their intended use cases.

Conclusion

Stacks and queues are fundamental data structures in computer science and programming. Their distinct behaviors – Last-In-First-Out for stacks and First-In-First-Out for queues – make them suitable for a wide range of applications. By mastering these structures in C, you'll have powerful tools at your disposal for solving various programming challenges.

Remember:

📚 Use stacks when you need to reverse order or keep track of state that needs to be unwound (like function calls or undo operations).
🚶‍♂️🚶‍♀️ Use queues when you need to maintain order and process items in the sequence they arrived (like task scheduling or breadth-first algorithms).

As you continue your journey in C programming, you'll find countless opportunities to apply these data structures in creative and efficient ways. Happy coding!