Stacks and Queues in C: Implementation and Applications

drwxr-xr-x2026-01-135 min0 views

Stacks and queues are fundamental linear data structures that manage collections of elements with specific access patterns—stacks follow Last-In-First-Out (LIFO) principle where the most recently added element is removed first, while queues follow First-In-First-Out (FIFO) principle where elements are removed in the order they were added [web:297][web:298]. These abstract data types are essential building blocks in computer science, used in everything from function call management and expression evaluation to task scheduling and breadth-first search algorithms. Both can be implemented using arrays for fixed-size applications or linked lists for dynamic sizing, each approach offering different trade-offs between memory usage, performance, and flexibility [web:296][web:301].

This comprehensive guide explores complete stack and queue implementations in C, covering array-based stack implementation with push and pop operations, linked list-based stack for dynamic sizing, array-based queue implementation with enqueue and dequeue, circular queue optimization to prevent wasted space, linked list-based queue implementation, and real-world applications ranging from function call management to job scheduling [web:302]. Mastering these data structures is crucial for algorithm design, systems programming, and understanding more complex structures like trees and graphs.

Understanding Stack: LIFO Principle

A stack operates like a pile of plates where you can only add or remove from the top—the last plate added is the first one removed [web:297]. This LIFO behavior makes stacks ideal for scenarios requiring reverse-order processing, tracking state history, and managing nested structures like function calls and parentheses matching.

cstack_basics.c

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

int main() {
    printf("=== Stack: LIFO (Last-In-First-Out) ===\n\n");
    
    // Visual representation:
    // Top -> [5]  <- Last added, first to be removed
    //        [4]
    //        [3]
    //        [2]
    //        [1]  <- First added, last to be removed
    
    printf("LIFO Principle:\n");
    printf("Push 1: [1]\n");
    printf("Push 2: [1][2]\n");
    printf("Push 3: [1][2][3]\n");
    printf("Pop:    [1][2]     (removed 3)\n");
    printf("Pop:    [1]        (removed 2)\n\n");
    
    // Primary stack operations:
    // 1. Push  - Add element to top - O(1)
    // 2. Pop   - Remove element from top - O(1)
    // 3. Peek  - View top element without removing - O(1)
    // 4. isEmpty - Check if stack is empty - O(1)
    // 5. isFull - Check if stack is full (array-based) - O(1)
    
    printf("Stack Applications:\n");
    printf("1. Function call management (call stack)\n");
    printf("2. Expression evaluation and conversion\n");
    printf("3. Undo/Redo functionality\n");
    printf("4. Backtracking algorithms\n");
    printf("5. Syntax parsing and matching brackets\n");
    
    return 0;
}

Stack Implementation Using Array

Array-based stack implementation uses a fixed-size array with a top pointer tracking the index of the topmost element [web:296]. This approach offers fast O(1) operations and cache-friendly memory access but has a fixed capacity limitation requiring overflow checks before pushing elements.

carray_stack.c

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

#define MAX_SIZE 100

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

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

// Check if stack is full
bool isFull(Stack* s) {
    return s->top == MAX_SIZE - 1;
}

// Check if stack is empty
bool isEmpty(Stack* s) {
    return s->top == -1;
}

// Push element onto stack - O(1)
void push(Stack* s, int value) {
    if (isFull(s)) {
        printf("Stack Overflow! Cannot push %d\n", value);
        return;
    }
    
    s->items[++(s->top)] = value;
    printf("Pushed %d\n", value);
}

// Pop element from stack - O(1)
int pop(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack Underflow! Stack is empty\n");
        return -1;
    }
    
    return s->items[(s->top)--];
}

// Peek at top element without removing - O(1)
int peek(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack is empty\n");
        return -1;
    }
    
    return s->items[s->top];
}

// Get current size of stack
int size(Stack* s) {
    return s->top + 1;
}

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

