Solution for
Programming Exercise 12.1
THIS PAGE DISCUSSES ONE POSSIBLE SOLUTION to
the following exercise from this on-line
Java textbook.
Exercise 12.1:
In Section 12.2, I mentioned that a
LinkedList can be used as a queue by using the
addLast() and removeFirst() methods to enqueue
and dequeue items. But, if we are going to work with queues,
it's better to have a Queue class. The data for the
queue could still be represented as a LinkedList,
but the LinkedList object would be hidden as a
private instance variable in the Queue object.
Use this idea to write a generic Queue class for
representing queues of Objects. Also write a generic
Stack class that uses either a LinkedList
or an ArrayList to store its data. (Stacks and queues
were introduced in Section 11.3.)
Discussion
This is an easy exercise, but it does illustrate a few
points. A queue needs enqueue, dequeue, and
isEmpty methods.
If the Queue class is written as indicated, then
each of these methods is just one line long. For example, if queue
is the variable of type LinkedList that is being used
to implement the queue, then the dequeue() method is
simply:
public Object dequeue() {
return queue.removeLast();
}
Effectively, the three queue methods are just different names
for methods that are already in the LinkedList class.
So, why define the new class? The point of writing the class is
not so much to make the queue methods available as to hide
all the other methods from the LinkedList class.
A queue is only supposed to support certain operations.
It should be impossible to remove an item from the back of a queue
or to add an item at the front, or to look at any item in the
middle. All these things are possible for a linked list.
However, in the Queue class, the linked list is a private
variable and so is inaccessible from outside the class. The
linked list can be accessed only indirectly, through the methods
of the Queue class, and those methods allow only legitimate
queue operations.
For the Stack class, you have to decide between using
an ArrayList or using a LinkedList. For a queue,
there is a good reason to prefer linked lists over array lists.
In an array list, it's efficient to add and delete elements at
the end of the list but not at the beginning. For a linked list,
adding and deleting is efficient at either end. For a queue,
we are forced to work at both ends since items are added at
one end and are deleted at the other, so a linked list is preferable.
For a stack, where items are added and deleted at the same end,
we can use an array list. In fact, an array list will take up
less space, since a linked list uses extra space to store pointers
between nodes in the list. So, in my solution, I use an ArrayList
to implement a stack
The dequeue() method given above will throw a
NoSuchElementException if the queue is empty when
dequeue is called. This is because queue.removeLast()
throws this exception if the linked list is empty. A
"NoSuchElement" exception seems OK for an empty queue. The
pop operation for a stack is implemented by removing
and returning the last element in an ArrayList with
the command:
return stack.remove(stack.size()-1);
If the ArrayList is empty, this will throw an
IndexOutOfBoundsException. This does not seem like
the right sort of exception for a stack. Arrays use indices;
stacks don't. So, I wrote my pop() method to throw
a different type of exception when the stack is empty:
public Object pop() {
// Return and remove the top item from
// the stack. Throws an EmptyStackException
// if there are no elements on the stack.
if (stack.isEmpty())
throw new EmptyStackException();
return stack.remove(stack.size()-1);
}
EmptyStackException is a predefined exception class in
package java.util. (In case you are wondering: Java
defines this exception because it also defines a standard class
java.util.Stack. This is an older class, not part of
the new generic programming framework, and it is defined in terms
of Vectors rather than ArrayLists.)
The Solution
Implementing a queue as a linked list:
import java.util.LinkedList;
public class Queue {
private LinkedList queue = new LinkedList();
public void enqueue(Object obj) {
// Add an item to back of queue.
queue.addLast(obj);
}
public Object dequeue() {
// Remove the next item from the front of the queue.
// (Note that queue.removeFirst() both removes an
// item from the list, and returns the item that
// was removed.) Throws a NoSuchElementException
// if there are no items on the queue.
return queue.removeFirst();
}
public boolean isEmpty() {
// Test if the queue is empty.
return queue.isEmpty();
}
} // end class Queue
Implementing a stack as an array list:
import java.util.ArrayList;
import java.util.EmptyStackException;
public class Stack {
private ArrayList stack = new ArrayList();
public void push(Object obj) {
// Add obj to the stack.
stack.add(obj);
}
public Object pop() {
// Return and remove the top item from
// the stack. Throws an EmptyStackException
// if there are no elements on the stack.
if (stack.isEmpty())
throw new EmptyStackException();
return stack.remove(stack.size()-1);
}
public boolean isEmpty() {
// Test whether the stack is empty.
return stack.isEmpty();
}
} // end class Stack
[ Exercises
| Chapter Index
| Main Index
]
