Data Structures: Queues

A queue is a data structure that stores items in first-in, first-out (FIFO) order. Elements are added at the rear and removed from the front, like a real-world line of people. Queues are used in task scheduling, printing, and buffering in computer systems.

See more like this Stacks Trees Graphs Queues

Linear Queue

Skip to Algorithm

A linear queue is a data structure that stores elements in a sequential order. It follows the FIFO (First In, First Out) principle and consists of two pointers:

Front: The end from which elements are removed.
Rear: The end where elements are added.

Characteristics

Simple to implement.
Good for sequential task management (e.g., print jobs, queues).
Fixed size if implemented with an array.
Can waste memory after multiple dequeues.

Operations

Enqueue: Add an element to the rear.
Dequeue: Remove an element from the front.
Peek/Front: Check the element at the front.
IsEmpty: Check if the queue is empty.
IsFull: Check if the queue is full.

Example

Initial Queue (size 5):
Front = -1, Rear = -1

Enqueue 10:
Front = 0, Rear = 0, Queue = [10, _, _, _, _]

Enqueue 20:
Rear = 1, Queue = [10, 20, _, _, _]

Dequeue:
Front = 1, removed 10
Queue now = [_, 20, _, _, _]

Interactive Linear Queue

						procedure enqueue(item)
						if tail == 4 then
						print("Queue full")
						else
						tail = tail + 1
						questions[tail]=item
						endif
						endprocedure
					

						function dequeue()
						if head == tail + 1 then
						print("Queue empty")
						return -1
						else
						head = head + 1
						return question[head-1]
						endif
						end-function
					

Circular Queue

Skip to Algorithm

A circular queue is a linear data structure that solves the problem of wasted space in a linear queue by connecting the end of the queue back to the front. It also follows the FIFO (First In, First Out) principle.

Characteristics

Efficient memory usage compared to linear queues.

Implemented with arrays or linked lists.

Useful in buffer management (CPU scheduling, traffic management, etc.).

Slightly more complex to implement.

In a circular queue, the rear wraps around to the front when space is available:

[10] [20] [30] [40] [50]
Front = 0, Rear = 4

After some operations, rear can wrap back to the beginning:

[60] [70] [30] [40] [50]
Front = 2, Rear = 1

Operations

Enqueue (Insert): Add an element at the rear.
rear = (rear + 1) % size
queue[rear] = new_element
Dequeue (Remove): Remove an element from the front.
element = queue[front]
front = (front + 1) % size
Peek/Front: View the element at the front without removing it.
IsEmpty: True if front == -1.
IsFull: True if (rear + 1) % size == front.

Example

Initial Queue (size 5):
Front = -1, Rear = -1

Enqueue 10, 20, 30, 40, 50:
Front = 0, Rear = 4
[10] [20] [30] [40] [50]

Dequeue 10, 20:
Front = 2, Rear = 4
[10] [20] [30] [40] [50]

Enqueue 60, 70 (wrap around):
Front = 2, Rear = 1
[70] [60] [30] [40] [50]

Interactive Circular Queue

						procedure enqueue(item)
						if (tail+1) MOD size == head and tail>=0
						print("Queue is full")
						else
						tail=tail+1 MOD size
						queue[tail] = item
						endif
						end procedure
					

						function dequeue()
						if head== 0 and tail == -1
						print(“Queue is empty")
						else
						item=queue[head])
						if head==tail
						head = 0
						tail = -1
						else
						head = head + 1 MOD size
						endif
						return item
						endif
						end function
					

In this alternative solution an additional variable is ued to keep track of the number of items in the queue. This simplifies checking if the queue is full or empty as the variable can simply be checked to see if it is 0 (empty) or equal to max (full)

						procedure enqueue(item)
						if numitems==max
						print("Queue is full")
						else
						tail=tail+1 MOD size
						queue[tail] = item
						numitems=numitems+1
						endif
						end procedure
					

						function dequeue()
						if numitems==0
						print("Queue is empty")
						else
						temp = queue[head]
						head=head+1 MOD size
						numitems=numitems-1
						return temp
						ENDIF
						end function
					

Check your understanding

Download a worksheet to test your understanding and strengthen your skills!

Browse Worksheets