> ### 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 ]