Data Structure - 8 Circular & Double-Ended Queue

The Circular & Double-Ended Queue slide the Data Structures course include:
1. Definition of circular queue
2. Characteristics of circular queue
3. Basic operation of circular queue
4. Enqueue operation
5. Dequeue operation
6. Front operation
7. Rear operation
8. Definition of double-ended queue
9. Characteristics of double-ended queue
10. Double-ended queue operation
11. Enqueue front operation
12. Enqueue rear operation
13. Dequeue front operation
14. Dequeue rear operation

1. Department of Informatics
Faculty of Industrial Engineering
Universitas Pembangunan Nasional “Veteran” Yogyakarta
Data
Structure
Andi Nurkholis, S.Kom., M.Kom.
Circular &
Double-Ended Queue
October 27, 2025

2. Definition of Circular Queue
Circular Queue is a more efficient variation of the linear queue. The rear can
return to the beginning index of the array when it reaches the end, as long as
there is still available space. This prevents memory wastage caused by
dequeuing. A circular queue still follows the FIFO (First In, First Out) principle
but utilizes storage capacity more optimally. Analogy: a circular arrangement of
chairs that can be reused.
Basic structure of Circular Queue:
struct CircularQueue {
int front, rear; // front and rear indexes
int size, capacity; // number of elements and maximum capacity
int* array; // element storage
};

3. Characteristics ofCircular Queue
1.Circular Structure
2.FIFO (First In, First Out)
3.Memory Efficiency
4.Dynamic Front and Rear Indexes
5.Overflow and Underflow
Conditions

4. Characteristics of Circular Queue
1.Circular Structure: The rear (tail) returns to index 0 after reaching the last
index of the array, as long as that position is still unoccupied. This creates a
“circular” effect that allows optimal space utilization.
2.FIFO (First In, First Out): Just like a regular queue, a circular queue still
follows the FIFO principle, where the first element inserted is the first one to
be removed.
3.Memory Efficiency: No array space is wasted because the empty slots
created by dequeue operations can be reused. This differs from a linear
queue, where the empty slots at the front cannot be reused once the rear has
reached the end.

5. Characteristics of Circular Queue
4.Dynamic Front and Rear Indexes: The positions of the front and rear move
in a circular manner following enqueue (insertion) and dequeue (deletion)
operations. When the rear reaches the end of the array, it returns to the
starting index if there is still available space.
5.Overflow and Underflow Conditions: Overflow occurs when all slots are
filled, even though the rear index can still loop back to the beginning.
Underflow occurs when there are no elements in the circular queue (empty).

6. Basic Operation ofCircular Queue
1.Enqueue
2.Dequeue
3.Front
4.Rear

7. Enqueue Operation
1.Check for full condition: If (rear + 1) % size == front (in an array), the
queue is full, and the enqueue operation cannot be performed. In a linked
list, the full condition usually occurs only when memory is exhausted.
2.Handle empty condition: If front == -1 (array), set front = rear = 0. If front
== NULL (linked list), create a new node and set front = rear = node.
3.Move the rear pointer: If not empty, in an array update rear = (rear + 1) %
size. In a linked list, create a new node, link it with rear->next = node, then
set rear = node.
4.Store the new element: Insert the value into queue[rear] (in an array) or
store it in rear->data (in a linked list).

8. Dequeue Operation
1.Check empty condition: If front == -1 (array) or front == NULL (linked list),
the queue is empty, and the dequeue operation cannot be performed.
2.Retrieve the front element: Store the value from queue[front] (array) or
front->data (linked list) as the removed element.
3.Handle single-element condition: If front == rear (array or linked list), set
front = rear = -1 (array) or front = rear = NULL (linked list) to reset the
queue to empty.
4.Shift front position: If elements remain, update front = (front + 1) % size
(array) or front = front->next (linked list) to point to the next element.

9. Front Operation
1.Check empty condition: If front == -1 (array) or front == NULL (linked list),
the queue is empty, and no elements can be accessed.
2.Identify the front position: In an array, the front position is indicated by the
front index, while in a linked list it is directly pointed to by the front pointer.
3.Access the front element: Retrieve the value from queue[front] (array) or
front->data (linked list).
4.Return the value: The result of this operation is the data stored in the
frontmost element of the queue.

10. Rear Operation
1.Check empty condition: If rear == -1 (array) or front == NULL (linked list),
the queue is empty, and no elements can be accessed.
2.Identify the rear position: In an array, the last position is indicated by the
rear index, while in a linked list it is directly pointed to by the rear pointer.
3.Access the rear element: Retrieve the value from queue[rear] (array) or rear-
>data (linked list).
4.Return the value: The result of this operation is the data stored in the last
(rear) element of the queue.

