Circular Queue
The shortcoming of static array implementation of linear queue is
that, once rear points to n [the max size of the array] no element
can be further inserted even if there is space. Circular queue is
another linear data structure which avoids this problem by
connecting the back of the array with the front to make it a circle.
By this way, memory is utilized more efficiently in case of circular
queue's.
Algorithm for Insertion in a circular queue
Insert CircularQueue(QUEUE, ITEM)
If (FRONT == 1 and REAR == N) or (FRONT == REAR + 1) Then
Print: Overflow
Return
Else
If (REAR == 0) Then [Check if QUEUE is empty]
(a) Set FRONT = 1
(b) Set REAR = 1
Else If (REAR == N) Then [If REAR reaches end if QUEUE]
Set REAR = 1
Else
Set REAR = REAR + 1 [Increment REAR by 1]
End If
Set QUEUE[REAR] = ITEM
End If
Algorithm for Deletion in a circular queue
Delete CircularQueue (QUEUE)
If (FRONT == 0) Then [Check for Underflow]
Print: Underflow
Return
Else
ITEM = QUEUE[FRONT]
If (FRONT == REAR) Then [If only element is left]
(a) Set FRONT = 0
(b) Set REAR = 0
Else If (FRONT == N) Then [If FRONT reaches end if QUEUE]
Set FRONT = 1
Else
Set FRONT = FRONT + 1 [Increment FRONT by 1]
End If
End If
Deque
A deque (pronounced “deck”) is a double-ended queue in which items can be
inserted and removed at either end, but no random access to elements in the
middle. Some scheduling systems for systems with multiple CPUs use deques.
When a process creates a new process, these are added at the front; when a
CPU “steals” a process from another CPU, it takes from the rear, and adds to its
own front (each CPU gets its own deque of processes). There are two variant of
double ended queue depending upon the restriction to perform insertion or
deletion operations at the two ends.
i. Input restricted deque: An input restricted deque is a deque, which allows
insertion at only 1 end, rear end, but allows deletion at both ends, rear and front
end of the lists.
ii. Output restricted deque:An output-restricted deque is a deque, which allows
deletion at only one end, front end, but allows insertion at both ends, rear and
front ends, of the lists.
Typical operations that are allowed on a deque are given as follows:
i. insertFirst(e): insert e at the beginning of the deque
ii. insertLast(e): insert e at the end of the deque
iii. removeFirst( ): remove and return the first element
iv. removeLast( ): remove and return the last element
v. first( ): return the first element
vi. last( ): return the last element
vii. isEmpty( ): return true if deque is empty; false otherwise
viii. size( ): return the number of objects in the deque
Priority queues
Priority queues are a generalization of stacks and queues. Rather than inserting
and deleting elements in a fixed order, each element is assigned a priority
represented by an integer. We always remove an element with the highest
priority, which is given by the minimal integer priority assigned. Priority queues
often have a fixed size. For example, in an operating system the runnable
processes might be stored in a priority queue, where certain system processes
are given a higher priority than user processes. Similarly, in a network router
packets may be routed according to some assigned priorities. In both of these
examples, bounding the size of the queues helps to prevent so-called denial-of-
service attacks where a system is essentially disabled by flooding its task store.
This can happen accidentally or on purpose by a malicious attacker.
The operations that need to be provided for a priority queue are shown in the
following table, assuming that just priorities (no associated information) are to be
stored in a priority queue.
CreatePriorityQ( ) - create an empty priority queue
boolean empty( ) - return true iff the priority queue is empty
void insert(p) - add priority p to the priority queue
removeMax( ) - remove and return the highest priority from the priority queue
(error if the priority queue is empty)
A priority queue can be implemented using many of the data structures that
we've already studied (an array, a linked list, or a binary search tree). However,
those data structures do not provide the most efficient operations. To make all
of the operations very efficient, we'll use a new data structure called a heap.