Stacks and Queues

Lesson 34

Stacks and Queues in C are fundamental linear data structures. A stack follows LIFO (Last In, First Out) using push and pop operations, while a queue follows FIFO (First In, First Out) using enqueue and dequeue operations. Both can be implemented using arrays or linked lists and are widely used in algorithms, operating systems, and networking.

C Track

Save progress as you learn.

44 lessons

Lesson content

Stacks and Queues in C Programming: A Complete Beginner to Advanced Guide

What are Stacks and Queues in C Programming?

Stacks and Queues in C programming are two fundamental linear data structures used to organize and manage data efficiently. Although both store collections of elements, they differ in the order in which elements are inserted and removed.

A stack follows the Last In, First Out (LIFO) principle. Imagine a stack of plates in a cafeteria — you place a new plate on top, and you also remove the top plate first.

A queue follows the First In, First Out (FIFO) principle. Think of people waiting in line at a ticket counter. The first person to join the line is the first person served.

Why Do Stacks and Queues Exist?

Many programming problems require processing data in a specific order. Stacks and queues provide efficient ways to organize and access data based on these ordering rules. They help solve problems involving function call management, task scheduling, expression evaluation, Breadth-First Search (BFS), Depth-First Search (DFS), undo and redo operations, printer job management, and CPU scheduling.

Real-World Use Cases

Stacks are used in:

Function call stack
Undo/Redo operations
Browser back navigation
Expression evaluation
Syntax parsing

Queues are used in:

Printer queues
Customer service systems
CPU scheduling
Breadth-First Search (BFS)
Network packet processing

Prerequisites

Before learning Stacks and Queues in C, you should understand:

Variables
Data types
Arrays
Functions
Loops
Structures
Pointers (recommended)
Linked Lists (helpful)

Core Concepts

What is a Stack?

A stack is a linear data structure that allows insertion and deletion from only one end, called the top.

Stack Operations

Operation	Description
Push	Add an element to the top
Pop	Remove the top element
Peek (Top)	View the top element without removing it
IsEmpty	Check whether the stack is empty
IsFull	Check whether the stack is full (array implementation)

What is a Queue?

A queue is a linear data structure where elements are inserted at the rear and removed from the front.

Queue Operations

Operation	Description
Enqueue	Insert an element at the rear
Dequeue	Remove an element from the front
Front	View the first element
Rear	View the last element
IsEmpty	Check whether the queue is empty
IsFull	Check whether the queue is full (array implementation)

Stack vs Queue

Feature	Stack	Queue
Principle	LIFO	FIFO
Insertion	Top	Rear
Deletion	Top	Front
Main Operations	Push, Pop	Enqueue, Dequeue
Common Applications	Function calls, Undo	Scheduling, BFS

Stack Implementation

Stacks can be implemented using arrays or linked lists. Array implementation is simple and suitable when the maximum size is known. Linked list implementation allows the stack to grow dynamically.

Queue Implementation

Queues can be implemented using arrays, circular arrays, or linked lists. Circular queues are more efficient than simple array-based queues because they reuse unused positions.

Code Examples

Example 1: Beginner – Stack Using an Array

#include <stdio.h>                     // Include standard input/output library

#define SIZE 5                         // Define stack size

int stack[SIZE];                       // Declare stack array

int top = -1;                          // Initialize top pointer

int main()
{
    stack[++top] = 10;                 // Push first element

    stack[++top] = 20;                 // Push second element

    printf("%d\n", stack[top]);        // Peek top element

    top--;                             // Pop top element

    printf("%d\n", stack[top]);        // Print new top

    return 0;                          // End program
}

Output: 20 / 10

Example 2: Beginner – Queue Using an Array

#include <stdio.h>                     // Include standard input/output library

#define SIZE 5                         // Queue size

int queue[SIZE];                       // Queue array

int front = 0;                         // Front index

int rear = -1;                         // Rear index

int main()
{
    queue[++rear] = 10;                // Enqueue first element

    queue[++rear] = 20;                // Enqueue second element

    printf("%d\n", queue[front]);      // Print front element

    front++;                           // Dequeue first element

    printf("%d\n", queue[front]);      // Print new front

    return 0;                          // End program
}

Output: 10 / 20

Example 3: Intermediate – Stack Push and Pop Functions

#include <stdio.h>                             // Include standard input/output library

#define SIZE 5                                 // Maximum stack size

int stack[SIZE];                               // Stack array

int top = -1;                                  // Top index

void push(int value)                           // Push function
{
    if(top == SIZE - 1)                        // Check for overflow
    {
        printf("Stack Overflow\n");            // Display error
        return;                                // Exit function
    }

    stack[++top] = value;                      // Insert value
}

int pop()                                      // Pop function
{
    if(top == -1)                              // Check for underflow
    {
        printf("Stack Underflow\n");           // Display error
        return -1;                             // Return error value
    }

    return stack[top--];                       // Remove and return top element
}

