[Link]

my

QUEUE

DKS3083
 [Link]

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).
• basic queue operations:
– add (enqueue): Add an element to the rear/back.
– remove (dequeue): Remove the front element.
– peek: Examine the front element.
 [Link]

What are 2 differences between stack and

queue?

To answer this question, scan the

following QR code
 [Link]

Using Queues: Coded Messages

• A Caesar cipher is a substitution code that
encodes a message by shifting each letter in a
message by a constant amount k
• If k is 5, a becomes f, b becomes g, etc.
• Example: n qtaj ofaf
• Used by Julius Caesar to encode military
messages for his generals (around 50 BC)
• This code is fairly easy to break!
 [Link]

Implement with array?

• 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)
 [Link]

Approach On Queue as a Circular

Array
• If we don't fix one end of the queue at index 0, we
won't have to shift elements
• Circular array is an array that conceptually loops
around on itself
• The last index is thought to “precede” index 0
• In an array whose last index is n, the location
“before” index 0 is index n; the location “after”
index n is index 0
• Need to keep track of where the front as well as the
rear of the queue are at any given time
 [Link]

front
After 5
1 After 7 enqueues 1 dequeues
0 0
front
12 12
11 11
rear rear
10 10

rear
1
0
front
12
11
After 8 more enqueues
10
 [Link]

Circular Array Implementation of a

Queue

3 2 3
1 4
front queue 5
cq 0
8 5 n-1 6
rear count n-2 7
n-3 8
9
... 10
 [Link]

A Queue Straddling the End of a Circular

Array

98 2 3
1 4
front queue 5
cq 0
2 4 99 6
rear count 98 7
97 8
9
... 10
 [Link]

Circular Queue Drawn Linearly

Queue from previous slide

98
cq front queue
0 1 2 3 4 96 97 98 99
2 4 …
rear count
 [Link]

Circular Array Implementation

• When an element is enqueued, the value of
rear is incremented
• But it must take into account the need to loop
back to index 0:

rear = (rear+1) % [Link];

• Can this array implementation also reach

capacity?
 [Link]
Example: array of length 4
What happens?
0 1 2 3
2
front queue
cq
Suppose we try to add
1 3
one more item to a
rear count queue implemented by
an array of length 4

0 1 2 3
2 The queue is now full.
How can you tell?
front queue
cq
2 4
rear count
 [Link]

Add another item!

Need to expand capacity…
0 1 2 3
We can’t just double
2
the size of the array
front queue and copy values to
cq
the same positions
2 4
as before: circular
rear count properties of the
queue will be lost

0 1 2 3 4 5 6 7
2
front queue
cq
2 4 These locations
rear count should be in use
 [Link]

We could build the new array, and copy the queue elements
into contiguous locations beginning at location front:

0 1 2 3 4 5 6 7
2
front queue
cq
6 4
rear count
 [Link]

Better: copy the queue elements in order to the beginning

of the new array

0 1 2 3 4 5 6 7
0
front queue
cq
4 4
rear count
 [Link]

New element is added at rear = (rear+1) % [Link]

See expandCapacity() in [Link]

0 1 2 3 4 5 6 7
0
front queue
cq
5 5
rear count
 [Link]

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.
 [Link]

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.
 [Link]

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.
 [Link]

Queue Implementation
class Queue { private:
int front;
public: int rear;
Queue(int); ItemType* items;
Queue(); int maxQue;
};
~Queue();
void MakeEmpty();
bool IsEmpty() const;
bool IsFull() const;
void Enqueue(ItemType);
void Dequeue(ItemType&);
 [Link]

Queue Implementation (cont.)

Queue() {
maxQue = max + 1;
front = maxQue - 1;
rear = maxQue - 1;
items = new ItemType[maxQue];
}
MakeEmpty(){
front = maxQue - 1;
rear = maxQue - 1;
}
 [Link]

IsEmpty()
{
return (rear == front);
}

IsFull() const
{
return ( (rear + 1) %
maxQue == front);
}
 [Link]

void Enqueue (int newItem)

{
rear = (rear + 1) % maxQue;
items[rear] = newItem;
}

Dequeue (int & item)

{
front = (front + 1) % maxQue;
item = items[front];
}
 [Link]

Queue overflow

• The condition resulting from trying to add

an element onto a full queue.

if(![Link]())
[Link](item);
 [Link]

Case Study: Simulation

• Queuing System: consists of servers and
queues of objects to be served.

• Simulation: a program that determines how

long items must wait in line before being
served.
 [Link]

Case Study: Simulation (cont.)

• Inputs to the simulation:
(1) the length of the simulation
(2) the average transaction time
(3) the number of servers
(4) the average time between job
arrivals
 [Link]

Case Study: Simulation (cont.)

• Parameters the simulation must vary:
(1) number of servers
(2) time between arrivals of items

• Output of simulation: average wait time.

[Link]
 [Link]

Linked Implementation of a Queue

A queue q containing four elements

rear
q
front

4
count
 [Link]

Discussion

• What if the queue is empty?

• What if there is only 1 element?
To answer this question, scan the following
QR Code
 [Link]

Queue After Adding Element

New element is added in a node at the end of the list,

rear points to the new node, and count is incremented

rear
q
front

5
count
 [Link]

Queue After a dequeue Operation

Node containing is removed from the front of the list (see

previous slide), front now points to the node that was
formerly second, and count has been decremented.

rear
q
front

4
count
 [Link]

Implementation
struct Queue{
string data;
Queue * next;
};
Queue *rear, *front;
[Link]
[Link]
 [Link]

Using Queues:
Ticket Counter Simulation
• Simulate the waiting line at a movie theatre:
• Determine how many cashiers are needed to keep
the customer wait time under 7 minutes
• Assume:
• Customers arrive on average every 15 seconds
• Processing a request takes two minutes once a
customer reaches a cashier
 [Link]

Results of Ticket Counter Simulation

Number of
Cashiers

Average time
(in seconds)