CSC-207 Data Structures
Chapter 7 Queues
We have already studied the Stack
data structure. We saw that it was a last-in-first-out (LIFO) type of data
structure. In other words when you remove something from a stack, you will
remove the most recent item that you placed on the stack (i.e thje one you
placed on the stack last).
A
queue is almost the opposite. It is a first-in-first-out (FIFO) data structure.
Here when you remove an item from a queue, you will remove the oldest item. It
is very similar to a check-out line in a grocery store. The first customer to
get into the line will be the first customer to get checked out and leave.
A
stack only had one data that pointed us into the stack, the “top”, because all
we were interested in was placing something on the top, or removing something
from the top.
A
queue must have two pieces of data, a “front” and a “rear” or “back”. For
example, if we are to place items in an array in a queue fashion, then we need
to know where the front of the queue is in order to remove an item and we need
to know where the back of the queue is to add an item.
|
|
|
|
|
|
0 1 2 3 4
Front Back
A
stack had a few simple operations, the primary two being “push” and “pop”. A queue
also has only a few simple operations, the primary ones being “enqueue” (place
something into the queue, and “dequeue” (remove something from the queue).
As
before we can build a “queue interface”:
public
interface QueueInterface {
public boolean isEmpty();
// Determines whether a queue is empty.
// Precondition: None.
// Postcondition: Returns true if the queue
is empty;
// otherwise returns false.
public void enqueue(Object newItem) throws
QueueException;
// Adds an item at the back of a queue.
// Precondition: newItem is the item to be
inserted.
// Postcondition: If the operation was
successful, newItem
// is at the back of the queue. Some
implementations
// may throw QueueException if newItem
cannot be added
// to the queue.
public Object dequeue() throws
QueueException;
// Retrieves and removes the front of a
queue.
// Precondition: None.
// Postcondition: If the queue is not empty,
the item
// that was added to the queue earliest is
returned and
// the item is removed. If the queue is
empty, the
// operation is impossible and
QueueException is thrown.
public void dequeueAll();
// Removes all items of a queue.
// Precondition: None.
// Postcondition: The queue is empty.
public Object peek() throws QueueException;
// Retrieves the item at the front of a
queue.
// Precondition: None.
// Postcondition: If the queue is not empty,
the item
// that was added to the queue earliest is
returned.
// If the queue is empty, the operation is
impossible
// and QueueException is thrown.
} // end QueueInterface
Here is some code that may be used if you had a queue named “myQ”:
myQ.createQueue();
myQ.enqueue(task1);
myQ.enqueue(task2);
myQ.enqueue(task3);
//computer
is ready
execute(myQ.dequeue());
execute(myQ.dequeue());
//
oops another request
myQ.enqueue(task4);
//computer
is ready
execute(myQ.dequeue());
execute(myQ.dequeue());
Assuming that the above code
is handling the execution of tasks inside of an operating system, in what order
will the tasks get executed?
One of the nice things about queues is that they can
be easily implemented with a linked list structure.
Remember that we said that we need two data items,
front and back. Well, with a linked list and a little thought, we can actually
do it with only one.
Consider the figure in your textbook:
firstNode lastNode
If we make the list circular where the “7” node
points back to the “2” node, then we only need the “lastNode” pointer. The
“firstNode” can always be gotten to by referencing “lastNode.getNext( )”.
Your textbook goes through the processes of a)
inserting an item into a nonempty queue, b) inserting an item into an empty
queue, and deleting an item from a queue that has more than one node. There is
also code that goes along with these operations. We will go over this in class,
step-by-step.
Now we are ready to see the complete implementation of the queue interface using these lists. We will go over all of the methods very carefully:
public
class QueueReferenceBased
implements
QueueInterface {
private Node lastNode;
public QueueReferenceBased() {
lastNode = null;
} //
end default constructor
// queue operations:
public boolean isEmpty() {
return lastNode == null;
} //
end isEmpty
public void dequeueAll() {
lastNode = null;
} //
end dequeueAll
public void enqueue(Object newItem) {
Node newNode = new Node(newItem);
// insert the new node
if (isEmpty()) {
// insertion into empty queue
newNode.setNext(newNode);
}
else {
// insertion into nonempty queue
newNode.setNext(lastNode.getNext());
lastNode.setNext(newNode);
}
// end if
lastNode = newNode; // new node is at back
} //
end enqueue
public Object dequeue() throws
QueueException {
if (!isEmpty()) {
// queue is not empty; remove front
Node firstNode = lastNode.getNext();
if (firstNode == lastNode) { // special
case?
lastNode = null; // yes, one node in queue
}
else {
lastNode.setNext(firstNode.getNext());
}
// end if
return firstNode.getItem();
}
else {
throw new
QueueException("QueueException on dequeue:"
+ "queue
empty");
}
// end if
} //
end dequeue
public Object peek() throws QueueException {
if (!isEmpty()) {
// queue is not empty; retrieve front
Node firstNode = lastNode.getNext();
return firstNode.getItem();
}
else {
throw new
QueueException("QueueException on peek:"
+ "queue empty");
}
// end if
} //
end peek
}
// end QueueReferenceBased
Here is a cute little program to test to see if we can enqueue some items into a queue.
public
class QueueTest {
public static void main(String[] args) {
QueueReferenceBased aQueue =
new
QueueReferenceBased();
for (int i = 0; i < 9; i++) {
aQueue.enqueue(new Integer(i));
}
// end for
} //
end main
} // QueueTest
An in class exercise: How would you write a program, similar to the above program that would remove each item from the queue, one at a time and print them?
I will include our old friend, the Node class, for
reference, just in case we need it:
public class Node {
private Object item;
private Node next;
public Node(Object newItem) {
item = newItem;
next = null;
} // end constructor
public Node(Object newItem, Node nextNode) {
item = newItem;
next = nextNode;
} // end constructor
public void setItem(Object newItem) {
item = newItem;
} // end setItem
public Object getItem() {
return item;
} // end getItem
As you may remember, when we
studied stacks, we started by using an array to implement them. It seemed the
easiest way. But with queues, arrays are not the easy way to go; this is the
reason we chose to implement them as a list structure first. In the next
lecture we will consider how to make an array look like a queue and the special
problems that go with it.
If you have some time, you may want to start to look at problems 3 and 4 on page 326 to get some practice, but I will not assign them just yet. I want you to complete all of the other pending assignments first!!
An Array-Based Implementation
As we said before, the
linked list approach is probably the best way to implement a queue. It requires
only one pointer and there is virtually no limit to how many items can be
placed in the queue. However, many computer scientists do not like the idea of
dynamic memory allocation, especially when memory is scarce in some systems,
and they prefer an array-based implementation of a queue. We saw that
implementing a stack by using an array was fairly straightforward. Is it the
same for a queue? Let’s see.
Consider a simple array of 10 elements. It is to be
a queue. It will hold the names of patients that need treatment at a medical
center. The patients arrive one by one and are processed as whenever help is
available. The first patient to arrive is “Joe”. It is natural to place Joe in
the first location of the array. At that point he is both in the front and in
the back of the queue. Then “Sue” comes along. She is placed in the next
position and becomes the new “back” of the queue.
|
Joe |
Sue |
|
|
|
|
|
|
|
|
0 1 2
3 4 5 6 7 8 9
Front = 0
Back = 1
Other patients arrive and depart in a random fashion
and we keep moving them down the “track” in the array. Eventually we may have
something that looks like this
|
|
|
|
|
|
|
Tim |
Mary |
Sam |
|
Front = 6
Back = 8
Now Deb arrives, Tim gets processed and then Carl arrives. What happens? Deb and Tim are no problem, but when Carl arrives there is seemingly no place to put him in the queue. The queue seems full (we have reached the end) even though there are perhaps some empty spaces in the beginning indices (where Joe and Sue used to be).
What is the answer? The answer is to treat the array
as a circular array so that when Carl arrives, he is placed in the first
location of the array.
|
Carl |
|
|
|
|
|
|
Mary |
Sam |
Deb |
Front = 7
Back = 0
The problem now is to keep track of the Front and Back item pointers and to be able to determine when the queue is full and when the queue is empty.
If we begin properly, then inserting and deleting an
item from the queue is fairly easy. We simply have to use “modulo” arithmetic.
Suppose that Deb is in the queue at position 9. Carl comes in. His position is
(back + 1) % queue_size = ( 9 + 1 ) %
10 = 0.
In general insertion is done as follows:
back
= (back + 1) % MAX-QUEUE;
items[back] = newItem;
++count;
Notice that we are also using a count.
Deletion from the queue is done as follows:
front = (front + 1) % MAX_QUEUE;
--count;
Now the only question is how to the variables “front” and “back” correctly so that everything works out:
front = 0;
back = MAX_QUEUE –1;
count = 0;
Here is the complete implementation for the array-based queue:
public
class QueueArrayBased implements QueueInterface {
private final int MAX_QUEUE = 50; // maximum
size of queue
private Object[] items;
private int front, back, count;
public QueueArrayBased() {
items = new Object[MAX_QUEUE];
front = 0;
back = MAX_QUEUE-1;
count = 0;
} //
end default constructor
// queue operations:
public boolean isEmpty() {
return count == 0;
} //
end isEmpty
public boolean isFull() {
return count == MAX_QUEUE;
} //
end isFull
public void enqueue(Object newItem) {
if (!isFull()) {
back = (back+1) % (MAX_QUEUE);
items[back] = newItem;
++count;
}
else {
throw new QueueException("QueueException
on enqueue: "
+ "Queue
full");
}
// end if
} //
end enqueue
public Object dequeue() throws
QueueException {
if (!isEmpty()) {
// queue is not empty; remove front
Object queueFront = items[front];
front = (front+1) % (MAX_QUEUE);
--count;
return queueFront;
}
else {
throw new
QueueException("QueueException on dequeue: "+
"Queue
empty");
}
// end if
} //
end dequeue
public void dequeueAll() {
items = new Object[MAX_QUEUE];
front = 0;
back = MAX_QUEUE-1;
count = 0;
} //
end dequeueAll
public Object peek() throws QueueException {
if (!isEmpty()) {
// queue is not empty; retrieve front
return items[front];
}
else {
throw new QueueException("Queue
exception on peek: " +
"Queue
empty");
}
// end if
} //
end peek
}
// end QueueArrayBased
public class
QueueException extends RuntimeException {
public QueueException(String s) {
super(s);
} // end constructor
} // end QueueException
Your assignment is
to do problems 2, 3 and 4 on page 326 under Self-Test Exercises and problems 4
and 5 on page 327 under Exercises.