DATA STRUCTURE AND ALGORITHMS

LECTURE 6
QUEUES ADT
By : Dhahaba Nasser Al-Shaiba
 What is a Queue?

• Queue is a linear data structure in which the insertion and deletion operations are performed
at two ends.
• In a Queue data structure, the insertion operation is performed at a position which is known
as 'rear' and the deletion operation is performed at a position which is known as 'front’.
• In a Queue data structure, the insertion and deletion operations are performed based on the
FIFO (First In First Out) principle.

2
 What is a Queue? (cont.)

• In a queue data structure, the insertion operation is performed using a function called
“EnQueue()" and the deletion operation is performed using a function called
“DeQueue()".

3
 Example

• Ex: Queue after inserting 25, 30, 51, 60 and 85.

• The number of elements in the queue at any time is equal to the value of Rear - Front +1

4
 Operations on a Queue
The fundamental operations that can be performed on the queue are listed as follows -
1. Enqueue: The Enqueue operation inserts the element at the rear end of the queue. It
returns void.
2. Dequeue: It performs the deletion from the front-end of the queue. It also returns
the element which has been removed from the front-end. It returns an integer value.
3. Peek: This is the third operation that returns the element, which is pointed by the
front pointer in the queue but does not delete it.
4. Queue overflow (isFull): It shows the overflow condition when the queue is full.
5. Queue underflow (isEmpty): It shows the underflow condition when the Queue is
empty, i.e., no elements are in the Queue.

5
 Implementing queues

Queue data structure can be implemented in two ways :

1. Using Array

2. Using Linked List

6
 Queue Operations using Array
Queue data structure using an array can be implemented as follows :
• Step 1 - Include all the header files used in the program and define a constant ’SIZE’ with a
specific value.
• Step 2 - Create a one-dimensional array with the above-defined SIZE (int queue[SIZE])
• Step 3 - Define two integer variables ’front’ and ‘rear’ and initialize both with ’-1’.
(int front = -1, rear = -1)
• Step 4 - Then implement the main method by displaying the menu of the operations list and
make suitable function calls to perform the operation selected by the user on the
queue.
#Define SIZE 50;
int Queue[SIZE];
int FRONT = -1;
int REAR = -1 ; 7
 Enqueue() / Insertion

The following steps should be taken to enqueue (insert) data into a queue:
• If the queue is full, return overflow error and exit.
• If the queue is empty, Set front and rear =0, if not increment the rear pointer to point to the
next empty space.
• Add the data element to the queue location, where the rear is pointing.
• The Return success.

8
 Algorithm of Enqueue()
INITIALLY
STEP-1 If REAR= MAX-1 REAR = -1
write OVERFLOW FRONT = -1
Exit
STEP-2 If REAR = -1
Set FRONT=REAR= 0
Else
Set REAR = REAR +1
STEP-3 Set QUEUE [ REAR ] = Data

STEP-4 Exit

9
 Dequeue() / Deletion
This operation removes and returns an element that is at the front end of the queue. The steps :
• Check if the queue is empty.
• If the queue is empty, return the underflow error and exit.
• If the queue is not empty, check if the rear and front are equal which means there is only one
element, then set the rear and front as -1.
• Increment the front pointer to point to the next available data element.
• The Return success.

10
 Algorithm of Dequeue()

STEP-1 If (FRONT == -1 and REAR == -1)

write “UNDERFLOW “
Else
Set VAL = QUEUE [ FRONT ]
If (FRONT == REAR )
Set FRONT = REAR = -1
Else
Set FRONT = FRONT + 1
STEP-2 EXIT

11
 Queue using array

➢ Reasons to implement queues using arrays:

• Memory Efficient: Array elements do not hold the address of the next element like linked
list nodes do.
• Easier to implement and understand: Using arrays to implement queues requires less
code than using linked lists, and for this reason, it is typically easier to understand as well.

➢ Reasons for not using arrays to implement queues:

• Fixed size: An array occupies a fixed part of the memory. This means that it could take up
more memory than needed, or if the array fills up, it cannot hold more elements. And
resizing an array can be costly.
• Shifting cost: Dequeue causes the first element in a queue to be removed, and the other
elements must be shifted to take the removed elements' place. This is inefficient and can
cause problems, especially if the queue is long.
12
 Queue using array

• In the following example There are 3 elements in the queue but there is room for 5. items|5]
must be set to the value F. but the queue is an array of only 5 elements so this insertion cannot
be made If to insert F in the queue the Rear must be increased by 1 to 5 and Queue[5] must be
set to the value F. but Queue is an array of only 5 elements so this insertion cannot be made.

