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 ]