Queues in C Programming

By: Chaitra

Created: 11/28/2022 11:44

Last modified: 11/28/2022 11:44

1. What is a Queue?

A queue is a linear data structure that follows the First In, First Out (FIFO) principle. This means that the element inserted first is the one that is removed first—similar to people standing in a line: the first person in line gets served first.

2. Basic Queue Operations

A typical queue supports the following operations:

Operation	Description
Enqueue	Add an element at the rear (end) of the queue
Dequeue	Remove an element from the front of the queue
Front	Retrieve the first element without removing it
isEmpty	Check whether the queue is empty
isFull	Check whether the queue is full (for arrays)

3. Queue Implementation in C

Queues can be implemented in C in the following two common ways:

A. Using Arrays

Uses a fixed-size array.
Requires two variables: front and rear to track the first and last positions.
Efficient for simple use cases.

B. Using Linked Lists

Each element (node) points to the next.
No size limitation—uses dynamic memory.
front and rear are pointers to the first and last nodes.

4. Conceptual Syntax Overview (Array-Based Queue)

Initialization: Set front = -1, rear = -1.
Enqueue Operation:
- If rear == MAX - 1, queue is full (overflow).
- Otherwise, increment rear and insert value.
Dequeue Operation:
- If front > rear, queue is empty (underflow).
- Otherwise, increment front and return value.

Example Pseudocode:

Initialize queue[MAX], front = 0, rear = -1

Enqueue(x):
    if rear == MAX - 1
        overflow error
    else
        rear++
        queue[rear] = x

Dequeue():
    if front > rear
        underflow error
    else
        x = queue[front]
        front++

5. Types of Queues

1. Simple Queue

Standard FIFO queue.
Elements are inserted at the rear and removed from the front.

2. Circular Queue

Overcomes the limitation of array-based queues.
After reaching the end of the array, it wraps around to the beginning.

3. Priority Queue

Elements are ordered based on priority.
The highest priority element is dequeued first.

4. Double-Ended Queue (Deque)

Elements can be added or removed from both the front and rear.

6. Applications of Queues

Queues are commonly used in:

CPU scheduling and job scheduling
Breadth-first search (BFS) in graphs
Handling requests in web servers
Message queues in operating systems
Print spoolers

7. Array vs Linked List Queue Comparison

Feature	Array-Based Queue	Linked List-Based Queue
Memory Usage	Fixed memory allocation	Dynamic memory allocation
Size Limitation	Limited by array size	Grows as needed
Ease of Implementation	Simple	Slightly complex (pointers)
Time Complexity	O(1) for enqueue/dequeue	O(1) for enqueue/dequeue

8. Advantages of Queues

Useful in handling real-world data processing scenarios.
Efficient data structure for managing ordered data.
Easy to implement and use for scheduling and buffer tasks.

9. Limitations of Simple Queues (Array-Based)

Waste of space after multiple dequeue operations.
Requires shift operations or circular handling for reuse of space.
Dynamic memory cannot be used without a linked list.

A queue is a fundamental data structure used for orderly data handling where the first element to arrive should be the first to be served. In C programming, queues can be implemented using arrays or linked lists, depending on the use case. Understanding queues is crucial for solving problems related to resource scheduling, inter-process communication, and data streaming.