Transcript Queues

Queues
This picture shows 12 trams, each with a carrying capacity of
well over 100 people when 'crush loaded'.
Definition: A queue is a container of objects that are inserted
and removed according to the first-in first-out (FIFO)
principle.
front
rear
rear: Objects are inserted here
……
front: Objects are removed from here
Two fundamental operations:
dequeue
enqueue: Insert an object to the container.
dequeue: Remove an object from the container.
enqueue
The enqueue operation:
Front In the queue the longest
Front In the queue the longest
Front In the queue the longest
Rear
Rear
Rear
The dequeue operation:
Front In the queue the longest
Rear
In the queue the longest
Front
Front In the queue the longest
Rear
Rear
Comparison with a stack:
1. A queue is also a container of objects
2. In a stack, objects are inserted and removed according to
the LIFO principle.
3. In a queue, objects are inserted and removed according to
the FIFO principle.
4. A stack has a top.
5. A queue has a rear and a front.
6. Both stacks and queues have two fundamental operations
for inserting and removing objects.
Examples:
The ride "Indiana Jones and the Temple of the Forbidden Eye".
Queue of Cars at Peace Arch Crossing in Seattle.
Message queues in an operating system
There are times that programs need to communicate with each
other. Unix operating system provides message queue as one
of the mechanisms to facilitate communication.
Send a message to the queue
Program #1
rear
Take a message from
the queue
front
Program #2
Printing in a computer network is organized as print jobs. Prnt
jobs are placed in a queue before they are sent to a printer.
Computer 1
Computer 2
Computer 3
rear
front
Print jobs
Printer
Non-queue examples: a place for parking bicycles is not a
queue.
A collection of records in a file
Records
0
1
2
3
4
5
6
7
A group of numbers
76
5
21
4
100
An array of integers
21
4
5
Is it a queue or not a queue?
100
76
The Queue Abstract Data Type
A queue Q is an abstract data type that supports the following
two fundamental methods:
enqueue(o): Insert object o at the rear of the queue
Input: Object; Output: None.
dequeue( ): Remove and return from the queue the object at the
front; an error occurs if the queue is empty.
Input: None; Output: Object
Other supporting methods:
size(): Return the number of objects in the queue.
Input: None; Output: Integer
isEmpty(): Return a Boolean indicating if the queue is empty.
Input: None; Output: Boolean
front(): Return, but do not remove the front object in the
queue; an error occurs if the queue is empty.
Input: None; Output: Object
This table shows a series of queue operations and their effects.
The queue is empty initially.
Operation
enqueue(5)
enqueue(3)
dequeue()
enqueue(7)
dequeue()
front()
dequeue()
dequeue()
isEmpty()
enqueue(9)
enqueue(7)
size()
enqueue(3)
enqueue(5)
dequeue()
Output
5
3
7
7
“error”
true
2
9
front<-Q <- rear
(5)
(5,3)
(3)
(3,7)
(7)
(7)
()
()
()
(9)
(9,7)
(9,7)
(9,7,3)
(9,7,3,5)
(7,3,5)
5
5
3
3
Operation
enqueue(5)
enqueue(3)
dequeue()
enqueue(7)
dequeue()
front()
dequeue()
dequeue()
isEmpty()
enqueue(9)
enqueue(7)
size()
enqueue(3)
enqueue(5)
dequeue()
Output
5
3
7
7
“error”
true
2
9
front Qrear
(5)
(5,3)
(3)
(3,7)
(7)
(7)
()
()
()
(9)
(9,7)
(9,7)
(9,7,3)
(9,7,3,5)
(7,3,5)
A Queue Interface in Java
public interface Queue {
public void enqueue( Object element );
throws QueueFullException;
public Object dequeue()
throws QueueEmptyException;
public int size();
public boolean isEmpty();
public Object front()
throws QueueEmptyException;
}
When we define an interface, we just indicate that
a class which implements it should provide all the
methods specified in it.
A Simple Array-Based
Implementation
To implement a queue with an array, we need:
1. An array of the size N
2. An index f for the front element
3. An index r for next empty slot or cell
Q: 0 1 2
…
f
r
N-1
As objects are enqueued and dequeued, the queue moves along
in the array.
For example:
f
r
After enqueue:
r
f
After dequeue:
f
r
When the queue reaches the end of the array, it “wraps around”
and the rear of the queue starts from index 0. The figure below
demonstrates the situation.
Q: 0 1 2
N-1
...
r
f
How to calculate r and f when the queue wraps around?
When we increment f or r, we compute the result as
(f + 1) mod N or (r + 1) mod N .
In Java, the modulo operator is % (remainder operator).
For example, if r = N - 1, then (r + 1) = N , therefore,
(r + 1) mod N = 0
The value of r wraps around from N to 0.
Q:
0 1
2
N-1
…
r
f
Initially, we assign r = f = 0, indicating that the queue is empty.
During the process, we may meet a situation where
r = f = i (0 < i < N),
which also indicates the queue is empty.
Now we assume that we enqueue N objects into Q without
dequeueing any of them:
Q:
0 1 2
N-1
…
f
r
Then, we have r = f = 0. But in this case, we have a full queue.
In general, when r = f = i (0 < i < N), it is possible that we have
a full queue.
Problem: r = f may indicate that the queue is empty or that the
queue is full.
Solution: when |r – f| = N – 1, report that the queue is full.
Algorithms:
size():
return the number (N - f + r) mod N
0 1 2
N-1
N+r-1
Q
r
If r  f, then r - f  0
f
N + (r - f )  N
(N - f + r) mod N = - f + r = r - f
If r < f, then f - r > 0
N - f + r = N – (f - r ) < N
(N - f + r) mod N = N - f + r
Algorithms:
isEmpty( ):
return the result of the evaluation of the relationship f = r
f
r
Algorithms:
front( ):
if the queue is empty
throw a QueueEmptyException
else
return element Q[f]
Q: 0 1 2
…
f
r
N-1
enqueue(o):
if queue size is N - 1
throw a QueueFullException
else
store the object to Q[r]
assign (r + 1) mod N to r
(r + 1) mod N
Q: 0 1 2
…
f
r
N-1
dequeue( ):
if queue size is empty
throw a QueueEmptyException
else
save the element Q[f] to a variable temp
make the element Q[f] a null object
assign (f + 1) mod N to f
(f + 1) mod N
Q: 0 1 2
…
f
r
N-1
Memory Allocation in Java
Recall that Java programs use stack for function arguments and
local variables. The Java virtual machine provides another area of
storage for Java programs. Each Java program has a memory
heap. A typical memory space for a Java program is shown here.
Byte code
Stack
Fixed size
Grows
into
higher
memory
Free
memory
Heap
Grows
into
lower
memory
In Java, when a new object is created, the Java virtual machine
allocates a memory block for the object from the heap.
For simplicity, assume that blocks have a fixed size. The Java
virtual machine places all available memory blocks in a queue.
When the Java program needs a memory block, the Java virtual
machine dequeues a memory block from the queue.
When the Java virtual machine determines that a memory block is
no longer in use, it places the block in the queue (garbage
collection).
The memory block queue:
Front
Block 3
Rear
Block 2
Block 4
Block 1
When a new object is created, for example, a new 12-element
Vector object is generated:
Vector items = new Vector( 12 );
A block of Memory - block #3 is allocated for the variable
items as shown below.
Front
Block 2
items
Block 3
Rear
Block 4
Block 1
Data Structure Exercises 4.1