int main() {
    printf("=== Array-Based Stack Implementation ===\n\n");
    
    Stack stack;
    initStack(&stack);
    
    // Push operations
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
    push(&stack, 40);
    push(&stack, 50);
    
    printf("\n");
    display(&stack);
    
    // Peek operation
    printf("\nTop element: %d\n", peek(&stack));
    printf("Stack size: %d\n", size(&stack));
    
    // Pop operations
    printf("\nPopping elements:\n");
    printf("Popped: %d\n", pop(&stack));
    printf("Popped: %d\n", pop(&stack));
    
    printf("\n");
    display(&stack);
    
    // Push more elements
    printf("\n");
    push(&stack, 60);
    push(&stack, 70);
    
    printf("\n");
    display(&stack);
    
    return 0;
}

Overflow Check: Always check if the stack is full before pushing [web:296]. Array-based stacks have fixed capacity—pushing to a full stack causes overflow errors.

Stack Implementation Using Linked List

Linked list-based stack implementation eliminates the fixed-size limitation by dynamically allocating nodes for each element [web:294][web:295]. The top pointer references the head of the linked list, with push adding nodes at the beginning and pop removing from the beginning—both O(1) operations maintaining LIFO order.

clinkedlist_stack.c

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

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

// Stack structure with top pointer
typedef struct {
    Node* top;
} Stack;

// Initialize stack
void initStack(Stack* s) {
    s->top = NULL;
}

// Check if stack is empty
bool isEmpty(Stack* s) {
    return s->top == NULL;
}

// Push element onto stack - O(1)
void push(Stack* s, int value) {
    // Create new node
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return;
    }
    
    // Initialize node
    newNode->data = value;
    newNode->next = s->top;
    
    // Update top pointer
    s->top = newNode;
    
    printf("Pushed %d\n", value);
}

// Pop element from stack - O(1)
int pop(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack Underflow! Stack is empty\n");
        return -1;
    }
    
    // Save top node and data
    Node* temp = s->top;
    int popped = temp->data;
    
    // Update top pointer
    s->top = s->top->next;
    
    // Free memory
    free(temp);
    
    return popped;
}

// Peek at top element - O(1)
int peek(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack is empty\n");
        return -1;
    }
    
    return s->top->data;
}

// Display stack contents
void display(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack is empty\n");
        return;
    }
    
    printf("Stack (top to bottom): ");
    Node* current = s->top;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

// Free all nodes in stack
void freeStack(Stack* s) {
    while (!isEmpty(s)) {
        pop(s);
    }
}

int main() {
    printf("=== Linked List-Based Stack Implementation ===\n\n");
    
    Stack stack;
    initStack(&stack);
    
    // Push operations
    push(&stack, 100);
    push(&stack, 200);
    push(&stack, 300);
    push(&stack, 400);
    
    printf("\n");
    display(&stack);
    
    // Peek and pop
    printf("\nTop element: %d\n", peek(&stack));
    printf("\nPopping elements:\n");
    printf("Popped: %d\n", pop(&stack));
    printf("Popped: %d\n", pop(&stack));
    
    printf("\n");
    display(&stack);
    
    // Advantages: No size limit (dynamic allocation)
    printf("\nAdvantage: Can push unlimited elements (until memory exhausted)\n");
    push(&stack, 500);
    push(&stack, 600);
    push(&stack, 700);
    
    printf("\n");
    display(&stack);
    
    // Clean up
    freeStack(&stack);
    printf("\nStack freed\n");
    
    return 0;
}

Dynamic Sizing: Linked list stacks grow and shrink dynamically without fixed capacity [web:294]. This eliminates overflow errors but requires memory allocation for each push operation.

Understanding Queue: FIFO Principle

A queue operates like a line at a ticket counter where the first person to arrive is served first [web:297][web:298]. This FIFO behavior makes queues essential for fair resource allocation, task scheduling, and breadth-first traversal algorithms where processing order must match arrival order.

cqueue_basics.c

#include <stdio.h>