11. Definition of Double-Ended Queue
Double-Ended Queue (Deque) is a variation of the queue data structure that
allows insertion (enqueue) and deletion (dequeue) operations from both ends
— front and rear. Unlike a regular queue, which is limited to one direction, a
deque is more flexible as it can function as both a stack and a queue. This
structure is useful in buffer management, process scheduling, and sliding window
algorithms.
Basic structure of Double-Ended Queue:
struct Deque {
int front, rear; // front and rear indexes
int size, capacity; // number of elements and maximum capacity
int* array; // element storage
};

12. Characteristics ofDouble-Ended Queue
1.Access from Both Ends
2.Two Main Variations of Deque
3.Dynamic Capacity and Size
4.Similarity to Stack and Queue
5.Operation Complexity

13. Characteristics of Dequeue
1.Access from Both Ends: Elements can be inserted or deleted from either the
front or the rear end. This makes a deque more flexible than a conventional
queue.
2.Two Main Variations of Deque: a) Input-Restricted Deque: Insertion is
allowed only at one end (e.g., rear), but deletion can be performed from both
ends (front and rear); b) Output-Restricted Deque: Deletion is allowed only
at one end (e.g., front), but insertion can be performed from both ends (front
and rear).

14. Characteristics of Dequeue
3.Dynamic Capacity and Size: A deque can be implemented using either an
array or a linked list. Arrays are limited and prone to overflow or underflow,
while linked lists are more flexible since their length can grow as needed.
4.Similarity to Stack and Queue: A deque can behave like a stack if
operations are restricted to one end (e.g., using the front for push and pop).
It can also behave like a queue if insertion is limited to the rear and deletion
to the front.
5.Operation Complexity: All deque operations — such as insertFront,
insertRear, deleteFront, and deleteRear — can generally be performed in
constant time O(1), whether implemented with an array or a linked list.

15. Basic Operation ofDouble-Ended Queue
1.Enqueue Front
2.Enqueue Rear
3.Dequeue Front
4.Dequeue Rear

16. Enqueue Front Operation
1.Check full condition: If (front == 0 && rear == size - 1) || (front == rear +
1) (array), the deque is full, and the enqueue front operation cannot be
performed. In a linked list, this occurs only when memory is full.
2.Handle empty condition: If empty, set front = rear = 0 (array) or create a
new node and set front = rear = node (linked list).
3.Shift front position: If not empty, in an array update front = (front - 1 +
size) % size to maintain circular movement. In a linked list, create a new
node, link it with node->next = front, then set front = node.
4.Store new element: Insert the value into queue[front] (array) or store it in
front->data (linked list).

17. Enqueue Rear Operation
1.Check full condition: If (front == 0 && rear == size - 1) || (front == rear +
1) (array), the deque is full, and the enqueue rear operation cannot be
performed. In a linked list, it is full only when memory is exhausted.
2.Handle empty condition: If empty, set front = rear = 0 (array) or create a
new node and set front = rear = node (linked list).
3.Shift rear position: If not empty, in an array update rear = (rear + 1) % size.
In a linked list, create a new node, link it with rear->next = node, then set
rear = node.
4.Store new element: Insert the value into queue[rear] (array) or store it in
rear->data (linked list).

18. Dequeue Front Operation
1.Check empty condition: If front == -1 (array) or front == NULL (linked list),
the deque is empty, and the dequeue front operation cannot be performed.
2.Retrieve the front element: Store the value from queue[front] (array) or
front->data (linked list) as the deleted element.
3.Handle single-element condition: If front == rear (array or linked list), set
front = rear = -1 (array) or front = rear = NULL (linked list) to reset the
deque to empty.
4.Shift front position: If elements remain, update front = (front + 1) % size
(array) or front = front->next (linked list) to point to the next element.

19. Dequeue Rear Operation
1.Check empty condition: If rear == -1 (array) or rear == NULL (linked list),
the deque is empty, and the dequeue rear operation cannot be performed.
2.Retrieve the rear element: Store the value from queue[rear] (array) or rear-
>data (linked list) as the deleted element.
3.Handle single-element condition: If front == rear (array or linked list), set
front = rear = -1 (array) or front = rear = NULL (linked list) to reset the
deque to empty.
4.Shift rear position: If elements remain, update rear = (rear - 1 + size) % size
(array). In a linked list, move the rear pointer to the previous node by
traversing from the front until the node before rear.

20. Department of Informatics
Faculty of Industrial Engineering
Universitas Pembangunan Nasional “Veteran” Yogyakarta
Andi Nurkholis, S.Kom., M.Kom.
October 27, 2025
Done
Thank
You