Chap 5

The Queue ADT
Chap. 5
5.1 Queues
QueueA structure in which elements are added
to the rear and removed from the front; a first in,
first out (FIFO) structure
Operations on Queues
Constructor
new: creates an empty queue
Transformers
enqueue: adds an element to the rear of a
queue
dequeue: removesandreturnsthe front
element of the queue
Effectsof
Queue
Operations
Using Queues
A queue of processes that are ready to execute or that
are waiting for a particular event to occur.
A buffer is often implemented as a queue.
We wait in queues to buy pizza, to enter movie theaters,
to drive on a turnpike, and to ride on a roller coaster.
Another important application of the queue data structure
is to help us simulate and analyze such real world
queues.
5.2 Formal Specification

A queue is a first-in first-out" structure, with
primary operations
enqueue: adds an element to the rear of a queue
dequeue: removes and returns the front element of
the queue
A constructor that creates an empty queue
The Queue ADT will be generic, allowing the

class of objects held by the queue to be
specified upon instantiation of the queue.
Completing the Formal

Specification
To complete the formal specification of the
Queue ADT,
Identify and address any exceptional
situations
Determine boundedness
Define the Queue interface or interfaces
Exceptional Situations
dequeue what if the queue is empty?
throw a QueueUnderflowException
plus define an isEmpty method for use by
the application
enqueue what if the queue is full?

throw a QueueOverflowException
plus define an isFull method for use by the
application
Boundedness
Two versions of the Queue ADT
a bounded version
an unbounded version
Three interfaces
QueueInterface: features of a queue not affected
by boundedness
BoundedQueueInterface: features specific to a
bounded queue
UnboundedQueueInterface: features specific to
an unbounded queue
QueueInterface
//--------------------------------------------------------------------------// QueueInterface.java
by Dale/Joyce/Weems
Chapter 5
//
// Interface for a class that implements a queue of Objects.
// A queue is a first-in, first-out structure.
//--------------------------------------------------------------------------package ch05.queues;
public interface QueueInterface<T>
{
T dequeue() throws QueueUnderflowException;
// Throws QueueUnderflowException if this queue is empty,
// otherwise removes front element from this queue and returns it.
boolean isEmpty();
// Returns true if this queue is empty, otherwise returns false.
}
The Remaining Queue Interfaces

TheBoundedQueueInterface
package ch05.queues;
public interface BoundedQueueInterface<T> extends QueueInterface<T>
{
void enqueue(T element) throws QueueOverflowException;
// Throws QueueOverflowException if this queue is full,
// otherwise adds element to the rear of this queue.
boolean isFull();
// Returns true if this queue is full, otherwise returns false.
}
TheUnboundedQueueInterface
public interface UnboundedQueueInterface<T> extends QueueInterface<T>
{
void enqueue(T element);
// Adds element to the rear of this queue.
}
Relationships among Queue

Interfaces and Exception Classes
5.3 Array-Based Implementations

Two array-based implementations of the
Queue ADT
a bounded queue version
an unbounded queue version
Fixed Front Design

After four calls to enqueue
with arguments A, B, C,
and D:
Dequeue the front
element:
Move every element in the
queue up one slot
The dequeue operation is
inefficient, so we do not
use this approach.
Floating
Front
Design
We use this
Approach.
Wrap
Around
with
Floating
Front
Design
The ArrayBndQueue Class