int main() {
    printf("=== Queue: FIFO (First-In-First-Out) ===\n\n");
    
    // Visual representation:
    // Front -> [1][2][3][4][5] <- Rear
    //          ^               ^
    //          |               |
    //      Dequeue here    Enqueue here
    
    printf("FIFO Principle:\n");
    printf("Enqueue 1: [1]\n");
    printf("Enqueue 2: [1][2]\n");
    printf("Enqueue 3: [1][2][3]\n");
    printf("Dequeue:   [2][3]     (removed 1)\n");
    printf("Dequeue:   [3]        (removed 2)\n\n");
    
    // Primary queue operations:
    // 1. Enqueue - Add element at rear - O(1)
    // 2. Dequeue - Remove element from front - O(1)
    // 3. Front   - View front element - O(1)
    // 4. Rear    - View rear element - O(1)
    // 5. isEmpty - Check if queue is empty - O(1)
    // 6. isFull  - Check if queue is full (array) - O(1)
    
    printf("Queue Applications:\n");
    printf("1. CPU task scheduling\n");
    printf("2. Printer job management\n");
    printf("3. Breadth-first search (BFS)\n");
    printf("4. Network packet handling\n");
    printf("5. Call center systems\n");
    printf("6. Asynchronous data transfer\n");
    
    return 0;
}

Circular Queue Implementation Using Array

Circular queue optimizes array-based implementation by treating the array as circular—when rear reaches the end, it wraps around to the beginning if space is available [web:301]. This prevents wasted space that occurs in simple linear queues where dequeued positions cannot be reused, maximizing array utilization.

ccircular_queue.c

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

#define MAX_SIZE 5

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

// Initialize queue
void initQueue(Queue* q) {
    q->front = 0;
    q->rear = -1;
    q->size = 0;
}

// Check if queue is full
bool isFull(Queue* q) {
    return q->size == MAX_SIZE;
}

// Check if queue is empty
bool isEmpty(Queue* q) {
    return q->size == 0;
}

// Enqueue (add element at rear) - O(1)
void enqueue(Queue* q, int value) {
    if (isFull(q)) {
        printf("Queue Overflow! Cannot enqueue %d\n", value);
        return;
    }
    
    // Circular increment: wrap around to 0 when reaching MAX_SIZE
    q->rear = (q->rear + 1) % MAX_SIZE;
    q->items[q->rear] = value;
    q->size++;
    
    printf("Enqueued %d\n", value);
}

// Dequeue (remove element from front) - O(1)
int dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue Underflow! Queue is empty\n");
        return -1;
    }
    
    int dequeued = q->items[q->front];
    q->front = (q->front + 1) % MAX_SIZE;  // Circular increment
    q->size--;
    
    return dequeued;
}

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

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

// Display queue contents
void display(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return;
    }
    
    printf("Queue (front to rear): ");
    int i = q->front;
    for (int count = 0; count < q->size; count++) {
        printf("%d ", q->items[i]);
        i = (i + 1) % MAX_SIZE;
    }
    printf("\n");
}

int main() {
    printf("=== Circular Queue Implementation ===\n\n");
    
    Queue queue;
    initQueue(&queue);
    
    // Enqueue operations
    enqueue(&queue, 10);
    enqueue(&queue, 20);
    enqueue(&queue, 30);
    enqueue(&queue, 40);
    enqueue(&queue, 50);
    
    printf("\n");
    display(&queue);
    printf("Front: %d, Rear: %d\n", getFront(&queue), getRear(&queue));
    
    // Try to enqueue when full
    printf("\n");
    enqueue(&queue, 60);  // Should fail - queue full
    
    // Dequeue operations
    printf("\nDequeuing elements:\n");
    printf("Dequeued: %d\n", dequeue(&queue));
    printf("Dequeued: %d\n", dequeue(&queue));
    
    printf("\n");
    display(&queue);
    
    // Now we can enqueue again (circular behavior)
    printf("\nEnqueuing after dequeue (circular wrap):\n");
    enqueue(&queue, 60);
    enqueue(&queue, 70);
    
    printf("\n");
    display(&queue);
    printf("Size: %d\n", queue.size);
    
    return 0;
}

Circular Advantage: Circular queues maximize space utilization by wrapping around [web:301]. The modulo operation (front + 1) % MAX_SIZE ensures indices wrap from end to beginning.

Queue Implementation Using Linked List

