Queues

What is a Queue?

2
 What is a queue?
• It is an ordered group of homogeneous items of
elements.
• Queues have two ends:
– Elements are added at one end.
– Elements are removed from the other end.
• The element added first is also removed first
(FIFO: First In, First Out).
tail queue head
elements elements
4 3 2 1
enter exit
no changes of order
3
 Queue Overview

• Queue ADT
• Basic operations of queue
– Enqueuing, dequeuing etc.
• Implementation of queue
– Array
– Linked list

4
 Queue ADT
• Like a stack, a queue is also a list. However,
with a queue, insertion is done at one end,
while deletion is performed at the other end.
• Accessing the elements of queues follows a
First In, First Out (FIFO) order.
– Like customers standing in a check-out line in a
store, the first customer in is the first customer
served.

5
 The Queue ADT
• Another form of restricted list
– Insertion is done at one end, whereas deletion is
performed at the other end
• Basic operations:
– enqueue: insert an element at the rear of the list
– dequeue: delete the element at the front of the
list

• First-in First-out (FIFO) list 6

 The Queue ADT

• The Queue ADT stores arbitrary • Auxiliary queue operations:

objects – front(): returns the element at the
• Insertions and deletions follow the front without removing it
first-in first-out (FIFO) scheme – size(): returns the number of
• Insertions are at the rear of the elements stored
queue and removals are at the – isEmpty(): returns a Boolean
front of the queue value indicating whether no
elements are stored
• Main queue operations:
– enqueue(object o): inserts element • Exceptions
o at the end of the queue – Attempting the execution of
– dequeue(): removes and returns dequeue or front on an empty
the element at the front of the queue throws an
queue EmptyQueueException
7
 The ADT Queue

Queue
-maxSize : int
-queueArray [] : long
-front : int
QueueApp -rear : int
-nItems : int
Interface1 +Queue()
+insert() : void
+remove() : long
+peekFront() : long
+isEmpty() : bool
+isFull() : bool
+size() : int

UML diagram for the class Queue

8
 Queue Specification
• Definitions: (provided by the user)
– MAX_ITEMS: Max number of items that might be on
the queue
– ItemType: Data type of the items on the queue

• Operations
– MakeEmpty
– Boolean IsEmpty
– Boolean IsFull
– Enqueue (ItemType newItem)
– Dequeue (ItemType& item) (serve and retrieve) 9
 Applications of Queues
• Direct applications
– Waiting lines
– Access to shared resources (e.g., printer)

• Indirect applications
– Auxiliary data structure for algorithms
– Component of other data structures
– Job scheduling (e.g. Round-Robin algorithm for
CPU allocation)

10
 Various Queues

• Normal queue (FIFO)

• Circular Queue (Normal Queue)
• Priority Queue

11
 Enqueue and Dequeue
• Primary queue operations: Enqueue and
Dequeue
• Like check-out lines in a store, a queue has a
front and a rear.
• Enqueue
– Insert an element at the rear of the queue
• Dequeue
– Remove an element from the front of the queue

Remove Insert
(Dequeue) front rear (Enqueue) 12
 Array-based Queue
• Use an array of size N in a circular
fashion
• Two variables keep track of the front and
rear
– f index of the front element
– r index immediately past the rear
element
• Array location r is kept empty
normal configuration
Q
0 1 2 f r

wrapped-around configuration
Q
0 1 2 r f
13
14
15
 Enqueue (ItemType newItem)
• Function: Adds newItem to the rear of the
queue.
• Preconditions: Queue has been initialized
and is not full.
• Postconditions: newItem is at rear of
queue.

16
 Enqueue
public void enQueue(int x)
{
if(!isFull())
{
rear=(rear+1)%maxSize;
queueArray[rear]=x;
nItems++;
}
else
System.out.println("Can not be added");
}

17
 Dequeue (ItemType& item)

• Function: Removes front item from queue

and returns it in item.
• Preconditions: Queue has been initialized
and is not empty.
• Postconditions: Front element has been
removed from queue and item is a copy of
removed element.

18
 Dequeue

public Object deQueue()

