Lab 8 -- A Little Stack Practice

For this very small lab, you will write a program to use a Java API class that implements the Deque interface as a stack.

You will also complete some zyBook exercises during our lab meetings. These must be complete before class on Friday.

You will be assigned a partner to work with on this lab. Only one submission per group is needed.

You will receive an email with the link to follow to set up your GitHub repository stacks-lab-yourgitname for this Lab. One member of the group should follow the link to set up the repository on GitHub, then that person should email the instructor with the other group members' GitHub usernames so they can be granted access. This will allow all members of the group to clone the repository and commit and push changes to the origin on GitHub.

Please answer lab questions in the README.md file in your group's GitHub repository.

Bailey's structure package includes multiple implementations of both stacks and queues. The Java API has class java.util.Stack, but it is no longer recommended for use.

We mentioned briefly in class the idea of a deque, a "double ended queue", which provides the ability to add or remove values efficiently at either end of the structure. The Java API includes an interface java.util.Deque, which is implemented by a few Java API classes, that we can use when we need either a stack or a queue.

The essential operations of a deque are addFirst, addLast, removeFirst, and removeLast. When using the deque as a queue, the methods add and remove correspond to the "enqueue" and "dequeue" operations, and are aliases for the addLast and removeFirst method. The methods when using the deque as a stack are the standard push and pop, which are aliases for addFirst and removeFirst.

For each of the fundamental underlying data structures we used when considering stack and queue implementations, the array list, the singly-linked list, the circular list, and the doubly-linked list, answer the following questions:

Question 1: How you would "orient" the data structure so the four required deque operations addFirst, addLast, removeFirst, and removeLast are most efficient? (4 points)

Question 2: What is the time complexity (Big O) of each of those operations for each of the underlying data structures. Explain each briefly. (16 points)

Practice Program: Write a program in a file PositiveAndNegative.java that uses a stack to keep track of integer values read from the keyboard in this unusual way. If 0 is entered, the input loop terminates. If the stack is empty, the number entered is pushed. The number is also pushed if its sign matches the sign of the number at the top of the stack. However, if the sign does not match, then the number "cancels out" the number of the opposite sign at the top of the stack. Once a 0 is entered, the program either prints out the message "All negatives and positives cancelled" if the stack is empty, or prints the message "Uncancelled values" followed by the contents of the stack otherwise.

Use a stack declared as an instance of the java.util.Deque interface, but construct a java.util.LinkedList. Only use the push, pop and peek operations of the Deque. (15 points)

Your submission requires that all required deliverables are committed and pushed to the master for your repository's origin on GitHub. That's it! If you see everything you intend to submit when you visit your repository's page on GitHub, you're set.

> Feature	Value	Score
Q1: orientations	4
Q2: operation efficiencies	16
`PositiveAndNegative` correctness	15
Total	35