Linked list-based queue implementation uses dynamic memory allocation with front and rear pointers [web:298]. Enqueue adds nodes at the rear while dequeue removes from the front, both O(1) operations. This eliminates fixed-size limitations and automatically handles the circular behavior through pointer manipulation.

clinkedlist_queue.c

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

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

// Queue structure with front and rear pointers
typedef struct {
    Node* front;
    Node* rear;
} Queue;

// Initialize queue
void initQueue(Queue* q) {
    q->front = NULL;
    q->rear = NULL;
}

// Check if queue is empty
bool isEmpty(Queue* q) {
    return q->front == NULL;
}

// Enqueue (add at rear) - O(1)
void enqueue(Queue* q, int value) {
    // Create new node
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return;
    }
    
    newNode->data = value;
    newNode->next = NULL;
    
    // If queue is empty, new node is both front and rear
    if (isEmpty(q)) {
        q->front = newNode;
        q->rear = newNode;
    } else {
        // Add to rear
        q->rear->next = newNode;
        q->rear = newNode;
    }
    
    printf("Enqueued %d\n", value);
}

// Dequeue (remove from front) - O(1)
int dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue Underflow! Queue is empty\n");
        return -1;
    }
    
    // Save front node and data
    Node* temp = q->front;
    int dequeued = temp->data;
    
    // Move front pointer
    q->front = q->front->next;
    
    // If queue becomes empty, update rear
    if (q->front == NULL) {
        q->rear = NULL;
    }
    
    free(temp);
    return dequeued;
}

// Get front element - O(1)
int getFront(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    
    return q->front->data;
}

// Get rear element - O(1)
int getRear(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    
    return q->rear->data;
}

// Display queue contents
void display(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return;
    }
    
    printf("Queue (front to rear): ");
    Node* current = q->front;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

// Free all nodes in queue
void freeQueue(Queue* q) {
    while (!isEmpty(q)) {
        dequeue(q);
    }
}

int main() {
    printf("=== Linked List-Based Queue Implementation ===\n\n");
    
    Queue queue;
    initQueue(&queue);
    
    // Enqueue operations
    enqueue(&queue, 100);
    enqueue(&queue, 200);
    enqueue(&queue, 300);
    enqueue(&queue, 400);
    enqueue(&queue, 500);
    
    printf("\n");
    display(&queue);
    printf("Front: %d, Rear: %d\n", getFront(&queue), getRear(&queue));
    
    // Dequeue operations
    printf("\nDequeuing elements:\n");
    printf("Dequeued: %d\n", dequeue(&queue));
    printf("Dequeued: %d\n", dequeue(&queue));
    
    printf("\n");
    display(&queue);
    
    // Enqueue more elements
    printf("\nEnqueuing more elements:\n");
    enqueue(&queue, 600);
    enqueue(&queue, 700);
    enqueue(&queue, 800);
    
    printf("\n");
    display(&queue);
    
    // Advantages
    printf("\nAdvantages:\n");
    printf("1. No fixed size limit\n");
    printf("2. No circular logic needed\n");
    printf("3. Memory allocated only when needed\n");
    
    // Clean up
    freeQueue(&queue);
    printf("\nQueue freed\n");
    
    return 0;
}

Real-World Applications

Stacks and queues solve practical problems across computing domains from operating systems to web browsers [web:302]. Understanding their applications helps choose the right data structure for specific problems and recognize patterns in existing systems.

capplications.c

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

#define MAX 100

// Application 1: Balanced Parentheses Checker using Stack
typedef struct {
    char items[MAX];
    int top;
} CharStack;

void initStack(CharStack* s) {
    s->top = -1;
}

bool isEmptyStack(CharStack* s) {
    return s->top == -1;
}

void pushChar(CharStack* s, char c) {
    if (s->top < MAX - 1) {
        s->items[++(s->top)] = c;
    }
}

char popChar(CharStack* s) {
    if (!isEmptyStack(s)) {
        return s->items[(s->top)--];
    }
    return '\0';
}

bool isMatchingPair(char open, char close) {
    return (open == '(' && close == ')') ||
           (open == '[' && close == ']') ||
           (open == '{' && close == '}');
}