public class ArrayBndQueue<T> implements BoundedQueueInterface<T>
{
protected final int DEFCAP = 100; // default capacity
protected T[] queue;
// array that holds queue elements
protected int numElements = 0;
// number of elements in the queue
protected int front = 0;
// index of front of queue
protected int rear;
// index of rear of queue
public ArrayBndQueue()
{
queue = (T[]) new Object[DEFCAP];
rear = DEFCAP - 1;
}
public ArrayBndQueue(int maxSize)
{
queue = (T[]) new Object[maxSize];
rear = maxSize - 1;
}
The enqueue operation

public void enqueue(T element)
// Throws QueueOverflowException if this queue is full,
// otherwise adds element to the rear of this queue.
{
if (isFull())
throw new QueueOverflowException("Enqueue attempted on a full queue.");
else
{
rear = (rear + 1) % queue.length;
queue[rear] = element;
numElements = numElements + 1;
}
}
The dequeue operation

public T dequeue()
{
if (isEmpty())
throw new QueueUnderflowException(Dequeue attempted on empty queue.);
else
{
T toReturn = queue[front];
queue[front] = null;
front = (front + 1) % queue.length;
numElements = numElements - 1;
return toReturn;
}
}
Remaining Queue Operations

public boolean isEmpty()
// Returns true if this queue is empty, otherwise returns false
{
return (numElements == 0);
}
public boolean isFull()
// Returns true if this queue is full, otherwise returns false.
{
return (numElements == queue.length);
}
The ArrayUnbndQueue Class

The trick is to create a new, larger array, when
needed, and copy the queue into the new array
Since enlarging the array is conceptually a separate
operation from enqueing, we implement it as a
separate enlarge method.
This method instantiates an array with a size equal to
the current capacity plus the original capacity.
Drop the isFull method from the class.

The dequeue and isEmpty methods are
unchanged
The ArrayUnbndQueue Class

public class ArrayUnbndQueue<T> implements UnboundedQueueInterface<T>
{
protected final int DEFCAP = 100; // default capacity
protected T[] queue;
// array that holds queue elements
protected int origCap;
// original capacity
protected int numElements = 0;
// number of elements n the queue
protected int front = 0;
// index of front of queue
protected int rear = -1;
// index of rear of queue
public ArrayUnbndQueue()
{
queue = (T[]) new Object[DEFCAP];
rear = DEFCAP - 1;
origCap = DEFCAP;
}
public ArrayUnbndQueue(int origCap)
{
queue = (T[]) new Object[origCap];
rear = origCap - 1;
this.origCap = origCap;
}
The enlarge operation

private void enlarge()
// Increments the capacity of the queue by an amount
// equal to the original capacity.
{
// create the larger array
T[] larger = (T[]) new Object[queue.length + origCap];
// copy the contents from the smaller array into the larger array
int currSmaller = front;
for (int currLarger = 0; currLarger < numElements; currLarger++)
{
larger[currLarger] = queue[currSmaller];
currSmaller = (currSmaller + 1) % queue.length;
}
// update instance variables
queue = larger;
front = 0;
rear = numElements - 1;
}

{
if (numElements == queue.length)
enlarge();
rear = (rear + 1) % queue.length;
queue[rear] = element;
numElements = numElements + 1;
}
5.6 Linked-Based Implementations

A link-based implementations of the
Unbounded Queue ADT
A second link-based approach
The LLNode class is used for nodes.
The LinkedUnbndQueue Class

import support.LLNode;
public class LinkedUnbndQueue<T> implements UnboundedQueueInterface<T>
{
protected LLNode<T> front;
// reference to the front of this queue
protected LLNode<T> rear;
// reference to the rear of this queue
public LinkedUnbndQueue()
{
front = null;
rear = null;
}
. . .

Enqueue (element)
1. Create a node for the new element
2. Insert the new node at the rear of the queue
3. Update the reference to the rear of the queue
Code for the enqueue method

{
LLNode<T> newNode = new LLNode<T>(element);
if (rear == null)
front = newNode;
else
rear.setLink(newNode);
rear = newNode;
}
The dequeue operation

Dequeue: returns Object
1. Set element to the information in the front node
2. Remove the front node from the queue
if the queue is empty
Set the rear to null
return element
Code for the dequeue method

public T dequeue()
{
if (isEmpty())
throw new QueueUnderflowException("Dequeue attempted on empty queue.");
else
{
T element;
element = front.getInfo();
front = front.getLink();
if (front == null)
rear = null;
return element;
}
}
An Alternative Approach A Circular Linked Queue
Comparing Queue Implementations

Storage Size
Array-based: takes the same amount of memory, no matter how
many array slots are actually used, proportional to current
capacity
Link-based: takes space proportional to actual size of the queue
(but each element requires more space than with array
approach)
Operation efficiency
All operations, for each approach, are O(1)
Except for the Constructors:
Array-based: O(N)
Link-based: O(1)
Special Case: For the ArrayUnbndQueue the size

penalty can be minimized but the enlarge method is
O(N)

Chap 5

Uploaded by

Copyright:

Available Formats

Chap 5

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Chap 5

Uploaded by

Copyright:

Available Formats

The Queue ADT

5.2 Formal Specification

The Queue ADT will be generic, allowing the

Completing the Formal

enqueue what if the queue is full?

The Remaining Queue Interfaces

Relationships among Queue

5.3 Array-Based Implementations

Fixed Front Design

The ArrayBndQueue Class

The enqueue operation

The dequeue operation

Remaining Queue Operations

The ArrayUnbndQueue Class

Drop the isFull method from the class.

The ArrayUnbndQueue Class

The enlarge operation

The enqueue operation

5.6 Linked-Based Implementations

The LinkedUnbndQueue Class

The enqueue operation

Code for the enqueue method

The dequeue operation

Code for the dequeue method

An Alternative Approach A Circular Linked Queue

Comparing Queue Implementations

Special Case: For the ArrayUnbndQueue the size

You might also like