Your Progress

6/30 completed

20% complete. Continue learning to master DSA!

Queues in Data Structures

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. Think of it like a line of people waiting at a ticket counter: the first person to join the line is the first one to be served.

Key Takeaways

  • Queues follow the FIFO (First-In-First-Out) principle
  • Main operations: enqueue (add), dequeue (remove), peek (view front element)
  • Basic queue operations have O(1) time complexity
  • Queues can be implemented using arrays or linked lists
  • Common applications include CPU scheduling, disk scheduling, and handling requests in web servers

What is a Queue?

A queue is a linear data structure that follows a particular order for operations. The order is First In First Out (FIFO). In a queue, insertion happens at one end (rear) and deletion happens at the other end (front).

Key Characteristics of Queues

Queues are fundamental data structures used in many algorithms and system designs. They have a specific set of operations and can be efficiently implemented with arrays or linked lists. Queues ensure fair processing by handling elements in the exact order they were received.

Visual Representation of a Queue

Item 1
Item 2
Item 3
Item 4
Front
(Dequeue from here)
Rear
(Enqueue here)

A queue with 4 elements, with enqueue at the rear and dequeue from the front

Note: In a queue, elements are always added at the rear and removed from the front. This ensures that the first element added to the queue will be the first one to be removed, maintaining the FIFO property.

Basic Queue Operations

A queue supports the following basic operations:

OperationDescriptionTime Complexity
EnqueueAdds an element to the rear of the queueO(1)
DequeueRemoves the element from the front of the queueO(1)
Front (or Peek)Returns the front element without removing itO(1)
RearReturns the rear element without removing itO(1)
isEmptyChecks if the queue is emptyO(1)
isFullChecks if the queue is full (for array-based implementations)O(1)
SizeReturns the number of elements in the queueO(1)

Efficiency Insight

Standard queue operations (enqueue, dequeue, front, rear) all have O(1) time complexity, making queues highly efficient for their intended use cases. This constant-time performance is crucial for applications like job scheduling and request processing where speed is essential.

Types of Queues

There are several variations of queues, each designed for specific use cases:

Simple Queue

The basic queue structure where elements are inserted at the rear and removed from the front, following the FIFO principle. It can be implemented using arrays or linked lists.

Circular Queue

A queue that connects the front and rear ends, forming a circle. This design efficiently uses the array space by allowing elements to be added at positions that were previously dequeued, avoiding the "false full" condition in simple array queues.

Priority Queue

A special type of queue where elements are served based on their priority rather than the order of arrival. Higher priority elements are dequeued before lower priority ones, regardless of when they were added to the queue.

Double-ended Queue (Deque)

A queue that allows insertion and deletion at both ends. Deques are more flexible than standard queues and can be used to implement both stacks and queues, making them versatile data structures for various applications.

Circular Queue Visualization

Item 1
Item 2
Item 3
Item 4
Front
Rear

A circular queue with 4 elements, showing how the rear connects back to the front

Queue Implementation

Queues can be implemented in two main ways: using arrays or linked lists. Let's explore both approaches:

Array-based Queue

  • Uses a fixed-size array to store elements
  • Requires tracking front and rear indices
  • Simple implementation for basic queues
  • Can lead to false full condition (wasted space)
  • Circular implementation solves the space wastage issue

Linked List-based Queue

  • Dynamic size that grows and shrinks as needed
  • No wasted space or false full condition
  • Uses more memory for storing node pointers
  • Requires tracking both head and tail pointers
  • Better for queues with unpredictable sizes

Simple Array-based Queue Implementation

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

