You Are Asked to Implement Two Abstract Data Types with Following Goals

Assignment 7: OurStack<E> and OurQueue<E>
Due: Thursday, 25-Feb by 19:00 via web cat turnin

You are asked to implement two abstract data types with following goals:

·  Understand the different behavior of insertions and deletions in Stacks and Queues

·  Use Node objects again as a way to store data where nodes are linked by one of its instance variables

·  This will help when we implement other linked structure and the binary tree data structure

·  Gain further practice with linked structures, exceptions, interfaces, generics, and unit testing.

1) Begin a new Eclipse project and obtain these two interfaces that represent two important abstract data types: The Stack and Queue ADTs:

·  interface OurStack<E> in OurStack.java

·  interface OurQueue<E> in OurQueue.java

2) Write a unit test for LinkedStack<E> implements OurStack<E> and use a singly linked structure to implement the LinkedStack<E> collection class. You may only use one external reference named top. The collection class must be named LinkedStack. Ensure pop and peek are throwing exceptions whenever the stack is empty (Rick's test will). Here is one for pop:

@Test(expected = EmptyStackException.class)
public void testPopOnEmpty() {
OurStack<String> s = new LinkedStack<String>();
String top = s.pop();
}

3) Write a unit test for LinkedQueue<E> implements OurQueue<E> and use a singly linked structure to implement the LinkedStack<E> collection class. You must use two external references named front and back. Using the back reference allows the add method to be O(1)—See the section in Chapter 18 on Queues. The collection class must be named LinkedQueue. Ensure pop and peek are throwing exceptions whenever the queue is empty (Rick's test do). Here is the one for peek.

@Test(expected = NoSuchElementException.class)
public void testPeekOnEmpty() {
OurQueue<String> q = new LinkedQueue<String>();
String front = q.peek();
}

4) Turnin your completed Eclipse project to WebCat: LinkedStack and LinkedQueue

Grading Criteria 30pts max

___/ 20 For 100% code coverage and problem coverage on WebCat

___/ 10 LinkedQueue's add method is O(1) by using a reference to the last element all of the time such

that back is either empty or refers to the most recently added element (at the end of the queue).

___/ -15 If you did not use a singly linked structure for LinkedStack

___/ -15 If you did not use a singly linked structure for LinkedQueue

___/ -5 for being 24 to 47.9999 hours late

___/ -10 for being 48 or more hours late