TutorialKart.comA queue is a linear data structure that processes elements in first-in, first-out order, commonly written as FIFO. The element inserted first is the first element removed. New elements enter through the rear, while existing elements leave through the front.
A queue can be compared with a line of people waiting at a ticket counter. The person who joins first is normally served first, while each new person joins at the end of the line.
How a Queue Data Structure Works
Consider a queue that receives the values 10, 20, and 30 in that order:
Front -> 10 20 30 <- RearIf one element is removed, 10 leaves the queue because it was inserted first. The queue then becomes:
Front -> 20 30 <- RearThis restricted access distinguishes a queue from a stack. A stack inserts and removes elements from the same end, whereas a queue inserts at the rear and removes from the front.
Basic Queue Operations
The principal operations performed on a queue are:
- Enqueue: Inserts an element at the rear.
- Dequeue: Removes and returns the element at the front.
- Front or peek: Reads the front element without removing it.
- Rear: Reads the last element without removing it.
- isEmpty: Checks whether the queue contains no elements.
- Size: Returns the number of elements currently stored.
Enqueue an Element at the Rear
The enqueue operation inserts an element into the queue. In a standard queue, insertion is permitted only at the rear. When the first element is inserted into an empty queue, both the front and rear refer to that element.
Dequeue an Element from the Front
The dequeue operation removes the element at the front of the queue. Attempting to dequeue from an empty queue causes an underflow condition and should be handled by returning an error, a status value, or an empty result.
Read the Queue Front
The front operation, also called peek, retrieves the element at the front without changing the queue. It is useful when a program needs to inspect the next item scheduled for processing.
Read the Queue Rear
The rear operation retrieves the most recently inserted element without changing the queue. In a linked-list implementation, a rear pointer allows this operation to run without traversing the entire list.
Types of Queues in Data Structures
Queue implementations are commonly grouped into the following types:
- Simple queue: Inserts at the rear and removes from the front in FIFO order.
- Circular queue: Treats the last array position as connected to the first, allowing released positions to be reused.
- Priority queue: Removes elements according to priority rather than insertion order. Elements with equal priority may still be processed in FIFO order.
- Deque: A double-ended queue that permits insertion and deletion at both the front and rear.
Why a Circular Queue Is Used with Arrays
In a basic linear array queue, dequeued positions at the beginning of the array may remain unused even when free space exists. A circular queue solves this problem by wrapping the rear index back to the beginning when it reaches the end of the array.
For an array of capacity n, the next position can be calculated as follows:
next_index = (current_index + 1) % capacity;Queue Implementation Using a Linked List
A linked-list queue stores each element in a node. The queue maintains a front pointer for deletion and a rear pointer for insertion. This design allows both enqueue and dequeue to run in constant time when the pointers are updated correctly.
Linked-List Queue Data Structures
Two structures are used in this implementation: a data node and a queue header.
The queue header contains pointers named front and rear, together with a count that records the number of nodes.
Each data node contains a pointer to the user data and a link to the next node.
typedef struct node {
void* dataptr;
struct node* next;
}NODE;
typedef struct {
NODE* front;
NODE* rear;
int count;
}QUEUE;Without creating two structures, we can use double pointer in one structure.
Algorithms for a Linked-List Queue
Create and Initialize the Queue
The queue creation algorithm allocates the queue header and initializes it as empty:
- Allocate queue head
- Set queue front to null
- Set queue rear to null
- Set queue count to 0
- Return queue head
Original C Implementation for Creating a Queue
QUEUE* createqueue(void)
{
QUEUE* queue;
queue=(QUEUE*)malloc(sizeof(QUEUE));
if(queue)
{
queue->front=NULL;
queue->rear=NULL;
queue->count=o;
}
return queue;
}In the original snippet above, the count assignment contains the letter o. In compilable C code, it should be the numeric value 0. A corrected version is shown below while preserving the original example.
QUEUE* createqueue(void)
{
QUEUE* queue = malloc(sizeof(QUEUE));
if (queue != NULL)
{
queue->front = NULL;
queue->rear = NULL;
queue->count = 0;
}
return queue;
}Enqueue Algorithm for a Linked-List Queue
The enqueue(queue, data_in) algorithm inserts a new node at the rear:
- if(queue full)
- return false
- end if
- allocate (new node)
- move datain to new node data
- set new node next to null pointer
- if(empty queue)
- set queue front to address of new node
- else
- set next pointer of rear node to address of new node
- end if
- set queue rear to address of new node
- increment queue count
- return true
C Implementation of Enqueue
bool enqueue(QUEUE* queue,void* item)
{
NODE* newptr;
if(!(newptr=(NODE*)malloc(sizeof(NODE))))
return false;
newptr->dataptr=item;
newptr->next=NULL;
if(queue->count==0)
queue->front=newptr;
else
queue->rear->next=newptr;
(queue->count)++;
queue->rear=newptr;
return true;
}When the queue is empty, the new node becomes both the front and rear. Otherwise, the existing rear node links to the new node before the rear pointer is advanced.
Dequeue Algorithm for a Linked-List Queue
The dequeue(queue, item) algorithm removes the front node and returns its data:
- if (queue empty)
- return false
- end if
- move front data to item
- if(only one node in queue)
- set queue rear to null
- end if
- set queue front to queue front next
- decrement queue count
- return true
C Implementation of Dequeue
bool dequeue(QUEUE* queue,void** item)
{
NODE* deleteloc;
if(!queue->count)
return false;
*item=queue->front->dataptr;
deleteloc=queue->front;
if(queue->count==1)
{
queue->rear=NULL;
queue->front=NULL;
}
else
queue->front=queue->front->next;
(queue->count)--;
free(deleteloc);
return true;
}The function returns false when the queue is empty. When the final node is removed, both the front and rear pointers must be set to NULL.
Queue Front Algorithm
The queuefront(queue, dataout) operation reads the first element without removing its node:
- if(queue empty)
- return false
- end if
- move data at front of queue to dataout
- return true
Original C Implementation of Queue Front
bool queuefront(QUEUE* queue,void** item)
{
if(!queue->count)
return false;
else
{
*item=queue>front>dataptr;
return true;
}
}The member-access expressions in the original snippet use > instead of the C pointer-member operator ->. The corrected operation is:
bool queuefront(QUEUE* queue, void** item)
{
if (queue == NULL || queue->count == 0)
return false;
*item = queue->front->dataptr;
return true;
}Destroy the Queue and Release Memory
The destroyqueue(queue) algorithm visits every node, releases the allocated memory, and then releases the queue header:
- if(queue not empty)
- loop(queue not empty)
- delete front node
- end loop
- loop(queue not empty)
- end if
- delete head structure
Original C Implementation for Destroying a Queue
QUEUE* destroyqueue(QUEUE* queue)
{
NODE* deleteptr;
if(queue)
{
while(queue->front!=NULL)
{
free(queue->front->dataptr);
deleteptr=queue->front;
queue->front=queue->front->next;
free(deQQleteptr);
}
free(queue);
}
return NULL;
}The original snippet contains the misspelled variable deQQleteptr. It also assumes that the queue owns every object referenced by dataptr. Whether those objects should be freed depends on how the caller allocated and shares them.
QUEUE* destroyqueue(QUEUE* queue)
{
NODE* deleteptr;
if (queue != NULL)
{
while (queue->front != NULL)
{
deleteptr = queue->front;
queue->front = queue->front->next;
free(deleteptr);
}
free(queue);
}
return NULL;
}This corrected version releases the queue nodes but does not free dataptr. A production implementation can accept a callback function when the queue is responsible for destroying the stored data.
Complete Queue Example in C
The following example demonstrates a compact integer queue using linked nodes. It includes enqueue, dequeue, front, and cleanup operations.
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
typedef struct {
Node* front;
Node* rear;
size_t size;
} Queue;
void initializeQueue(Queue* queue)
{
queue->front = NULL;
queue->rear = NULL;
queue->size = 0;
}
bool enqueueValue(Queue* queue, int value)
{
Node* node = malloc(sizeof(Node));
if (node == NULL)
return false;
node->data = value;
node->next = NULL;
if (queue->rear == NULL)
{
queue->front = node;
queue->rear = node;
}
else
{
queue->rear->next = node;
queue->rear = node;
}
queue->size++;
return true;
}
bool dequeueValue(Queue* queue, int* value)
{
if (queue->front == NULL)
return false;
Node* oldFront = queue->front;
*value = oldFront->data;
queue->front = oldFront->next;
if (queue->front == NULL)
queue->rear = NULL;
free(oldFront);
queue->size--;
return true;
}
bool frontValue(const Queue* queue, int* value)
{
if (queue->front == NULL)
return false;
*value = queue->front->data;
return true;
}
void clearQueue(Queue* queue)
{
int discarded;
while (dequeueValue(queue, &discarded))
{
}
}
int main(void)
{
Queue queue;
int value;
initializeQueue(&queue);
enqueueValue(&queue, 10);
enqueueValue(&queue, 20);
enqueueValue(&queue, 30);
if (frontValue(&queue, &value))
printf("Front: %d\n", value);
while (dequeueValue(&queue, &value))
printf("Removed: %d\n", value);
clearQueue(&queue);
return 0;
}The program produces the following result:
Front: 10
Removed: 10
Removed: 20
Removed: 30Queue Operation Time Complexity
| Queue operation | Linked-list queue | Circular array queue |
|---|---|---|
| Enqueue | O(1) with a rear pointer | O(1) |
| Dequeue | O(1) | O(1) |
| Read front | O(1) | O(1) |
| Read rear | O(1) with a rear pointer | O(1) |
| Search for a value | O(n) | O(n) |
A linked-list queue requires additional memory for node pointers and dynamic allocation. An array queue stores elements contiguously but usually has a fixed capacity unless the array is resized.
Queue Overflow and Underflow Conditions
- Queue underflow: Occurs when a program attempts to remove or inspect an element from an empty queue.
- Queue overflow: Occurs when a program attempts to insert into a fixed-capacity queue that is already full.
- Allocation failure: In a linked-list queue, insertion can fail when memory for a new node cannot be allocated.
Linked queues do not have a predetermined maximum number of elements, but they remain limited by available memory. Each queue function should therefore return a status that allows the caller to handle failure safely.
Applications of Queue Data Structures
Queues are used whenever tasks or data must be processed in arrival order or held until a resource becomes available.
- CPU scheduling: Ready processes can wait in scheduling queues before receiving processor time.
- Printer spooling: Print jobs wait until the printer is available.
- Web and application servers: Incoming requests or background jobs can be placed in a queue for controlled processing.
- Breadth-first search: Graph and tree algorithms use a queue to visit nodes one level at a time.
- Message processing: Producers place messages in a queue, and consumers process them independently.
- Network buffering: Packets may wait in queues before transmission or processing.
- Customer-service systems: Requests, tickets, and orders can be handled according to arrival time.
- Data categorization: Multiple queues can group items while preserving the relative order within each group.
Queue Compared with Stack
| Feature | Queue | Stack |
|---|---|---|
| Processing order | First in, first out | Last in, first out |
| Insertion point | Rear | Top |
| Removal point | Front | Top |
| Typical operation names | Enqueue and dequeue | Push and pop |
| Common use | Scheduling and breadth-first traversal | Function calls, undo operations, and depth-first traversal |
Queue Data Structure FAQs
What is a queue in data structures?
A queue is a linear data structure in which elements are normally inserted at the rear and removed from the front. It follows the first-in, first-out rule.
What are the four main types of queues?
The commonly discussed types are the simple queue, circular queue, priority queue, and double-ended queue or deque.
What is the difference between enqueue and dequeue?
Enqueue inserts a new element at the rear of a queue. Dequeue removes the element currently stored at the front.
Which data structure is suitable for implementing a queue?
A queue can be implemented with either an array or a linked list. A circular array is suitable for bounded queues, while a linked list supports dynamic growth and constant-time insertion when a rear pointer is maintained.
Why are queues used in breadth-first search?
Breadth-first search must process vertices in the order they are discovered. A queue preserves that order, allowing all vertices at one level to be processed before vertices at the next level.
Queue Tutorial Editorial QA Checklist
- Confirm that FIFO order is explained using insertion at the rear and deletion from the front.
- Verify that empty-queue checks are included before dequeue and front operations.
- Confirm that removing the final linked-list node sets both front and rear to
NULL. - Check that enqueue, dequeue, front, and rear complexities are stated for the implementation being discussed.
- Verify that circular queues, priority queues, deques, overflow, and underflow are distinguished accurately.
- Compile newly added C examples with warnings enabled and check all allocated nodes are released.