1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5#define MAX_SIZE 100
6
7// Array-based queue implementation
8typedef struct {
9 int items[MAX_SIZE];
10 int front;
11 int rear;
12} Queue;
13
14// Initialize queue
15void initialize(Queue *q) {
16 q->front = -1;
17 q->rear = -1;
18}
19
20// Check if queue is full
21bool isFull(Queue *q) {
22 return q->rear == MAX_SIZE - 1;
23}
24
25// Check if queue is empty
26bool isEmpty(Queue *q) {
27 return q->front == -1 || q->front > q->rear;
28}
29
30// Add an element to the queue (enqueue)
31bool enqueue(Queue *q, int value) {
32 if (isFull(q)) {
33 printf("Queue Overflow!\n");
34 return false;
35 }
36
37 if (q->front == -1) {
38 q->front = 0;
39 }
40
41 q->items[++(q->rear)] = value;
42 return true;
43}
44
45// Remove an element from the queue (dequeue)
46int dequeue(Queue *q) {
47 if (isEmpty(q)) {
48 printf("Queue Underflow!\n");
49 return -1; // Assuming -1 is not a valid queue element
50 }
51
52 int value = q->items[q->front];
53 q->front++;
54
55 // Reset the queue when it becomes empty
56 if (q->front > q->rear) {
57 q->front = q->rear = -1;
58 }
59
60 return value;
61}
62
63// Get the front element without removing it
64int front(Queue *q) {
65 if (isEmpty(q)) {
66 printf("Queue is empty!\n");
67 return -1;
68 }
69
70 return q->items[q->front];
71}
72
73// Get the size of the queue
74int size(Queue *q) {
75 if (isEmpty(q)) {
76 return 0;
77 }
78 return q->rear - q->front + 1;
79}
80
81int main() {
82 Queue queue;
83 initialize(&queue);
84
85 // Enqueue elements
86 enqueue(&queue, 10);
87 enqueue(&queue, 20);
88 enqueue(&queue, 30);
89 enqueue(&queue, 40);
90
91 printf("Front element: %d\n", front(&queue));
92 printf("Queue size: %d\n", size(&queue));
93
94 printf("Dequeued element: %d\n", dequeue(&queue));
95 printf("Dequeued element: %d\n", dequeue(&queue));
96
97 printf("Queue size after dequeuing: %d\n", size(&queue));
98 printf("Front element after dequeuing: %d\n", front(&queue));
99
100 return 0;
101}
102
103// Output:
104// Front element: 10
105// Queue size: 4
106// Dequeued element: 10
107// Dequeued element: 20
108// Queue size after dequeuing: 2
109// Front element after dequeuing: 30

Note: The simple array implementation above can be inefficient because it doesn't reuse the space at the beginning of the array after elements are dequeued. When the rear reaches the end of the array, no more elements can be added even if there's space at the beginning.

Circular Queue Implementation

A circular queue solves the space wastage problem by connecting the front and rear in a circular manner:

