PA6 Stacks and Queues

Overview

The purpose of this assignment is to give you practice implementing data structures, compar- ing different implementations of data structures, and determining the runtime complexity of certain methods of data structures.

The assignment consists of a written part answering questions and a coding part. It is suggested to finish the coding part first, since the written questions rely on the code that you have written. Make sure to start early.

Assignment

Code

Your job is to implement four different classes. Two of the classes represent the Stack ADT (abstract data type) and the other two represent the Queue ADT. All four ADTs will hold only int data type (we are not using generics in this assignment). As mentioned in class, many data structures are built on either arrays or linked structures. You will implement both types for both the Stack and the Queue and then compare the implementations. We will not specify all of the methods you must implement for these classes in this spec. Instead, we will provide interfaces with the starter code that you must implement. In addition to the methods from the interfaces, you must also override the toString and equals methods. Lastly, you must implement copy constructors for all of your classes.

• ArrayStack.java - implement the StackInterface with a Stack backed by an array.
• ListStack.java - implement the StackInterface with a Stack backed by a linked list.
• ArrayQueue.java - implement the QueueInterface with a Queue backed by an array.
• ListQueue.java - implement the QueueInterface with a Queue backed by a linked list.

You are not allowed to use any other data structures other than an array for the two Array classes and a linked list for the two list classes.

Remember that in order to implement an interface all you have to type is:

public class ArrayStack implements StackInterface {
...
}

You will then get a compile error because your ArrayStack will have unimplemented methods from the interface. Eclipse should provide a 'quick fix when you hover over the red line indicating the error. This quick fix can provide all of the method headers which can save some time typing. The quick fix is Add unimplemented methods.

Remember that after you have implemented the interfaces you must also override the toString and equals methods, and write copy constructors for all of your classes.

The toString method should return a string of the format: "{ 0, 1, 2, 3, 4, 5, }. Note that even though '5 is the last element, it is still followed by a comma and a space to make things easier for you all. In the above example, 0 would be the bottom of the stack and 5 would be the top. If it were representing a queue, 0 would be the next element to be dequeued (the front of the queue) and 5 would be the element most recently enqueued (the back of the queue).

Two stacks are equal if their sizes and all of their elements are equal. Two queues are equal if their sizes and all of their elements are equal.

Clarifications to Common Questions

As (has been or will be) mentioned in class and the spec (in bold), you are not allowed to use any other data structures. That means you cannot use the Java LinkedList class or the Java ArrayList class or any other data structure. To put it simply, just implement the classes very similarly to how we did in lecture.

At the very top of this spec, we listed the files that you need to turn in. You should not turn in any other files. This means you can't create a Node class in a separate file. Instead, make the Node class as a nested class as shown in lecture. If you believe you need any other classes, these must also be nested/inner classes.

Queue Interface

public interface QueueInterface {

/**
* Add an element to the back of the queue
*/
public void enqueue(int value);

/**
* Remove and return the front element in the queue.
*
* If the user attempt to dequeue from an empty queue, ignore the request.
*/
public int dequeue();

/**
* Return but do not remove the front element of the queue.
*/
public int peek();

/**
* Return true if the queue has no elements.
*/
public boolean isEmpty();

/**
* Return the number of elements in the queue.
*/
public int size();

/**
* Remove all elements from the queue.
*/
public void clear();
}

Stack Interface

public interface StackInterface {

/**
* Add an element to the top of the stack.
*/
public void push(int value);

/**
* Remove and return the top element in the stack.
*/
public int pop();

/**
* Return the top element in the stack.
*/
public int peek();

/**
* Return true if the stack has no element.
*/
public boolean isEmpty();

/**
* Returns the number of elements in the stack.
*/
public int size();

/**
* Remove all elements in the stack.
*/
public void clear();
}