int main()
{
    push(100);                                 // Push value

    push(200);                                 // Push another value

    printf("%d\n", pop());                     // Pop and print

    printf("%d\n", pop());                     // Pop and print

    return 0;                                  // End program
}

Output: 200 / 100

Example 4: Intermediate – Queue Enqueue and Dequeue Functions

#include <stdio.h>                             // Include standard input/output library

#define SIZE 5                                 // Queue size

int queue[SIZE];                               // Queue array

int front = 0;                                 // Front index

int rear = -1;                                 // Rear index

void enqueue(int value)                        // Enqueue function
{
    if(rear == SIZE - 1)                       // Check overflow
    {
        printf("Queue Overflow\n");            // Display error
        return;                                // Exit function
    }

    queue[++rear] = value;                     // Insert value
}

int dequeue()                                  // Dequeue function
{
    if(front > rear)                           // Check underflow
    {
        printf("Queue Underflow\n");           // Display error
        return -1;                             // Return error value
    }

    return queue[front++];                     // Remove front element
}

int main()
{
    enqueue(15);                               // Insert value

    enqueue(25);                               // Insert value

    printf("%d\n", dequeue());                 // Remove first value

    printf("%d\n", dequeue());                 // Remove second value

    return 0;                                  // End program
}

Output: 15 / 25

Example 5: Advanced – Stack Using a Linked List

#include <stdio.h>                             // Include standard input/output library
#include <stdlib.h>                            // Include memory allocation functions

struct Node                                    // Define stack node
{
    int data;                                  // Store value
    struct Node *next;                         // Pointer to next node
};

struct Node *top = NULL;                       // Initialize stack top

void push(int value)                           // Push function
{
    struct Node *newNode = (struct Node *)malloc(sizeof(struct Node)); // Allocate memory

    if(newNode == NULL)                        // Check allocation success
    {
        printf("Memory allocation failed\n");  // Display error
        return;                                // Exit function
    }

    newNode->data = value;                     // Store value

    newNode->next = top;                       // Link to previous top

    top = newNode;                             // Update top pointer
}

void pop()                                     // Pop function
{
    if(top == NULL)                            // Check empty stack
    {
        printf("Stack Underflow\n");           // Display error
        return;                                // Exit function
    }

    struct Node *temp = top;                   // Store current top

    printf("%d\n", top->data);                 // Print removed value

    top = top->next;                           // Move top pointer

    free(temp);                                // Free removed node
}

int main()
{
    push(10);                                  // Push value

    push(20);                                  // Push value

    pop();                                     // Remove top

    pop();                                     // Remove top

    return 0;                                  // End program
}

Output: 20 / 10

Common Mistakes and Pitfalls

Wrong	Correct
Pushing onto a full stack	Check for stack overflow before pushing
Popping from an empty stack	Check for stack underflow before popping
Forgetting to free linked-list nodes	Call free() after removing a node
Accessing queue[front] when the queue is empty	Verify the queue is not empty first
Using a simple array queue for many operations	Consider a circular queue to reuse space efficiently

Wrong:

stack[++top] = value;

Correct:

if(top < SIZE - 1)
{
    stack[++top] = value;
}

Best Practices

Check for overflow and underflow before every operation.
Prefer linked-list implementations when the maximum size is unknown.
Use circular queues for array-based queue implementations.
Free dynamically allocated memory to avoid memory leaks.
Keep stack and queue operations in separate functions.
Use descriptive variable names such as top, front, and rear.
Handle error conditions gracefully instead of assuming valid input.

When NOT to Use This

Avoid stacks when:

You need random access to elements.
Data must be processed in FIFO order.

Avoid queues when:

The most recently inserted item should be processed first.
Frequent random access by index is required.

Summary / Key Takeaways

Stacks and Queues in C programming are essential linear data structures.
A stack follows the LIFO principle using push and pop operations.
A queue follows the FIFO principle using enqueue and dequeue operations.
Both can be implemented using arrays or linked lists.
Array implementations are simple but have fixed sizes.
Linked-list implementations grow dynamically.
Always check for overflow and underflow.
Stacks and queues are widely used in operating systems, compilers, networking, and algorithms.

FAQ About Stacks and Queues in C

1. What is the difference between a stack and a queue?

A stack follows the Last In, First Out (LIFO) principle, while a queue follows the First In, First Out (FIFO) principle.

2. Which implementation is better: array or linked list?

Use an array when the maximum size is known and fixed. Use a linked list when the number of elements changes dynamically.

3. What is stack overflow?

A stack overflow occurs when you try to push an element onto a full stack or when excessive recursive function calls exhaust the available stack memory.

4. Why are circular queues preferred over simple array queues?

Circular queues reuse freed positions at the beginning of the array, making memory usage more efficient and preventing wasted space after dequeue operations.

5. Where are stacks and queues used in real-world software?

Stacks are commonly used for function call management, undo/redo operations, expression evaluation, and browser history. Queues are commonly used for CPU scheduling, printer job management, Breadth-First Search (BFS), network packet buffering, and customer service systems.

Prev: Linked Lists Back to hub