1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5#define MAX_SIZE 5 // Small size to demonstrate circular behavior
6
7// Circular queue implementation
8typedef struct {
9 int items[MAX_SIZE];
10 int front;
11 int rear;
12 int size; // Track number of elements
13} CircularQueue;
14
15// Initialize circular queue
16void initialize(CircularQueue *q) {
17 q->front = -1;
18 q->rear = -1;
19 q->size = 0;
20}
21
22// Check if circular queue is full
23bool isFull(CircularQueue *q) {
24 return q->size == MAX_SIZE;
25}
26
27// Check if circular queue is empty
28bool isEmpty(CircularQueue *q) {
29 return q->size == 0;
30}
31
32// Add an element to the circular queue (enqueue)
33bool enqueue(CircularQueue *q, int value) {
34 if (isFull(q)) {
35 printf("Queue Overflow!\n");
36 return false;
37 }
38
39 // If queue is empty, set front to 0
40 if (isEmpty(q)) {
41 q->front = 0;
42 }
43
44 // Move rear circularly and add element
45 q->rear = (q->rear + 1) % MAX_SIZE;
46 q->items[q->rear] = value;
47 q->size++;
48
49 return true;
50}
51
52// Remove an element from the circular queue (dequeue)
53int dequeue(CircularQueue *q) {
54 if (isEmpty(q)) {
55 printf("Queue Underflow!\n");
56 return -1;
57 }
58
59 int value = q->items[q->front];
60
61 // If the last element is being removed
62 if (q->front == q->rear) {
63 q->front = q->rear = -1;
64 } else {
65 // Move front circularly
66 q->front = (q->front + 1) % MAX_SIZE;
67 }
68
69 q->size--;
70 return value;
71}
72
73// Get the front element without removing it
74int front(CircularQueue *q) {
75 if (isEmpty(q)) {
76 printf("Queue is empty!\n");
77 return -1;
78 }
79
80 return q->items[q->front];
81}
82
83// Get the size of the circular queue
84int size(CircularQueue *q) {
85 return q->size;
86}
87
88// Display the circular queue
89void display(CircularQueue *q) {
90 if (isEmpty(q)) {
91 printf("Queue is empty\n");
92 return;
93 }
94
95 printf("Circular Queue: ");
96 int i = q->front;
97 int count = 0;
98
99 while (count < q->size) {
100 printf("%d ", q->items[i]);
101 i = (i + 1) % MAX_SIZE;
102 count++;
103 }
104 printf("\n");
105}
106
107int main() {
108 CircularQueue queue;
109 initialize(&queue);
110
111 printf("Enqueuing 10, 20, 30, 40, 50\n");
112 enqueue(&queue, 10);
113 enqueue(&queue, 20);
114 enqueue(&queue, 30);
115 enqueue(&queue, 40);
116 enqueue(&queue, 50);
117
118 display(&queue);
119
120 printf("Trying to enqueue 60: ");
121 if (!enqueue(&queue, 60)) {
122 printf("Failed, queue is full\n");
123 }
124
125 printf("Dequeuing two elements\n");
126 printf("Dequeued: %d\n", dequeue(&queue));
127 printf("Dequeued: %d\n", dequeue(&queue));
128
129 display(&queue);
130
131 printf("Enqueuing 60, 70 after dequeuing\n");
132 enqueue(&queue, 60);
133 enqueue(&queue, 70);
134
135 display(&queue);
136
137 return 0;
138}
139
140// Output:
141// Enqueuing 10, 20, 30, 40, 50
142// Circular Queue: 10 20 30 40 50
143// Trying to enqueue 60: Failed, queue is full
144// Dequeuing two elements
145// Dequeued: 10
146// Dequeued: 20
147// Circular Queue: 30 40 50
148// Enqueuing 60, 70 after dequeuing
149// Circular Queue: 30 40 50 60 70

Linked List-based Queue Implementation

A queue can also be implemented using a linked list, which doesn't have size limitations:

1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5// Node structure for linked list
6typedef struct Node {
7 int data;
8 struct Node *next;
9} Node;
10
11// Queue structure using linked list
12typedef struct {
13 Node *front;
14 Node *rear;
15 int size;
16} LinkedQueue;
17
18// Create a new node
19Node* createNode(int data) {
20 Node* newNode = (Node*)malloc(sizeof(Node));
21 if (newNode == NULL) {
22 printf("Memory allocation failed\n");
23 exit(1);
24 }
25 newNode->data = data;
26 newNode->next = NULL;
27 return newNode;
28}
29
30// Initialize queue
31void initialize(LinkedQueue *q) {
32 q->front = NULL;
33 q->rear = NULL;
34 q->size = 0;
35}
36
37// Check if queue is empty
38bool isEmpty(LinkedQueue *q) {
39 return q->front == NULL;
40}
41
42// Add an element to the queue (enqueue)
43void enqueue(LinkedQueue *q, int value) {
44 Node* newNode = createNode(value);
45
46 // If queue is empty, both front and rear point to the new node
47 if (isEmpty(q)) {
48 q->front = q->rear = newNode;
49 } else {
50 // Add the new node at the end and update rear
51 q->rear->next = newNode;
52 q->rear = newNode;
53 }
54
55 q->size++;
56}
57
58// Remove an element from the queue (dequeue)
59int dequeue(LinkedQueue *q) {
60 if (isEmpty(q)) {
61 printf("Queue Underflow!\n");
62 return -1;
63 }
64
65 // Store the front node and its data
66 Node* temp = q->front;
67 int value = temp->data;
68
69 // Move front to the next node
70 q->front = q->front->next;
71
72 // If front becomes NULL, set rear to NULL as well
73 if (q->front == NULL) {
74 q->rear = NULL;
75 }
76
77 // Free the memory of the dequeued node
78 free(temp);
79 q->size--;
80
81 return value;
82}
83
84// Get the front element without removing it
85int front(LinkedQueue *q) {
86 if (isEmpty(q)) {
87 printf("Queue is empty!\n");
88 return -1;
89 }
90
91 return q->front->data;
92}
93
94// Get the size of the queue
95int size(LinkedQueue *q) {
96 return q->size;
97}
98
99// Display the queue
100void display(LinkedQueue *q) {
101 if (isEmpty(q)) {
102 printf("Queue is empty\n");
103 return;
104 }
105
106 printf("Queue: ");
107 Node* current = q->front;
108 while (current != NULL) {
109 printf("%d ", current->data);
110 current = current->next;
111 }
112 printf("\n");
113}
114
115// Free the memory used by the queue
116void freeQueue(LinkedQueue *q) {
117 Node* current = q->front;
118 Node* next;
119
120 while (current != NULL) {
121 next = current->next;
122 free(current);
123 current = next;
124 }
125
126 q->front = q->rear = NULL;
127 q->size = 0;
128}
129
130int main() {
131 LinkedQueue queue;
132 initialize(&queue);
133
134 printf("Enqueuing 10, 20, 30, 40, 50\n");
135 enqueue(&queue, 10);
136 enqueue(&queue, 20);
137 enqueue(&queue, 30);
138 enqueue(&queue, 40);
139 enqueue(&queue, 50);
140
141 display(&queue);
142 printf("Queue size: %d\n", size(&queue));
143 printf("Front element: %d\n", front(&queue));
144
145 printf("Dequeuing two elements\n");
146 printf("Dequeued: %d\n", dequeue(&queue));
147 printf("Dequeued: %d\n", dequeue(&queue));
148
149 display(&queue);
150 printf("Queue size after dequeuing: %d\n", size(&queue));
151
152 // Free memory
153 freeQueue(&queue);
154
155 return 0;
156}
157
158// Output:
159// Enqueuing 10, 20, 30, 40, 50
160// Queue: 10 20 30 40 50
161// Queue size: 5
162// Front element: 10
163// Dequeuing two elements
164// Dequeued: 10
165// Dequeued: 20
166// Queue: 30 40 50
167// Queue size after dequeuing: 3