Rear = 4
EX : Queue[5]

Front = 2

13
 Solution to Problem

1. Shifting the elements downward with each deletion

2. Viewing the array as a circular buffer, i.e. wrapping the end to front.

14
 Solution 1

• After dequeue, shift all the elements of the array from Queue[index] to Queue[index-l]

1. X = Queue[0];
2. i = 0;
3. While (i < REAR )
Queue[i] = Queue[i+l];
i = i+1;
4. REAR = REAR -1;

• Method is costly as we have to move all the elements of the array.

 Solution 2

• To avoid the costly operation of coping all the elements again we employ another method
called Circular Queue.
• Simply dequeue the element and move the front pointer to the next index.

• If REAR = FRONT, Queue is empty

 Circular Array
implementation for Queue
2 4 dequeue

enqueue(1)
1 3 2 4
1 2 4 dequeue

enqueue(3) 1 3 2 4
dequeue
1 3 2 4
1 3 2 4
dequeue
: Front of queue
1 3 2 4
: R ear of queue
 Queue Using Linked List

➢ Reasons for using linked lists to implement queues:

• Dynamic size: The queue can grow and shrink dynamically, unlike with arrays.
• No shifting: The front element of the queue can be removed (enqueue) without having
to shift other elements in the memory.

➢ Reasons for not using linked lists to implement queues:

• Extra memory: Each queue element must contain the address to the next element (the
next linked list node).
• Readability: The code might be harder to read and write for some because it is longer
and more complex.
18
 Queue Using Linked List(cont.)

• A queue data structure can be implemented using a linked list data structure. The queue
which is implemented using a linked list can work for an unlimited number of values
• In the linked list implementation of a queue, the last inserted node is always pointed by
'rear' and the first node is always pointed by 'front’.
• In the below example, the last inserted node is 50 and is pointed by 'rear' and the first
inserted node is 10 and is pointed by 'front'. The order of elements inserted is 10, 15, 22,
and 50.

19
 Queue Operations using Linked List

To implement a queue using a linked list, we need to set the following things before
implementing actual operations.

• Step 1 - Define a 'Node' structure with two members data and next.

• Step 2 - Define two Node pointers 'front' and 'rear' and set both to NULL.

20
 Insert operation – Using LL
• The insert operation appends the queue by adding an element to the end of the queue. The
new element will be the last element of the queue.
• Firstly, allocate the memory for the new node PTR by using the following statement.

