Your Progress
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
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:
Operation | Description | Time Complexity |
---|---|---|
Enqueue | Adds an element to the rear of the queue | O(1) |
Dequeue | Removes the element from the front of the queue | O(1) |
Front (or Peek) | Returns the front element without removing it | O(1) |
Rear | Returns the rear element without removing it | O(1) |
isEmpty | Checks if the queue is empty | O(1) |
isFull | Checks if the queue is full (for array-based implementations) | O(1) |
Size | Returns the number of elements in the queue | O(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
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>45#define MAX_SIZE 10067// Array-based queue implementation8typedef struct {9 int items[MAX_SIZE];10 int front;11 int rear;12} Queue;1314// Initialize queue15void initialize(Queue *q) {16 q->front = -1;17 q->rear = -1;18}1920// Check if queue is full21bool isFull(Queue *q) {22 return q->rear == MAX_SIZE - 1;23}2425// Check if queue is empty26bool isEmpty(Queue *q) {27 return q->front == -1 || q->front > q->rear;28}2930// 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 }3637 if (q->front == -1) {38 q->front = 0;39 }4041 q->items[++(q->rear)] = value;42 return true;43}4445// 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 element50 }5152 int value = q->items[q->front];53 q->front++;5455 // Reset the queue when it becomes empty56 if (q->front > q->rear) {57 q->front = q->rear = -1;58 }5960 return value;61}6263// Get the front element without removing it64int front(Queue *q) {65 if (isEmpty(q)) {66 printf("Queue is empty!\n");67 return -1;68 }6970 return q->items[q->front];71}7273// Get the size of the queue74int size(Queue *q) {75 if (isEmpty(q)) {76 return 0;77 }78 return q->rear - q->front + 1;79}8081int main() {82 Queue queue;83 initialize(&queue);8485 // Enqueue elements86 enqueue(&queue, 10);87 enqueue(&queue, 20);88 enqueue(&queue, 30);89 enqueue(&queue, 40);9091 printf("Front element: %d\n", front(&queue));92 printf("Queue size: %d\n", size(&queue));9394 printf("Dequeued element: %d\n", dequeue(&queue));95 printf("Dequeued element: %d\n", dequeue(&queue));9697 printf("Queue size after dequeuing: %d\n", size(&queue));98 printf("Front element after dequeuing: %d\n", front(&queue));99100 return 0;101}102103// Output:104// Front element: 10105// Queue size: 4106// Dequeued element: 10107// Dequeued element: 20108// Queue size after dequeuing: 2109// 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>45#define MAX_SIZE 5 // Small size to demonstrate circular behavior67// Circular queue implementation8typedef struct {9 int items[MAX_SIZE];10 int front;11 int rear;12 int size; // Track number of elements13} CircularQueue;1415// Initialize circular queue16void initialize(CircularQueue *q) {17 q->front = -1;18 q->rear = -1;19 q->size = 0;20}2122// Check if circular queue is full23bool isFull(CircularQueue *q) {24 return q->size == MAX_SIZE;25}2627// Check if circular queue is empty28bool isEmpty(CircularQueue *q) {29 return q->size == 0;30}3132// 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 }3839 // If queue is empty, set front to 040 if (isEmpty(q)) {41 q->front = 0;42 }4344 // Move rear circularly and add element45 q->rear = (q->rear + 1) % MAX_SIZE;46 q->items[q->rear] = value;47 q->size++;4849 return true;50}5152// 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 }5859 int value = q->items[q->front];6061 // If the last element is being removed62 if (q->front == q->rear) {63 q->front = q->rear = -1;64 } else {65 // Move front circularly66 q->front = (q->front + 1) % MAX_SIZE;67 }6869 q->size--;70 return value;71}7273// Get the front element without removing it74int front(CircularQueue *q) {75 if (isEmpty(q)) {76 printf("Queue is empty!\n");77 return -1;78 }7980 return q->items[q->front];81}8283// Get the size of the circular queue84int size(CircularQueue *q) {85 return q->size;86}8788// Display the circular queue89void display(CircularQueue *q) {90 if (isEmpty(q)) {91 printf("Queue is empty\n");92 return;93 }9495 printf("Circular Queue: ");96 int i = q->front;97 int count = 0;9899 while (count < q->size) {100 printf("%d ", q->items[i]);101 i = (i + 1) % MAX_SIZE;102 count++;103 }104 printf("\n");105}106107int main() {108 CircularQueue queue;109 initialize(&queue);110111 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);117118 display(&queue);119120 printf("Trying to enqueue 60: ");121 if (!enqueue(&queue, 60)) {122 printf("Failed, queue is full\n");123 }124125 printf("Dequeuing two elements\n");126 printf("Dequeued: %d\n", dequeue(&queue));127 printf("Dequeued: %d\n", dequeue(&queue));128129 display(&queue);130131 printf("Enqueuing 60, 70 after dequeuing\n");132 enqueue(&queue, 60);133 enqueue(&queue, 70);134135 display(&queue);136137 return 0;138}139140// Output:141// Enqueuing 10, 20, 30, 40, 50142// Circular Queue: 10 20 30 40 50143// Trying to enqueue 60: Failed, queue is full144// Dequeuing two elements145// Dequeued: 10146// Dequeued: 20147// Circular Queue: 30 40 50148// Enqueuing 60, 70 after dequeuing149// 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>45// Node structure for linked list6typedef struct Node {7 int data;8 struct Node *next;9} Node;1011// Queue structure using linked list12typedef struct {13 Node *front;14 Node *rear;15 int size;16} LinkedQueue;1718// Create a new node19Node* 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}2930// Initialize queue31void initialize(LinkedQueue *q) {32 q->front = NULL;33 q->rear = NULL;34 q->size = 0;35}3637// Check if queue is empty38bool isEmpty(LinkedQueue *q) {39 return q->front == NULL;40}4142// Add an element to the queue (enqueue)43void enqueue(LinkedQueue *q, int value) {44 Node* newNode = createNode(value);4546 // If queue is empty, both front and rear point to the new node47 if (isEmpty(q)) {48 q->front = q->rear = newNode;49 } else {50 // Add the new node at the end and update rear51 q->rear->next = newNode;52 q->rear = newNode;53 }5455 q->size++;56}5758// Remove an element from the queue (dequeue)59int dequeue(LinkedQueue *q) {60 if (isEmpty(q)) {61 printf("Queue Underflow!\n");62 return -1;63 }6465 // Store the front node and its data66 Node* temp = q->front;67 int value = temp->data;6869 // Move front to the next node70 q->front = q->front->next;7172 // If front becomes NULL, set rear to NULL as well73 if (q->front == NULL) {74 q->rear = NULL;75 }7677 // Free the memory of the dequeued node78 free(temp);79 q->size--;8081 return value;82}8384// Get the front element without removing it85int front(LinkedQueue *q) {86 if (isEmpty(q)) {87 printf("Queue is empty!\n");88 return -1;89 }9091 return q->front->data;92}9394// Get the size of the queue95int size(LinkedQueue *q) {96 return q->size;97}9899// Display the queue100void display(LinkedQueue *q) {101 if (isEmpty(q)) {102 printf("Queue is empty\n");103 return;104 }105106 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}114115// Free the memory used by the queue116void freeQueue(LinkedQueue *q) {117 Node* current = q->front;118 Node* next;119120 while (current != NULL) {121 next = current->next;122 free(current);123 current = next;124 }125126 q->front = q->rear = NULL;127 q->size = 0;128}129130int main() {131 LinkedQueue queue;132 initialize(&queue);133134 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);140141 display(&queue);142 printf("Queue size: %d\n", size(&queue));143 printf("Front element: %d\n", front(&queue));144145 printf("Dequeuing two elements\n");146 printf("Dequeued: %d\n", dequeue(&queue));147 printf("Dequeued: %d\n", dequeue(&queue));148149 display(&queue);150 printf("Queue size after dequeuing: %d\n", size(&queue));151152 // Free memory153 freeQueue(&queue);154155 return 0;156}157158// Output:159// Enqueuing 10, 20, 30, 40, 50160// Queue: 10 20 30 40 50161// Queue size: 5162// Front element: 10163// Dequeuing two elements164// Dequeued: 10165// Dequeued: 20166// Queue: 30 40 50167// 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>45#define MAX_VERTICES 10067// Queue structure for BFS8typedef struct {9 int items[MAX_VERTICES];10 int front;11 int rear;12} Queue;1314// Graph structure15typedef struct {16 int vertices;17 int** adjacencyMatrix;18 bool* visited;19} Graph;2021// Queue operations22void initializeQueue(Queue* q) {23 q->front = -1;24 q->rear = -1;25}2627bool isQueueEmpty(Queue* q) {28 return q->front == -1;29}3031void 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}3839int dequeue(Queue* q) {40 int item = q->items[q->front];4142 if (q->front == q->rear) {43 q->front = q->rear = -1;44 } else {45 q->front++;46 }4748 return item;49}5051// Graph operations52Graph* createGraph(int vertices) {53 Graph* graph = (Graph*)malloc(sizeof(Graph));54 graph->vertices = vertices;5556 // Create adjacency matrix57 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 }6465 // Initialize visited array66 graph->visited = (bool*)malloc(vertices * sizeof(bool));6768 return graph;69}7071void 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}7677void resetVisited(Graph* graph) {78 for (int i = 0; i < graph->vertices; i++) {79 graph->visited[i] = false;80 }81}8283// Breadth-First Search algorithm using queue84void BFS(Graph* graph, int startVertex) {85 Queue queue;86 initializeQueue(&queue);8788 // Reset all vertices as not visited89 resetVisited(graph);9091 // Mark the start vertex as visited and enqueue it92 graph->visited[startVertex] = true;93 printf("BFS starting from vertex %d: ", startVertex);94 printf("%d ", startVertex);95 enqueue(&queue, startVertex);9697 // Process vertices in BFS order98 while (!isQueueEmpty(&queue)) {99 // Dequeue a vertex100 int currentVertex = dequeue(&queue);101102 // Visit all adjacent vertices103 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}113114// Free the graph memory115void 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}123124int main() {125 // Create a graph with 7 vertices126 Graph* graph = createGraph(7);127128 // Add edges to create a sample graph129 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);135136 // Perform BFS starting from vertex 0137 BFS(graph, 0);138139 // Free the graph memory140 freeGraph(graph);141142 return 0;143}144145// 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 moreLinked Lists
Explore linked lists, which can be used to implement queues.
Learn morePriority Queues
Learn about priority queues, a specialized queue where elements have priorities.
Learn more