bool checkBalancedParentheses(const char* expr) {
    CharStack stack;
    initStack(&stack);
    
    for (int i = 0; expr[i] != '\0'; i++) {
        char ch = expr[i];
        
        // Push opening brackets
        if (ch == '(' || ch == '[' || ch == '{') {
            pushChar(&stack, ch);
        }
        // Check closing brackets
        else if (ch == ')' || ch == ']' || ch == '}') {
            if (isEmptyStack(&stack)) {
                return false;  // No matching opening bracket
            }
            
            char top = popChar(&stack);
            if (!isMatchingPair(top, ch)) {
                return false;  // Mismatched pair
            }
        }
    }
    
    // All brackets should be matched
    return isEmptyStack(&stack);
}

// Application 2: Task Scheduler using Queue
typedef struct {
    int taskId;
    char taskName[50];
} Task;

typedef struct {
    Task items[MAX];
    int front, rear, size;
} TaskQueue;

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

bool isEmptyQueue(TaskQueue* q) {
    return q->size == 0;
}

void enqueueTask(TaskQueue* q, int id, const char* name) {
    if (q->size < MAX) {
        q->rear = (q->rear + 1) % MAX;
        q->items[q->rear].taskId = id;
        strcpy(q->items[q->rear].taskName, name);
        q->size++;
        printf("Task %d (%s) added to queue\n", id, name);
    }
}

Task dequeueTask(TaskQueue* q) {
    Task empty = {-1, ""};
    if (isEmptyQueue(q)) {
        return empty;
    }
    
    Task task = q->items[q->front];
    q->front = (q->front + 1) % MAX;
    q->size--;
    return task;
}

int main() {
    printf("=== Real-World Applications ===\n\n");
    
    // Application 1: Balanced Parentheses
    printf("1. Balanced Parentheses Checker (Stack):\n");
    
    const char* expressions[] = {
        "((a + b) * c)",
        "{[a + b] * (c - d)}",
        "((a + b)",
        "{[a + b)]"
    };
    
    for (int i = 0; i < 4; i++) {
        bool balanced = checkBalancedParentheses(expressions[i]);
        printf("  \"%s\" -> %s\n", expressions[i], 
               balanced ? "Balanced" : "Not Balanced");
    }
    
    // Application 2: Task Scheduling
    printf("\n2. Task Scheduler (Queue):\n");
    printf("  Simulating CPU task scheduling\n\n");
    
    TaskQueue scheduler;
    initQueue(&scheduler);
    
    // Add tasks
    enqueueTask(&scheduler, 1, "Process Email");
    enqueueTask(&scheduler, 2, "Compile Code");
    enqueueTask(&scheduler, 3, "Run Tests");
    enqueueTask(&scheduler, 4, "Deploy App");
    
    printf("\nProcessing tasks in FIFO order:\n");
    while (!isEmptyQueue(&scheduler)) {
        Task task = dequeueTask(&scheduler);
        printf("  Executing Task %d: %s\n", task.taskId, task.taskName);
    }
    
    // More applications
    printf("\n3. Other Stack Applications:\n");
    printf("   - Function call stack (recursion)\n");
    printf("   - Undo/Redo in text editors\n");
    printf("   - Browser back/forward navigation\n");
    printf("   - Expression evaluation (postfix)\n");
    
    printf("\n4. Other Queue Applications:\n");
    printf("   - Printer job management\n");
    printf("   - BFS graph traversal\n");
    printf("   - Keyboard buffer\n");
    printf("   - Request handling in web servers\n");
    
    return 0;
}

Application Pattern: Use stacks for nested/reversible operations and queues for sequential processing [web:302]. Stacks handle LIFO scenarios like function calls, while queues manage FIFO tasks like job scheduling.

Comparison: Array vs Linked List Implementation

Choosing between array-based and linked list-based implementations depends on your specific requirements regarding size predictability, memory usage, and performance characteristics. Each approach offers distinct trade-offs.

