Queue

Qurra-tul-ann
 Queue
• A queue is a linear data structure into which elements can
only be inserted at one end(rear/tail) and deleted from the
other(Front/head)
• Queue is a First In First Out data structure (FIFO) data
structure
• In a stack we remove the item that is most recently added
while in a queue, we remove the item that is least recently
added.
 Queue Example
• We queue up while depositing a utility bill or purchasing a
ticket.
• Serving requests on a single shared resource, like a printer,
CPU task scheduling etc.
• Handling of interrupts in real-time systems. The interrupts are
handled in the same order as they arrive, First come first
served.
• A whole branch of mathematics, known as queueing theory,
deals with computing, probabilistically, how long users expect
to wait on a line, how long the line gets, and other such
questions
 Types of Queues
• Simple Queue: insert the at the back and remove from front of the queue.
(FIFO order)
• Double-Ended Queue (Deque): insertion and deletion operations can be
performed from both ends. (FIFO order)
 Input Restricted Queue: The input can be taken from only one end
but deletion can be done from any of the ends.
 Output Restricted Queue: The input can be taken from both ends but
deletion can be done from only one end.
• Circular Queue: This is a special type of queue where the last position is
connected back to the first position. (in FIFO order)
• Priority Queue: A priority queue is a special queue where the elements
are accessed based on the priority assigned to them.
 Ascending Priority Queue: Element with smallest priority value is
popped first
 Descending Priority Queue: Element with largest priority is popped
first
 Queue Operations
• enqueue(): Inserts an element at the end of the
queue i.e. at the rear end.
• dequeue(): removes and returns an element that is at
the front end of the queue.
• front(): returns the element at the front end without
removing it.
• rear(): This operation returns the element at the rear
end without removing it
• isEmpty() - checks if queue is empty or not.
• isFull() - checks if queue is full or not.
 Queue Issue
• Queue Overflow :
The condition resulting from trying to add an element onto a full queue.
if(![Link]())
[Link](item);

• Queue Underflow
The condition resulting from trying to remove an element from an empty
queue.
if(![Link]())
[Link](item);
 Queue-Enqueue
• Steps to enqueue (insert) data into a queue
Step 1 −Check if queue is full.
Step 2 − If queue is full, produce overflow error & exit.
Step 3 −If queue is not full, increment rear pointer
Step 4 −Add element to the queue location, where rear is pointing.
Step 5 − return success.
 Queue-Enqueue
void enqueue(int val)
{
if (isFull()) {
cout << "Queue is full" << endl;
return;
}
// if queue is empty, set front to 0
if (isEmpty())
front = 0;

rear++;
arr[rear] = val;
}
 Queue-Dequeue
• The following steps are taken to perform dequeue
operation
Step 1 − Check if queue is empty.
Step 2 − If queue is empty, produce underflow error and exit.

Step 3 − If queue is not empty, access data where front is pointing.

Step 4 − Increment front pointer to point next available data element.
Step 5 − return success
 Queue-Dequeue
int dequeue()
{
if (isEmpty()) {
cout << "Queue is empty" << endl;
return -1;
}
int ans = arr [front];
front++;

// if queue becomes empty, reset both pointers

if (isEmpty())
front = rear = -1;

return ans;
}
 Queue-isfull/isempty
Void isempty()
{ if(rear==-1 && front ==-1)
cout<<“queue is empty”;
}
Void isfull()
{ if(rear== MAX_SIZE-1)
cout<<“queue is full”;
}
 Queues using Arrays
• For each queue data structure, we keep an array, Queue[], and
the positions Front and Rear, which represent the ends of the
queue.
• In queue ,both ends are required
• Array implementation of a Queue do have drawbacks. The
maximum queue size has to be set at compile time, rather than
at run time. Space can be wasted, if we do not use the full
capacity of the array.
Queues using Arrays
Queues using Arrays
Queues using Arrays-Code
Queues using Arrays-Code
Queues using Arrays-Code
Queues using Arrays-Code
 Queues using Arrays-STL
• push() : Inserts an element at the back of the queue.
• pop() : Removes an element from the front of the queue.
• front() : Returns the first element of the queue.
• back() : Returns the last element of the queue.
• empty(): Returns true if the queue is empty.
• size() : Returns the number of elements in the queue.
Queues using Arrays-STL
 Queues using Arrays

