Algorithm and Data Structure - Queue

This material aims to enable students to:
1) Understanding queue concept
2) Understanding enqueue, dequeue, front, rear operation in a queue
3) Understanding working of queue
4) Knowing of queue application

1. Algorithm and
Data Structure
Andi Nurkholis, S.Kom, M.Kom
Study Program of Informatics
Faculty of Engineering and Computer Science
SY. 2020-2021
April 19, 2021

2. 2
5 Queue

3. 3
What is Queue?
Like Stack, Queue is a linear structure which follows a
particular order in which the operations are
performed. The order is First In First Out (FIFO). A
good example of queue is any queue of consumers
for a resource where the consumer that came first is
served first.

4. 4
Illustration

5. 5
Queue VS Stack
The difference between stacks and queues is in removing. In a
stack we remove the item the most recently added; in a queue,
we remove the item the least recently added

6. 6
Queue
Operations
1)Enqueue
2)Dequeue
3)Front
4)Rear

7. 7
Enqueue
Enqueue: Adds an item in the stack. If the stack is full, then it is
said to be an Overflow condition.

8. Steps of Enqueue
Step 1− Check if the queue is full.
Step 2 − If the queue is full, produce overflow error
and exit.
Step 3 − If the queue is not full, increment rear
pointer to point the next empty space.
Step 4 − Add data element to the queue location,
where the rear is pointing.
Step 5 − return success.
8

9. 9
Enqueue Algorithm
begin procedure enqueue(data)
if queue is full
return overflow
endif
rear ← rear + 1
queue[rear] ← data
return true
endprocedure

10. Dequeue
Dequeue: Removes an item from the queue. The items are
popped in the same order in which they are pushed. If the
queue is empty, then it is said to be an Underflow condition.
10

11. Steps of Dequeue
Step 1 − Check if the queue is empty.
Step 2 − If the queue is empty, produce underflow
error and exit.
Step 3 − If the queue is not empty, access the data
where front is pointing.
Step 4 − Increment front pointer to point to the next
available data element.
Step 5 − Return success.
11

12. Dequeue Algorithm
beginprocedure dequeue
ifqueue is empty
return underflow
end if
data = queue[front]
front ← front + 1
return true
end procedure
12

13. Front
Front: Get the front item from queue.
13
Front Algorithm:
begin procedure front
return queue[top]
endprocedure

14. Rear
Rear: Get the last item from
queue.
Rear Algorithm:
begin procedure rear
return queue[last]
endprocedure
14

15. Working of Queue
This abstract data type​ can be implemented in C in
multiple ways. One such way is by using an array.
Pro of using an array:
Easyto implement.
Conof using an array:
Static Data Structure, fixed size.
15

16. Queue Application
1.CPU scheduling, Disk Scheduling
2.When data is transferred asynchronously between two
processes.Thequeue is used for synchronization. For example:
IO Buffers, pipes, file IO, etc
3.Handling of interrupts in real-time systems.
4.Call Center phone systems use Queues to hold people calling
them in order.
16

17. Thank You, Next …
Searching
April 19, 2021
Andi Nurkholis, S.Kom, M.Kom
Study Program of Informatics
Faculty of Engineering and Computer Science
SY. 2020-2021