Aspect	Array Implementation	Linked List Implementation
Size	Fixed capacity	Dynamic, grows as needed
Memory	Contiguous allocation	Non-contiguous, extra pointer overhead
Operations	O(1) push/pop, enqueue/dequeue [web:296]	O(1) all operations [web:294]
Overflow	Possible, needs checking	Only when memory exhausted
Cache Performance	Better (locality)	Worse (scattered nodes)
Memory Waste	Unused array slots	Pointer overhead per node
Implementation	Simpler	More complex (pointers)
Best For	Known max size, speed critical	Unknown size, flexibility needed

Best Practices and Guidelines

Following established best practices ensures robust, efficient implementations of stacks and queues. These guidelines prevent common errors and improve code maintainability.

Always check overflow/underflow: Validate before push/pop or enqueue/dequeue to prevent errors [web:296]
Initialize properly: Set top = -1 for stacks, front = 0 and rear = -1 for queues
Use circular queue for arrays: Prevents wasted space and maximizes array utilization [web:301]
Free memory in linked implementations: Always free nodes when popping/dequeuing to avoid leaks
Encapsulate in structures: Use typedef struct for clean, maintainable code
Provide utility functions: Include isEmpty, isFull, size, peek for complete interface
Handle edge cases: Test with empty structures, single elements, and full capacity
Return meaningful values: Use return codes or special values to indicate errors
Document time complexity: Comment O(1) or O(n) for each operation
Choose appropriate implementation: Arrays for fixed size, linked lists for dynamic needs

Common Pitfalls to Avoid

Not checking empty before pop/dequeue: Causes underflow errors and undefined behavior
Forgetting circular logic in queues: Wastes array space after dequeuing elements
Memory leaks in linked implementations: Not freeing nodes leads to accumulating memory waste
Off-by-one errors: Incorrect top/front/rear pointer management
Not updating rear in queue: Forgetting to update rear when queue becomes empty after dequeue
Accessing freed memory: Using node pointers after calling free()
Incorrect size tracking: Not incrementing/decrementing size variable properly
Ignoring malloc failures: Not checking if malloc returns NULL before use

Critical Check: Always validate isEmpty before pop/dequeue operations [web:297]. Attempting to remove from empty structures causes underflow errors and can crash your program.

Conclusion

Stacks and queues are fundamental linear data structures with contrasting access patterns—stacks follow Last-In-First-Out (LIFO) where push adds elements to the top and pop removes from the top, while queues follow First-In-First-Out (FIFO) where enqueue adds at the rear and dequeue removes from the front. Array-based implementations offer fixed capacity with O(1) operations and excellent cache performance due to contiguous memory, requiring overflow checks before insertion but providing simple, fast access patterns ideal when maximum size is known. Linked list-based implementations eliminate fixed-size limitations through dynamic memory allocation, with stack operations at the head and queue operations using separate front and rear pointers, both achieving O(1) complexity while trading memory overhead for flexibility and avoiding overflow errors except when system memory is exhausted.

Circular queues optimize array-based implementations by treating the array as circular using modulo arithmetic—(rear + 1) % MAX_SIZE—to wrap indices from end to beginning, preventing wasted space from dequeued positions and maximizing array utilization without complex memory management. Real-world applications demonstrate their utility: stacks power function call management storing local variables and return addresses, undo/redo functionality in editors, balanced parentheses checking, and expression evaluation, while queues manage CPU task scheduling ensuring fair processing order, printer job management, breadth-first search graph traversal, and asynchronous request handling in servers. Implementation choice depends on specific requirements—use array-based for predictable maximum size and speed-critical applications, linked list-based when size varies significantly or flexibility is paramount. Best practices mandate overflow/underflow checking, proper initialization with top = -1 for stacks and appropriate front/rear values for queues, circular logic for array queues, memory freeing in linked implementations, and comprehensive testing of edge cases including empty structures and capacity limits. By mastering stack and queue implementations—from basic array and linked list approaches to optimized circular queues and practical applications—you build essential algorithmic foundations for advanced data structures, algorithm design, and systems programming where understanding LIFO and FIFO patterns enables solving diverse computational problems efficiently.