►Lab 5, CSC 2001
Lab 5, CSC 2001
1 Stack
1.1 measurement
2 Queue
9.3

Lab 5, CSC 2001🔗

For this lab you will explore the implementation and use of two additional sequential data structures: the Stack and the Queue.

All classes must come with the standard constructor that accepts values for all fields, and all classes must have an ‘equals‘ method that performs a test of value equality on all fields. (Without these, writing precise test cases is more or less impossible.)

As before, follow the design recipe (data definitions if necessary, signature, purpose statement, header, test cases, template when appropriate, fill in body) to design all methods required by this lab.

For variety, this lab will use Strings, rather than integers, as its values.

1 Stack🔗

You must provide two implementations of the Stack data structure. One implementation will be based on your Linked List implementation and the other will be based on your Array List implementation. Each Stack implementation must define each of the following functions.

Write your linked list implementation in a file named LLStack.java and your array list implementation in a file named AStack.java.

  • empty_stack — this static method takes no arguments and returns an empty stack.

  • push — this void method accepts a String and pushes it onto the stack.

  • pop —a method that removes and returns the top element. If there is no such element, raises an IndexError exception.

  • peek — a method that returns the top element, but does not remove it. If there is no such element, raises an IndexError exception.

  • size — a method that returns the number of elements in the stack.

  • is_empty — a method that returns true when the stack contains no elements.

1.1 measurement🔗

Along with your standard testing, let’s do some timing. Here’s a short piece of Java code that measures the time it takes to run a function ‘f‘:

long startTime = System.nanoTime();
f();
long endTime = System.nanoTime();
 
long duration = ((endTime - startTime) / 1000000);  //divide by 1000000 to get milliseconds.
IO.println("calling f took "+duration+" milliseconds.\n");

Building on this code, write a function in the testing class that accepts a number ‘t‘, and tries to determine the largest number ‘n‘ for which pushing and then popping ‘n‘ elements takes less than ‘t‘ milliseconds. This testing function should start with a list of length 1, and then consider a list that is twice as big, and twice as big again, to examine successive elements of the exponential sequence 2^n. When it finds that a computation has taken more than ‘t‘ milliseconds, it should report the prior value of the sequence 2^n.

Use this function to determine the number of elements that can be pushed and then popped in less than 1/10 of a second, 2/10 of a second, 3/10 of a second, and so forth up to 1 second.

You may notice some "jitter"; running the function twice with the same input may produce different outputs.

Plot your outputs by hand on a piece of paper, with ‘pushes and pops‘ on the x axis and seconds on the y axis. Does it look linear?

2 Queue🔗

You must provide two implementations of the Queue data structure. One of the implementations must be implemented as a circular buffer, as discussed below. The other should use a pair of linked lists, one representing the front of the queue, and the other the reversed tail of the queue, as discussed in class.

Your queue implementations should be able to handle millions of elements. This will require reversing your linked list using a loop, rather that with recursion; Java is not very good at recursion.

Each Queue implementation must define each of the following functions.

Write your circular buffer implementation in a file named AQueue.java. Write your list-based implementation in a file called LLQueue.java.

  • empty_queue — a static method that returns an empty queue. To simplify the circular queue, we do not require resizing of an array-based queue. This mens that this method should accept a single argument for an array-based queue, indicating the (fixed) size of the queue. For the linked-list-based queue, no argument should be accepted.

  • enqueue — a void method that accepts a string and adds it to the end of the queue.

  • dequeue — a method that removes and returns the element at the front of the queue.If there is no such element, raises an IndexError exception.

  • peek — a method that returns the element at the front of the queue, without removing it. If there is no such element,raises an IndexError exception.

  • size — a method that returns a count of the number of elements currently in the queue.

  • is_empty — a method that returns true when the queue contains no elements.