Struct node
{ int data;
node *next;
} *PTR,*REAR,*FRONT;
PTR = new node ; (or PTR = (struct node *) malloc (sizeof(struct node));

21
 Algorithm of EnQueue(value) – Using LL

• Step 1: PTR = new Node INITIALLY

• Step 2: Set PTR -> DATA = value REAR = NULL
• Step 3: IF FRONT = NULL FRONT = NULL
Set FRONT = REAR = PTR
Set FRONT -> NEXT = NULL
Set REAR -> NEXT = NULL
ELSE
Set REAR -> NEXT = PTR
Set REAR = PTR
Set REAR -> NEXT = NULL
• Step 4: END

22
 Algorithm of DeQueue(value) – Using LL

• Step 1: If FRONT = NULL

Write " Underflow "
Exit;
Step 2: Set temp = FRONT
• Step 3: Set FRONT = FRONT -> NEXT
• Step 4: If FRONT = NULL
Set REAR = NULL
• Step 5: FREE temp
• Step 6: Exit

23
 Types of Queue

• Simple Queue or Linear Queue

• Circular Queue

• Priority Queue

• Double Ended Queue (or Deque)

24
 Simple Queue or Linear Queue

• In a Linear Queue, an insertion takes place from one end while the deletion occurs from
another end.
• The end at which the insertion takes place is known as the rear end, and the end at which the
deletion takes place is known as the front end. It strictly follows the FIFO rule.
• The major drawback of using a linear Queue is that insertion is done only from the rear end.
• If the first three elements are deleted from the Queue, we cannot insert more elements even
though the space is available in a Linear Queue.
• In this case, the linear Queue shows the overflow condition as the rear is pointing to the last
element of the Queue.

25
 Circular Queue

Why was the concept of the circular queue introduced?

There was one limitation in the array implementation of Queue.

If the rear reaches the end position of the Queue then there
might be a possibility that some vacant spaces are left in the
beginning that cannot be utilized. So, to overcome such
limitations, the concept of the circular queue was introduced.

26
 What is a Circular Queue?

• A Circular queue is similar to a linear queue as it is also based on the FIFO (First In First

Out) principle except that the last position is connected to the first position in a circular

queue that forms a circle. It is also known as a Ring Buffer.

27
Example of Circular Queue

28
 Implement Circular Queue using Array
• Initialize an array of size n, where n is the maximum number of elements that the queue can
hold.
• Initialize three variables (size=0, capacity(the capacity of array), and front.)
Algorithm to insert an element in a circular queue(Enqueue):
• if size == capacity
display “Queue is full”.
Else
rear = (front + size) % capacity (% is mode function)
Queue[rear] = value.
size = size + 1.
29
 Algorithm to delete an element in a circular
queue(Dequeue):

• If size == 0 (the queue is empty),

display “Queue is empty”.
Else
Set temp = Queue[front];
Set front = (front + 1) % capacity.
size = size – 1;
return temp.
30
31
 Priority Queue
• A Priority queue is a type of queue that arranges elements based on their priority values.
Elements with higher priority values are typically retrieved or removed before elements with
lower priority values. Each element has a priority value associated with it. When we add an
item, it is inserted in a position based on its priority value.
• Implement Priority Queue Using Array:
A simple implementation is to use an array of the following structure.
struct item
{int value;
int priority;}
• Implement Priority Queue Using Linked List:
typedef struct node
{ int data;
int priority;
struct node* next; } Node; 32
 Properties of Priority Queue

• Priority queue is an extension of the queue with the following properties.

• Every item has a priority associated with it.
• An element with high priority is dequeued before an element with low priority(The
elements with higher priority are served first).
• If two elements have the same priority, they are served according to their order in the
queue.

33
 How is Priority assigned to the elements in a
Priority Queue?

• In a priority queue, an element’s value is generally considered for assigning the priority.

• For example, the element with the highest value is assigned the highest priority, and the
element with the lowest value is assigned the lowest priority. The reverse case can also be
used i.e., the element with the lowest value can be assigned the highest priority. Also, the
priority can be assigned according to our needs.

34
Example of a Priority Queue

35
 Types of Priority Queue

1) Ascending Order Priority Queue (APQ)

• The element with the highest priority (largest value) is dequeued first.
• Commonly implemented using a max heap.

2) Descending order Priority Queue (DPQ)

• The element with the lowest priority (smallest value) is dequeued first.
• Commonly implemented using a min heap.

36
 Applications of Priority Queue

• CPU Scheduling (Process with higher priority executes first, Ex: Real-time operating
systems use priority queues to manage critical tasks.SJF)
• Dijkstra’s Algorithm (Shortest path in graphs, Ex: Google Maps uses Dijkstra’s
algorithm to find the fastest route.)
• Huffman Coding (Used in data compression, Ex: MP3, PNG, and GZIP compression
use Huffman coding.)
• Job Scheduling (Task execution based on priority, Ex: Print queue management, where
urgent print jobs are processed first.)
37
 Deque (or double-ended queue)
What is a Deque (or double-ended queue)?
• The deque stands for Double Ended Queue. Deque is a linear data structure where the
insertion and deletion operations are performed from both ends. We can say that deque is
a generalized version of the queue.
• Though the insertion and deletion in a deque can be performed on both ends, it does not
follow the FIFO rule.
• The representation of a deque is given as follows -

38
 Types of deque

There are two types of deque :

• Input restricted queue
• Output restricted queue

39
 Input restricted Queue

• In input restricted queue, insertion operation can be performed at only one end, while
deletion can be performed from both ends.

40
 Output restricted Queue

• In output restricted queue, deletion operation can be performed at only one end, while
insertion can be performed from both ends.

41
 Advantages of Queue

• Easy to understand and use.

• Efficient for storing and retrieving data in the same order as insertion.

42
 Disadvantages of Queue

• Memory issues can be experienced if implemented wrongly.

• Not suitable for applications with complex priority or insertion/ removal operations that

need flexibility across ends (front and rear).

43
 Applications of Queues

• Managing tasks in operating systems (e.g., print spooling, job scheduling)

• Handling requests in web servers.
• Breadth-first traversal in graph algorithms.
• Simulating queueing systems (e.g., call centers).
• Handling user input in applications.
• Implementing buffers for data transfer between different processes.
• Managing tasks in CPU scheduling.

44
 Assignment 3- Solutions

Write the solution steps in the following questions:

A. The postfix form of the expression: (A + B) * (C - D)
B. The prefix form of the expression: A – B / (C * D ^ E)
C. Convert the prefix expression to infix: - / A B + C D

45
46
47
48