Ø Queue –
·
Queue is an abstract data structure, it
is similar to Stacks.
·
Unlike stacks, a queue is open at both
its ends.
·
One end is always used to insert data
(enqueue) and the other is used to remove data (dequeue).
·
Queue follows First-In-First-Out
methodology, i.e., the data item stored first will be accessed first.
·
In queue, we always dequeue (or access)
data, pointed by front pointer and while enqueing (or storing)
data in the queue we take help of rear pointer.
· A real-world example of queue can be a single-lane one-way road, where the vehicle enters first, exits first.
· More real-world examples can be seen as queues at the ticket windows and bus-stops
Applications of Queue Data Structure –
·
When a resource is shared among
multiple consumers. Examples include CPU scheduling, Disk Scheduling.
·
When data is transferred
asynchronously (data not necessarily received at same rate as sent) between two
processes. Examples include IO Buffers, pipes, file IO, etc.
Queue Representation
As we now understand that in
queue, we access both ends for different reasons. As in stacks, a queue can
also be implemented using Arrays, Linked-lists, Pointers and Structures. The following diagram given below tries to
explain queue representation as data structure −
Basic Operations –
1)
Enqueue()
2)
Dequeue()
3)
Peek()
4)
Isfull()
5)
Isempty()
·
enqueue() − add
(store) an item to the queue.
·
dequeue() − remove
(access) an item from the queue.
·
peek() − Gets the
element at the front of the queue without removing it.
·
isfull() − Checks
if the queue is full.
·
isempty() − Checks
if the queue is empty.
1)
Enqueue () – enqueue
means insert an element in a queue.
The following steps should be
taken to enqueue (insert) data into a queue –
·
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.
Algorithm of enqueue () -
if queue is full
return overflow
endif
rear <- rear + 1
queue[rear] <- data
return true
end procedure
2)
Dequeue () – dequeue
means accessing or removing an element from queue.
The following steps are taken to
perform dequeue operation –
·
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.
Algorithm of dequeue –
if queue isempty
return underflow
endif
data <- queue [front]
front <- front + 1
return true
end procedure
3)
Isfull () – check if
the queue is full.
begin procedure isfull
if rear equal to maximize
return true
else
return false
endif
end procedure
4)
Isempty () – this
function check if the queue is full or not.
Begin procedure isempty
If front is less than MIN or front is greater than rear
return true
else
return false
endif
end procedure
5)
Peek () – this
function is used to see the data at the front of
the queue.