{
if(!isEmpty())
{
front=(front+1)%maxSize;
nItems--;
return (queueArray[front]);
}
else
{
System.out.println("Can not be deQueued");
return null;
}
}
19
 Implementation issues

• Implement the queue as a circular structure.

• How do we know if a queue is full or
empty?
• Initialization of front and rear.
• Testing for a full or empty queue.

20
 Empty or Full?
• Empty queue
– rear = front - 1
• Full queue?
– the same!
– Reason: n values to represent n+1 states
• Solutions
– Use a boolean variable to say explicitly whether the queue is
empty or not
– Make the array of size n+1 and only allow n elements to be
stored
– Use a counter of the number of elements in the queue

21
 isEmpty or isFull

public boolean isFull()

{
return (nItems==maxSize);
}

public boolean isEmpty()

{
return (nItems==0);
}

22
 Circular Queue

• When a new item is inserted at the rear, the pointer to

rear moves upwards.
• Similarly, when an item is deleted from the queue the
front arrow moves downwards.
• After a few insert and delete operations the rear might
reach the end of the queue and no more items can be
inserted although the items from the front of the queue
have been deleted and there is space in the queue.

23
 Circular Queue

• To solve this problem, queues implement wrapping

around. Such queues are called Circular Queues.
• Both the front and the rear pointers wrap around to the
beginning of the array.
• It is also called as “Ring buffer”.
• Items can inserted and deleted from a queue in O(1)
time.

24
Implementation :Wrapped Configuration

EMPTY QUEUE

[2] [3] [2] [3]

J2 J3

[1] [4] [1] J1 [4]

[0] [5] [0] [5]

front = 0 front = 0
rear = - 1 rear = 3

Can be seen as a circular queue

25
Leave one empty space when queue is full, Why?

FULL QUEUE FULL QUEUE

[2] [3] [2] [3]

J2 J3 J8 J9

[1] J1 J4 [4][1] J7 [4]

J5 J6 J5

[0] [5] [0] [5]

front =0 front =4
rear = 5 rear =3

How to test when queue is empty?

How to test when queue is full?

26
 Queue Class
• Attributes of Queue
– front/rear: front/rear index
– nItem: number of elements in the queue
– maxSize: capacity of the queue
– values: point to an array which stores elements of the queue
• Operations of Queue
– IsEmpty: return true if queue is empty, return false otherwise
– IsFull: return true if queue is full, return false otherwise
– Enqueue: add an element to the rear of queue
– Dequeue: delete the element at the front of queue
– DisplayQueue: print all the data
– front(): returns the element at the front without removing it
– size(): returns the number of elements stored
27
 Create Queue
• Queue(int size = 10)
– Allocate a queue array of size. By default,
size = 10.
– front is set to 0, pointing to the first element
of the array
– rear is set to -1. The queue is empty initially.

Queue(int size /* = 10 */) {

queueArray = new double[size];
maxSize = size;
front = 0;
rear = -1;
nItem = 0;
} 28
 Exercise: Queues
• Describe the output of the following series of queue operations
– enqueue(8)
– enqueue(3)
– dequeue()
– enqueue(2)
– enqueue(5)
– dequeue()
– dequeue()
– enqueue(9)
– enqueue(1)

29
 Deque

• It is a double-ended queue.
• Items can be inserted and deleted from either ends.
• More versatile data structure than stack or queue.
• E.g. policy-based application (e.g. low priority go
to the end, high go to the front)
• In a case where you want to sort the queue once in
a while, What sorting algorithm will you use?

30
 Priority Queues

• More specialized data structure.

• Similar to Queue, having front and rear.
• Items are removed from the front.
• Items are ordered by key value so that the item with
the lowest key (or highest) is always at the front.
• Items are inserted in proper position to maintain the
order.
• Let’s discuss complexity

31
 Priority Queue Example

PrioityQ
-maxSize : int
-queueArray [] : long
PriorityQApp
-nItems : int
Interface1 +Queue()
+insert() : void
+remove() : long
+peekMin() : long
+isEmpty() : bool
+isFull() : bool

32