Transcript Queues

Queues
Data structures that wait their turn
queues
1
Queue characteristics
• FIFO: first in, first out
• insertion of items occurs at one end,
removal occurs at the other end
• first item inserted is the first item removed;
second inserted is second removed, third is
third, etc.
queues
2
Queue characteristics
• Structure is very similar to stack, with much
the same considerations -- still subject to
overflow and underflow
• Unlike stack, queue is accessible at both
ends
• Entry and removal still occur at one end -but each operation occurs at a different end
queues
3
Java’s Queue interface
• Unlike the Stack ADT, the Java API doesn’t
provide a full implementation of a generic Queue
• The Queue interface specifies methods for
working with a queue, most of which are listed on
the next slide
• There are several API classes that implement the
interface, but each of these adds methods not
specified by the interface
queues
4
Queue ADT member methods
• Constructor(s)
• Modifiers
– enqueue (insert item at back): add
– dequeue (remove item at front): remove
• Observers
– size
– isEmpty
queues
5
Queue implementations
• The API classes that implement the Queue
interface are designed for more
sophisticated uses than the simple interface
implies
• We can implement a simple queue using
either an array or a linked list as the basic
structure
queues
6
Array implementation
public class ArrayQueue<E> implements Cloneable {
private E[ ] data;
private int manyItems;
private int front;
private int rear;
…
queues
7
Array implementation
public ArrayQueue( ) {
final int INITIAL_CAPACITY = 10;
manyItems = 0;
data = (E[]) new Object[INITIAL_CAPACITY];
}
// Since queue is empty, front and rear values
// don’t matter
queues
8
Array implementation
public ArrayQueue(int initialCapacity)
{
if (initialCapacity < 0)
throw new IllegalArgumentException
("initialCapacity is negative: " + initialCapacity);
manyItems = 0;
data = (E[]) new Object[initialCapacity];
}
queues
9
Array implementation
public ArrayQueue<E> clone( ) {
ArrayQueue<E> answer;
try {
answer = (ArrayQueue<E>) super.clone( );
}
catch (CloneNotSupportedException e) {
throw new RuntimeException
("This class does not implement Cloneable");
}
answer.data = data.clone( );
return answer;
}
queues
10
Enqueue and dequeue – not as
simple as they look!
// first attempt at enqueue
public void add (E item) {
if (manyItems == 0) {
front = 0;
rear = 0;
}
rear++;
data[rear]=item;
manyItems++;
}
queues
11
dequeue (first attempt)
public E remove( ) {
E answer;
if (manyItems == 0)
throw new NoSuchElementException("Queue underflow");
answer = data[front];
front++;
manyItems--;
return answer;
}
queues
12
Problems!!!
• Consider a queue with a capacity of 3:
• As items are added, rear approaches capacity:
• As items are removed, front approaches back:
• Situation: queue isn’t full (manyItems = 0) but
attempt to add an item will
go beyond array boundary
queues
13
Possible solution
• Maintain fixed front of queue:
// dequeue method:
answer = data[0];
for (int x=0; x<rear; x++)
data[x]=data[x+1];
• Increases complexity of algorithm
considerably -- we’ve gone from O(1)
operation in original function to O(N)
queues
14
Better solution: circular array
• Let front continue to float, but add ability
for rear to float as well
• When rear reaches index capacity-1, if
queue isn’t full, rear=0
• In effect, the successor of the last array
index is the first array index -- array can be
thought of as circular
• Can also grow array as necessary
queues
15
Circular queue implementation
• Add helper function nextIndex as private
method of queue class:
private int nextIndex(int i) {
if (++i == data.length)
return 0;
else
return i;
}
• Call method from enqueue and dequeue
queues
16
New enqueue method
public void add(E item) {
if (manyItems == data.length)
ensureCapacity(manyItems*2 + 1);
if (manyItems == 0) {
front = 0;
rear = 0;
}
else
rear = nextIndex(rear);
data[rear] = item;
manyItems++;
queues
}
17
New dequeue method
public E remove( ) {
E answer;
if (manyItems == 0)
throw new NoSuchElementException("Queue underflow");
answer = data[front];
front = nextIndex(front);
manyItems--;
return answer;
}
queues
18
Other methods
• Besides the queue-specific methods (and
clone()), the ArrayQueue implementation
includes a few other methods:
– ensureCapacity
– trimToSize
– getCapacity
queues
19
Invariant for revised queue
• Number of items on queue stored in
variable manyItems
• Items are stored in circular array from
data[front] to data[rear]
• If queue is empty, manyItems == 0 and the
values of front and rear are undefined
queues
20
Queue as linked list
• Implementation using linked list is actually easier
• Ironically, the Java API’s LinkedList class
implements the Queue interface, and will be our
preferred implementation when we look at queue
applications
• Need to decide which end of list is which; easiest
implementation is to have the head pointer point to
the front of the list, and maintain another pointer
to keep track of the back
queues
21
Code for linked list queue
public class LinkedQueue<E> implements Cloneable{
private int manyNodes;
private Node<E> front;
private Node<E> rear;
public LinkedQueue( ) {
front = null;
rear = null;
}
queues
22
Code for linked list queue
public void add(E item) {
if (isEmpty( )) {
front = new Node<E>(item, null);
rear = front;
}
else {
rear.addNodeAfter(item);
rear = rear.getLink( );
}
manyNodes++;
queues
}
23
Code for linked list queue
public LinkedQueue<E> clone( ) {
LinkedQueue<E> answer;
Node<E>[ ] cloneInfo;
try {
answer = (LinkedQueue<E>) super.clone( );
} catch (CloneNotSupportedException e) {
throw new RuntimeException
("This class does not implement Cloneable");
}
queues
24
Clone method continued
cloneInfo = Node.listCopyWithTail(front);
answer.front = cloneInfo[0];
answer.rear = cloneInfo[1];
return answer;
}
queues
25
Code for linked list queue
public boolean isEmpty( ) {
return (manyNodes == 0);
}
public int size( ) {
return manyNodes;
}
queues
26
Code for linked list queue
public E remove( ) {
E answer;
if (manyNodes == 0)
throw new NoSuchElementException("Queue underflow");
answer = front.getData( );
front = front.getLink( );
manyNodes--;
if (manyNodes == 0)
rear = null;
return answer;
}
queues
27
Invariant for linked list
implementation
• The number of items in the queue is stored in the
instance variable manyNodes.
• The items in the queue are stored in a linked list,
with the front of the queue stored at the head node,
and the rear of the queue at the final node.
• For a non-empty queue, the instance variable front
is the head reference of the linked list and the
instance variable rear is the tail reference. For an
empty queue, both front and rear are the null
reference.
queues
28
Priority Queues
• Variation on an ordinary queue -- stores
entries and a priority value for each entry
• Elements are dequeued according to
priority, highest first
• In case of a tie, priority queue reverts to
FIFO behavior
queues2
29
PQ implementation
• One strategy is to create an array of
ordinary queues
– each element in the array would be a queue of
items
– all items in any given queue have equal priority
• Array index indicates priority level
queues2
30
PQ Implementation
public class PQ<E>
{
private ArrayQueue<E>[] queues;
public int highest;
public int total;
public int highCurrent;
public PQ<E> (int h){
highest = h;
queues = ArrayQueue<E>[] new Object[h+1];
total = 0;
highCurrent = 0;
}
queues2
31
PQ implementation
public int size () {
return total;
}
public boolean is_empty() {
return (total == 0);
}
queues2
32
Enqueue function
template <class Item>
void PQ<Item>::PQenqueue(const Item& entry, int priority)
{
assert (priority <= HIGHEST);
// if this is highest priority entry so far, so note:
if (priority > highest_current)
highest_current = priority;
// place entry in queue:
queues[priority].enqueue(entry);
// increment count of total entries:
count++;
}
queues2
33
Dequeue function
template <class Item>
Item PQ<Item>::PQdequeue()
{
assert (PQsize() > 0);
int p = highest_current;
count--;
for(p; p>=0; p--)
if (!queues[p].is_empty())
return queues[p].dequeue();
}
queues2
34