• Array has reached its limit–size problem with array

• Two location at start are vacant–how we can use these
locations?
• Is there any work around instead of shifting elements?
 Array- Issues
• The simple array implementation of queue has a problems:
 It is wasting space
 Because front is moving towards back and leaving empty
space behind.
 Elements are stored towards end of array and front cells
may be empty due to dequeue
• To resolve this problem array can be used as a circular array.
 Circular Queue
• Circular queue is a queue where the last element of the
queue is connected to the first element of the queue.
This is known as a circular array implementation.
 Circular Queue using Array
• For array implementation for circular queue, we use the
mathematical concept of modular (or circular) increment.
• In this concept, a value that is being incremented will wrap
around a particular threshold value. Formula:
value = (value + 1) % threshold_value;
 Circular Queue-Enqueue

• Queue is Full now. Queue does not have such characteristic

to become full
• Its implementation Array has been full–what is the
remedy?
• How we check that Queue is full or empty?
 Circular Queue-Enqueue
void enQueue (int value)
{ if (isFull ())
{ cout << "Queue is full." << endl; }
else
{ if (front == -1)
{ front = 0; }
rear = (rear + 1) % MAX_SIZE;
arr[rear] = value;
cout << "Enqueued element: " << value << endl;
}
}
 Circular Queue-Dequeue
int deQueue ()
{ int element;
if (isEmpty ()) {
cout << "Queue is empty." << endl;
return -1; }
else{ element = arr[front];
if (front == rear) { // if only one element left in the queue.
front = -1;
rear = -1; }
else { front = (front + 1) % MAX_SIZE; }
cout << "Dequeued element: " << element << endl;
return element; }
}
 Circular Queue
bool isFull ()
{ if ((front == 0 && rear == MAX_SIZE - 1)
|| (rear == (front - 1) % (MAX_SIZE - 1)))
{ return true; }
return false;
}
bool isEmpty ()
{ if (front == -1)
{ return true; }
return false;
}
Circular Queue
Circular Queue
Circular Queue
Circular Queue
 Uses of Queue
• one of the most useful use is Simulation.
• A simulation program attempts to model a real-world
phenomenon.
• Many popular video games are simulations, e.g., SimCity, Flight
Simulator etc.
• Computer simulation is very powerful tool and it is used in
different high tech industries, especially in engineering projects.
• eg: used in aero plane manufacturing or simulation of computer
networks, traffic networks etc.
• If the simulation is accurate, the result of the program should
mirror the results of the real-world event.
• Thus it is possible to understand what occurs in the real-world
without actually observing its occurrence .
 Bank-Simulation
• A Bank with Four Tellers, anyone can attend the customer.
• A customer enters the bank at a specific time (t1) desiring to
conduct a transaction.
• The transaction (withdraws, deposit) will take a certain
period of time (t2).
• If a teller is free, the teller can process the customer’s
transaction immediately and the customer leaves the bank
at t1+t2.
• it is possible that none of the four tellers is free in which case
there is a line of customers at each teller.
• An arriving customer proceeds to the back of the shortest
line and waits for his turn
 Bank-Simulation
• The customer leaves the bank at t2 time units after reaching
the front of the line.
• The time spent at the bank is t2 plus time waiting in line.
• So what we want to simulate is the working environment of
the bank that there are specific number of queues of
customers in the bank in front of the tellers.
• We want to know the average waiting time of a bank
customer.
• What if there is lot of rush in the bank?
• There are only Four tellers and all are busy. So every new
customer will form a queue.
• Which queue you will choose to stand in when you face rush?
 Bank-Simulation
• A queue in front of each teller.
• A Customer enters, analyse the queue and wants to join the
shortest queue.
• This customer has to wait for the persons in front of him to be
served.
• In this simulation customer can not change his queue

• At the end of the day we have to calculate the average waiting

time of each customer.
• We need to write a program that will simulate the this situation.
 Bank-Simulation

• Which queue is shorter?

• Which queue a new customer will want to join?
 Bank-Simulation

