CHAPTER 5 : QUEUES
BCS1223: DATA STRUCTURES & ALGORITHMS
OBJECTIVE
To introduce:
Queues concept
Queues operations
Using Array-Based Implementation
Application using queues
Queue Simulation
INTRODUCTION
Queue is linear list in which data can only be inserted at
one end, called the rear, and deleted from the other end,
called the front.
First-In-First-Out (FIFO) concept.
Figure 1: The queue concept
INTRODUCTION
Two simple queue applications:
Queue Simulation modeling activity used to generate
statistics about the performance of queues.
Categorizing Data rearrange data without
destroying their basic sequence (multiple queues).
INTRODUCTION
Basic operations:
1) Add insert a given element at the back of the queue.
Figure 2: Add
INTRODUCTION
2) Remove if the queue is not empty, delete and return the element
that is at the front of the queue.
Figure 3: Remove
Fig. 4: Peek operation
INTRODUCTION
3) First if the queue is not empty, return the element that is at the front
the queue.
Figure 4: First
4) Size return the number of elements in the queue.
of
INTRODUCTION
Example:
Given queue Q with list of operations as below. Illustrate the queue operations step
by step:
Q.add(green), Q. add(blue), Q.remove( ), Q.add (red), frontItem = Q.first( ), lastItem =
Q.last(), Q.remove( ), Q.remove().
Figure 5: Queue example
QUEUE USING ARRAY-BASED
IMPLEMENTATION
front
rear
Array Implementation
Different compared to Stack because of two variables: front and rear.
Let Q store characters, defined as arrays of 6 elements numbered 0 to
5 as follows with front and rear index.
0
front
rear
QUEUE USING ARRAY-BASED
IMPLEMENTATION
1. Start operation: construct a queue
Queue Q;
front and rear = -1;
-1
front
// to show no data
0
2
rear
QUEUE USING ARRAY-BASED
IMPLEMENTATION
2. Input string ABU:
Q.add(A)
// add(A)
rear++;
// increase first
data[rear] = A;
// and assignment
-1 0
front
rear
QUEUE USING ARRAY-BASED
IMPLEMENTATION
3. Next input:
Q.add(B)
rear++;
data[rear] = B;
-1 0
A B
front
rear
QUEUE USING ARRAY-BASED
IMPLEMENTATION
4. Next input:
Q.add(U)
rear++;
data[rear] = U;
-1 0
A B U
front
rear
QUEUE USING ARRAY-BASED
IMPLEMENTATION
5. Remove operation:
Remove: remove the front item
while (!Q.isEmpty())
{
Q.remove(ch);
System.out.print(ch);
}
System.out.println();
Q.remove(ch);
front++; // increase first
ch = data[front];
QUEUE USING ARRAY-BASED
IMPLEMENTATION
After first iteration:
-1 0 1 2 3
A B U
5
Output : A
front
rear
However A still exists in arrays but no meaning.
The most important, front point to the front item.
QUEUE USING ARRAY-BASED
IMPLEMENTATION
Next iteration:
-1
0 1 2 3
A B U
5
Output : AB
front
rear
QUEUE USING ARRAY-BASED
IMPLEMENTATION
Next iteration:
-1
0 1 2 3
A B U
5
Output : ABU
front
rear
Now, Queue is empty.
Although string ABU exists in Queue, but it has no meaning because
front == rear.
With front == rear, its not guaranteed that Queue is empty.
QUEUE USING ARRAY-BASED
IMPLEMENTATION
// Read next string: BOLA
Q.add(B)
rear++;
data[rear] = B;
-1
front
0 1 2 3 4
A B U B
rear
QUEUE USING ARRAY-BASED
IMPLEMENTATION
Q.add(O)
rear++;
data[rear] = O;
-1
front
0 1 2 3 4 5
A B U B O
rears
QUEUE USING ARRAY-BASED
IMPLEMENTATION
Q.add(L)
rear++;
data[rear] = L;
-1
front
0 1 2 3 4 5
A B U B O L
rear
QUEUE USING ARRAY-BASED
IMPLEMENTATION
Q.add(A) ?
For this case, space in Queue still exists, with rear formula modification:
rear = (rear+1) mod MaxQLength;
data[rear] = A;
-1
front
0 1 2 3 4 5
A B U B O L
rear
QUEUE USING ARRAY-BASED
IMPLEMENTATION
6. Enter Queue with string TOM
T and O can fill up the space, but not M because Queue is full when
front == rear.
-1
0 1 2 3 4 5
A T O B O L
front
rear
How to differentiate whether queue is full or empty?
If front == rear, is not enough, we need another variable called ItemInQ of
type bool. Assign ItemInQ as false if queue is empty and true if queue is
full.
QUEUE USING ARRAY-BASED
IMPLEMENTATION
Queue Program:
Definitions of data structure and functions prototype for queue operations:
A Queue Interface
1 /**
2 * The <code>Queue</code> interface specifies the basic operations
3 * of a first-in-first-out (FIFO) containers.
4 */
5 public interface Queue {
6
7 /**
8 * Adds the specified element to the back of this queue.
9*
10 * @param object the element to be added to this queue.
11 */
12 public void add(Object object);
13
14 /**
15 * Returns the element at the front of this queue.
16 *
17 * @return the element at the front of this queue.
18 * @throws IllegalStateException if this queue is empty
19 */
20 public Object first();
21
22 /**
23 * Removes and returns the element at the front of this queue.
24 *
25 * @return the element at the front of this queue.
26 * @throws IllegalStateException if this queue is empty
27 */
28 public Object remove();
29
30 /**
31 * Returns the number of elements in this queue.
32 *
33 * @return the number of elements in this queue.
34 */
35 public int size();
36 }
The ArrayQueue class
QUEUE USING ARRAY-BASED
IMPLEMENTATION
The ArrayQueue class
public class ArrayQueue implements Queue {
private Object[] a;
private int front, back;
public ArrayQueue(int capacity) {
a = new Object[capacity];
}
public void add(Object object) {
if (back == a.length) resize();
a[back++] = object;
}
public Object first() {
if (size()==0) throw new IllegalStateException("queue is empty");
return a[front];
}
QUEUE USING ARRAY-BASED
IMPLEMENTATION
public boolean isEmpty() {
return (size() == 0);
}
public Object remove() {
if (size()==0) throw new IllegalStateException("queue is empty");
Object object=a[front];
a[front++] = null;
return object;
}
public int size() {
return back - front;
}
private void resize() {
Object[] aa = a;
a = new Object[2*aa.length];
System.arraycopy(aa, front, a, 0, size());
}
}
QUEUE USING ARRAY-BASED
IMPLEMENTATION
The implementation file begins as follows:
public class TestArrayQueue {
public static void main(String[] args) {
Queue kids = new ArrayQueue(2);
kids.add("Sara");
kids.add("John");
kids.add("Andy");
System.out.println("kids.size(): " + kids.size());
System.out.println("kids.first(): " + kids.first());
System.out.println("kids.remove(): " + kids.remove());
System.out.println("kids.size(): " + kids.size());
System.out.println("kids.first(): " + kids.first());
kids.add("Mike");
System.out.println("kids.size(): " + kids.size());
System.out.println("kids.first(): " + kids.first());
System.out.println("kids.remove(): " + kids.remove());
System.out.println("kids.size(): " + kids.size());
System.out.println("kids.first(): " + kids.first());
System.out.println("kids.remove(): " + kids.remove());
System.out.println("kids.size(): " + kids.size());
System.out.println("kids.first(): " + kids.first());
System.out.println("kids.remove(): " + kids.remove());
System.out.println("kids.size(): " + kids.size());
System.out.println("kids.first(): " + kids.first());
}
}
QUEUE APPLICATION:
QUEUE SIMULATION
Consider the real-world example of cars arriving at a station of toll
booths. The clients are the cars and the servers are the toll booths
(or their operators).
The client/server system is pictured as below with three toll booths,
labeled A, B and C. The cars are numbered. Cars 24, 21 and 22 are
being served, while cars 25-28 are waiting in the queue.
QUEUE APPLICATION:
QUEUE SIMULATION
The objects are:
Clients (cars)
Servers (toll booths)
A queue
The events are:
A client arrives at the queue
A server begins serving a client
A server finishes serving a client
QUEUE APPLICATION:
QUEUE SIMULATION
Algorithm Client/Server Simulation
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
Repeat steps 2 and 6 for times t = 0, 1, ...
If t = time for next arrival, do steps 3-5.
Create a new client.
Add the client to the queue.
Set time for next arrival.
Repeat steps 7 and 8 for each server.
If t = time for the server to finish serving, have it stop.
If server is idle and the queue is not empty, do steps 9-10.
Remove client from the queue.
Tell server to start serving client.
QUEUE APPLICATION:
QUEUE SIMULATION
Client/Server Simulation
for (int t=0; ; t++) { //step 1
if (t==nextArrivalTime) { //step 2
Client client = clients[i++] = new SimClient(i,t); //step 3
queue.add(client); //step 4
nextArrivalTime = t + randomArrival.nextInt(); //step 5
}
for (int j=0; j<numServers; j++) { //step 6
Server server = servers[j];
if (t==server.getStopTime()) server.stopServing(t); //step 7
if (server.isIdle() && !queue.isEmpty()) { //step 8
Client client = (SimClient)queue.remove(); //step 9
server.startServing(client,t); //step 10
}
}
}
QUEUE APPLICATION:
QUEUE SIMULATION
Server Interface
public interface Server {
public int getMeanServiceTime();
public int getStopTime();
public boolean isIdle();
public void startServing(Client client, int t);
public void stopServing(int t);
}
Client Interface
public interface Client {
public void setStartTime(int t);
public void setStopTime(int t);
}
QUEUE APPLICATION:
QUEUE SIMULATION
Server and Client objects
QUEUE APPLICATION:
QUEUE SIMULATION
A Server class
public class SimServer implements Server {
private Client client;
private int id, meanServiceTime, stopTime=-1;
private java.util.Random random;
public SimServer(int id, int meanServiceTime) {
this.id = id;
this.meanServiceTime = meanServiceTime;
this.random = new ExponentialRandom(meanServiceTime);
}
public int getMeanServiceTime() {
return meanServiceTime;
}
public int getStopTime() {
return stopTime;
QUEUE APPLICATION:
QUEUE SIMULATION
public boolean isIdle() {
return client==null; }
public void startServing(Client client, int t) {
this.client = client;
this.client.setStartTime(t);
this.stopTime = t + random.nextInt();
System.out.println(this + " started serving " + client
+ " at time " + t + " and will finish at time " + stopTime); }
public void stopServing(int t) {
client.setStopTime(t);
System.out.println(this+ " stopped serving " + client
+ " at time " + t);
client = null;
}
public String toString() {
String s="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
return "Server " + s.charAt(id); }
}
QUEUE APPLICATION:
QUEUE SIMULATION
A Client class
public class ExponentialRandom extends java.util.Random {
private double mean;
public ExponentialRandom(double mean) {
super(System.currentTimeMillis());
this.mean = mean;
}
public double nextDouble() {
return -mean*Math.log(1.0-super.nextDouble());
}
public int nextInt() {
return (int)Math.ceil(nextDouble());
}
}
QUEUE APPLICATION:
QUEUE SIMULATION
Exponential Distribution
public class SimClient implements Client {
int id, arrivalTime=-1, startTime=-1, stopTime=-1;
public SimClient(int id, int t) {
this.id = id;
arrivalTime = t;
System.out.println(this + " arrived at time " + t); }
public int getStartTime() {
return startTime; }
public int getStopTime() {
return stopTime; }
public void setStartTime(int t) {
startTime = t; }
public void setStopTime(int t) {
stopTime = t; }
public String toString() {
return "Client " + id; } }
QUEUE APPLICATION:
QUEUE SIMULATION
A Simulation class
public class Simulation {
static int numServers;
static int numClients;
static int meanServiceTime;
static int meanInterarrivalTime;
static Server[] servers;
static Client[] clients;
static Queue queue = new LinkedQueue();
static java.util.Random randomArrival;
static java.util.Random randomService;
public static void main(String[] args) {
init(args);
// See Listing 6.3 on page 173
QUEUE APPLICATION:
QUEUE SIMULATION
static void init(String[] args) {
if (args.length<4) {
System.out.println("Usage: java Simulation <numServers> "
+ "<numClients> <meanServiceTime> <meanInterarrivalTime>");
System.out.println(" e.g.: java Simulation 3 100 12 4");
System.exit(0);
}
numServers = Integer.parseInt(args[0]);
numClients = Integer.parseInt(args[1]);
meanServiceTime = Integer.parseInt(args[2]);
meanInterarrivalTime = Integer.parseInt(args[3]);
servers = new Server[numServers];
clients = new Client[numClients];
randomService = new ExponentialRandom(meanServiceTime);
randomArrival = new ExponentialRandom(meanInterarrivalTime);
queue = new LinkedQueue();
QUEUE APPLICATION:
QUEUE SIMULATION
for (int j=0; j<numServers; j++)
servers[j] = new SimServer(j,randomService.nextInt());
System.out.println("
Number of servers = " + numServers);
System.out.println("
Number of clients = " + numClients);
System.out.println("
Mean service time = " + meanServiceTime);
System.out.println("Mean interarrival time = "
+ meanInterarrivalTime);
for (int j=0; j<numServers; j++)
System.out.println("Mean service time for " + servers[j]
+ " = "+ servers[j].getMeanServiceTime());
}}
QUEUE APPLICATION:
QUEUE SIMULATION
Simulation objects
QUEUE APPLICATION:
QUEUE SIMULATION
Arrivals and Departures
QUEUE APPLICATION:
QUEUE SIMULATION
Output
Number of servers = 3
Number of clients = 20
Mean service time = 30
Mean interarrival time = 5
Mean service time for Server A = 34
Mean service time for Server B = 19
Mean service time for Server C = 78
Client 1 arrived at time 0
The queue has 1 clients
The queue has 0 clients
QUEUE APPLICATION:
QUEUE SIMULATION
Server A started serving Client 1 at time 0 and will finish at time 39
Client 2 arrived at time 6
The queue has 1 clients
The queue has 0 clients
Server B started serving Client 2 at time 6 and will finish at time 28
Client 3 arrived at time 10
The queue has 1 clients
The queue has 0 clients
Server C started serving Client 3 at time 10 and will finish at time 98
