Objectives

• To illustrate the concept of data abstraaction.
• To implement a Queue Abstract Data Type (ADT).
• To implement a Deque ADT.

Introduction

• DLNode.java, a complete implementation of the DLNode class.
• DList.java, a complete implementation of the DList class.
• DListStack.java, a complete implementation of the DListStack class.
• Stack.java, the Stack interface.
• StackEmptyException.java, an implementation of the StackEmptyException class.

You are provided a complete implementation (from Goodrich and Tamassia) of a doubly linked list (DList) of (DLNode). Before getting started, study the example of the DListStack class, an implementation of the Stack ADT based on the DList.

The relevant methods of the DList and DLNode classes are shown in the following UML diagrams:

The DListStack class uses a DList to provide an implementation of a Stack:

Implementing a Stack from a DList is simple. The Stack's push() method is the DList's addFirst() method. The Stack's top() method is the DList's getFirst() method. Thus the stack can be implemented by using a DList to store the stack's elements and calling the appropriate DList methods for push(), pop() and so forth.

Here's an example:

    private DList dl;
    
    public DListStack() {
        dl = new DList();  // A DList stores the stack's elements
    }
    public void push (Object element) {
        dl.addFirst(new DLNode(element, null,null));
    }

See the downloaded implementation for further details. Pay special attention to the pop() method. And note how the Stack is tested in the main() method.

Part I Problem

• Queue.java
• QueueEmptyException.java

Make sure you design a main() method that thoroughly tests your implementation. A good problem to test a Queue on would be to store the characters of the string in the queue and then remove them all. They should come out in the same order they went in.

Part II

A Deque (pronounced deck) is a double-ended queue. It allows insertions and deletions from both ends of a list. Develop a complete implementation of a DListDeque class that implements the Deque interface. A deque is defined abstractly as follows:

• addFirst(e) -- Insert element e at the beginning.
• addLast(e) -- Insert element e at the end.
• removeFirst(): Object -- Remove and return the first element; error if empty.
• removeLast(): Object -- Remove and return the last element; error if empty.
• Ancillary methods
• getFirst(): Object -- Return the first element; error if empty.
• getLast(): Object -- Return the last element; error if empty.
• size(): int -- Return the number of elements.
• isEmpty(): boolean -- Return true iff the deque is empty.

You can download Deque interface and exception classes here:

• Deque.java
• DequeEmptyException.java

The Railroad Yard Problem. Make sure you design a main() method that thoroughly tests your implementation and demonstrates its correctness. Here's a test case: Insert the numbers 1 through 8 into the deque in that order. Then use deque operations to print the numbers in the following sequence: 1, 2, 3, 5, 4, 6, 7, 8, ending with an empty deque. This might be called the railroad yard problem. Imagine train cars coming into a railroad yard in numerical order, 1..8. Your job is to send them down the track in some random order. The railroad yard has a physical version of a deque that you can use to rearrange cars.

Step-wise Refinement

Documentation