Two persons arrives, they join Queue 1 and Queue 3 respectively

 Bank-Simulation
• Three customer in Queue 1 and Queue 3 and two customers
in Queue 2 and Queue 4 are waiting.
• After the customers are served they leave the queue and bank
and similarly new customers arrive and join the queue which
is shortest.
• This process will go on
• The serving time of each customer is not same.
• Sometimes a longer queue is clear more quickly than a
shorter.
• We need to model this situation
 Simulation Model
• Two Common Models
1. Time Based Simulation
 Main a timeline or clock. The clock ticks and things
happen
when the time reaches the moment of an event.
2. Event Based Simulation
 Don’t wait for the clock to tick until the next event.
 Compute the time of next event and maintain a list of
events in increasing order of time.
 Time Based Simulation Model
• Suppose a clock in computer where minute hand moves after
every minute.
• Time of arrival of each customer is known and his transaction takes
5 minutes.
• Clock is ticking and after 5 minutes we ask the customer to leave
the bank.
• In the program, person is represented by some object
• Clock continues ticking, and every customer will take 5 minutes.
• During this time, the clock keeps on ticking. The program will do
nothing during this time period.
• Although some other customer can enter the bank.
• If the program is in some loop, it will do nothing in that loop until
the completion of the transaction time
 Time Based Simulation–Bank Example
• All tellers are free.
• Customer C1 comes in 2 minutes after the opening of the bank
(9:02 am). His transaction (withdraw money) will require 4 minutes.
• Customer C2 arrives 4 minutes after the bank opens (9:04 am). He
needs 6 minutes for transaction.
• Customer C3 arrives 12 minutes after the bank opens and needs 10
minutes for his transaction
Time Based Simulation-Bank Example
Pseudo code of bank routine
clock = 0;
while ( clock <= 24*60 ) { // one day
read new customer;
If [Link] == clock
insert into shortest queue;
check the customer at head of all four queues.
if transaction is over
remove from queue.
clock = clock + 1;
}
Event Based Simulation-Bank Example
• Don’t see the clock, look at events only
 Priority Queue
• FIFO is not always true in real life
• Imagine a ticket window at Daewoo Terminal, the person who arrives first
will get the ticket before the person who arrives later.
• We can develop such queues in which the condition for leaving the queue
is not to enter first. There may be some priority
• A priority queue is a collection of zero or more items, associated with
each item is a priority.
• A Priority Queue can be implemented using Arrays, Linked List or Heap.
• In priority queue, enqueue and dequeue operations consider the priorities
of items to insert and remove them.
• The highest priority can be either the most minimum value or most
maximum .
• Priority are used in operating Systems for process scheduling and job
scheduling.
• There is following applications of Priority Queue: Dijktra’s shortest path
algorithm, Data Compression->Huffman Code, Heap Sort
 Operations on Priority Queue
• enqueue(): It is used to insert the element at the end of the queue.
• peek():
 Traverse across the priority queue and find the element with the
highest priority and return its index.
 In the case of multiple elements with the same priority, find the
element with the highest value having the highest priority.
• dequeue():
 Find the index with the highest priority using the peek()
 function .let’s call that position as ind, and then shift the position
of all the elements after the position ind one position to the left.
 Decrease the size by one.
 Priority Queue
• Using ordered Array
 In ordered Array elements store in sorted for it can be in
ascending order or descending order.
 Insertion takes -- O(n) time complexity
 Deletion takes -- O(1) time complexity.
• Using unordered Array
 In unordered Array elements store in as they insert in Queue
there is no sorting.
 Insertion takes -- O(1) time complexity
 Deletion takes -- O(n) time complexity.
Priority Queue in Bank Simulation

• The above set of statement are from an input file which

gives information about the customer arrival time and
serving time.
• We will collect the events from the input file and placed in
priority queue as events are occurring
• Initially all four teller queues are empty
Priority Queue –Using Array
Priority Queue –Using Array
Priority Queue –Using Array
Priority Queue –Using Array
 Priority Queue-STL
They are implemented as a heap in memory.
 Time Complexity Analysis
• Arrays enqueue() dequeue() peek()

O(1) O(n) O(n)

• Heap insert() remove() peek()

O(log n) O(log n) O(1)