Common Queue Issues

Be aware of these common issues when working with queues:
- Queue Overflow: Occurs in array-based queues when trying to enqueue to a full queue
- Queue Underflow: Occurs when trying to dequeue from an empty queue
- False Full Condition: In simple array implementations, the queue may appear full even when there's space available
- Memory Leaks: In linked list implementations, failing to free nodes properly can cause memory leaks

Applications of Queues

Queues are used in a wide variety of applications due to their FIFO nature:

CPU Scheduling

Operating systems use queues for process scheduling. Ready processes are kept in a queue, waiting for their turn to use the CPU. This ensures each process gets fair CPU time based on its arrival time.

Disk Scheduling

I/O requests to a disk are managed through queues. The disk controller processes these requests in the order they were received, ensuring fair access to the disk resources.

Web Servers

Web servers use queues to handle incoming client requests. Requests are processed in the order they arrive, ensuring fair handling of client connections and preventing resource starvation.

Message Queues

In distributed systems, message queues enable asynchronous communication between components. They store messages until the receiving system is ready to process them, providing a buffer between sender and receiver.

Breadth-First Search

In graph algorithms, queues are used to implement breadth-first search (BFS). Nodes are visited level by level, starting from the source node, which ensures that the shortest path is found in unweighted graphs.

Print Spooling

Print jobs sent to a printer are added to a queue. The printer processes these jobs one by one in the order they were received, ensuring fair access to printing resources.

Real-world Example: Breadth-First Search using Queue

Here's an example of how queues are used in implementing the breadth-first search algorithm:

1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5#define MAX_VERTICES 100
6
7// Queue structure for BFS
8typedef struct {
9 int items[MAX_VERTICES];
10 int front;
11 int rear;
12} Queue;
13
14// Graph structure
15typedef struct {
16 int vertices;
17 int** adjacencyMatrix;
18 bool* visited;
19} Graph;
20
21// Queue operations
22void initializeQueue(Queue* q) {
23 q->front = -1;
24 q->rear = -1;
25}
26
27bool isQueueEmpty(Queue* q) {
28 return q->front == -1;
29}
30
31void enqueue(Queue* q, int value) {
32 if (q->front == -1) {
33 q->front = 0;
34 }
35 q->rear++;
36 q->items[q->rear] = value;
37}
38
39int dequeue(Queue* q) {
40 int item = q->items[q->front];
41
42 if (q->front == q->rear) {
43 q->front = q->rear = -1;
44 } else {
45 q->front++;
46 }
47
48 return item;
49}
50
51// Graph operations
52Graph* createGraph(int vertices) {
53 Graph* graph = (Graph*)malloc(sizeof(Graph));
54 graph->vertices = vertices;
55
56 // Create adjacency matrix
57 graph->adjacencyMatrix = (int**)malloc(vertices * sizeof(int*));
58 for (int i = 0; i < vertices; i++) {
59 graph->adjacencyMatrix[i] = (int*)malloc(vertices * sizeof(int));
60 for (int j = 0; j < vertices; j++) {
61 graph->adjacencyMatrix[i][j] = 0;
62 }
63 }
64
65 // Initialize visited array
66 graph->visited = (bool*)malloc(vertices * sizeof(bool));
67
68 return graph;
69}
70
71void addEdge(Graph* graph, int src, int dest) {
72 // Add edge (for undirected graph)
73 graph->adjacencyMatrix[src][dest] = 1;
74 graph->adjacencyMatrix[dest][src] = 1;
75}
76
77void resetVisited(Graph* graph) {
78 for (int i = 0; i < graph->vertices; i++) {
79 graph->visited[i] = false;
80 }
81}
82
83// Breadth-First Search algorithm using queue
84void BFS(Graph* graph, int startVertex) {
85 Queue queue;
86 initializeQueue(&queue);
87
88 // Reset all vertices as not visited
89 resetVisited(graph);
90
91 // Mark the start vertex as visited and enqueue it
92 graph->visited[startVertex] = true;
93 printf("BFS starting from vertex %d: ", startVertex);
94 printf("%d ", startVertex);
95 enqueue(&queue, startVertex);
96
97 // Process vertices in BFS order
98 while (!isQueueEmpty(&queue)) {
99 // Dequeue a vertex
100 int currentVertex = dequeue(&queue);
101
102 // Visit all adjacent vertices
103 for (int i = 0; i < graph->vertices; i++) {
104 if (graph->adjacencyMatrix[currentVertex][i] == 1 && !graph->visited[i]) {
105 graph->visited[i] = true;
106 printf("%d ", i);
107 enqueue(&queue, i);
108 }
109 }
110 }
111 printf("\n");
112}
113
114// Free the graph memory
115void freeGraph(Graph* graph) {
116 for (int i = 0; i < graph->vertices; i++) {
117 free(graph->adjacencyMatrix[i]);
118 }
119 free(graph->adjacencyMatrix);
120 free(graph->visited);
121 free(graph);
122}
123
124int main() {
125 // Create a graph with 7 vertices
126 Graph* graph = createGraph(7);
127
128 // Add edges to create a sample graph
129 addEdge(graph, 0, 1);
130 addEdge(graph, 0, 2);
131 addEdge(graph, 1, 3);
132 addEdge(graph, 1, 4);
133 addEdge(graph, 2, 5);
134 addEdge(graph, 2, 6);
135
136 // Perform BFS starting from vertex 0
137 BFS(graph, 0);
138
139 // Free the graph memory
140 freeGraph(graph);
141
142 return 0;
143}
144
145// Output:
146// BFS starting from vertex 0: 0 1 2 3 4 5 6

In this example, a queue is used to keep track of vertices to visit next in BFS. The algorithm visits vertices level by level, starting from the source vertex, which is exactly what we want in a breadth-first traversal.

Next Steps

Now that you understand queues, you're ready to explore more advanced queue variations and related data structures:

  • Priority Queues-Learn about queues where elements are served based on priority
  • Double-ended Queues (Deque)-Explore queues that allow insertion and deletion at both ends
  • Trees-Learn about hierarchical data structures and how queues are used in tree traversals

Related Tutorials

Stacks

Learn about stacks, the LIFO counterpart to queues.

Learn more

Linked Lists

Explore linked lists, which can be used to implement queues.

Learn more

Priority Queues

Learn about priority queues, a specialized queue where elements have priorities.

Learn more