Purpose: To review queues and stacks in Java, and to use the built-in Stack class and Queue interface.

The Stack class is a generic class containing these methods:

• public void push(E value) - pushes a new value onto the Stack
• public E pop() - pops the next value off of the stack and returns it; throws EmptyStackExceptionl if stack is empty
• public E peek() - returns the next value on the Stack but does not pop it off of the stack; throws EmptyStackExceptionl if stack is empty
• public boolean empty() - returns true if the stack is empty; false if not empty.

You can declare a stack with a statement such as:

Stack stack1 = new Stack<>();

You can print a stack with the toString() method.

1. Create a driver program that implements and tests the following method:

public static Stack copy(Stack s) - The copy method should non-destructively copy a stack of integers into a new stack, and return that new stack.

Test your method by adding code to the main method that creates a stack, pushes items onto the stack, and then calls your copy method. Still within the main method, print both the original stack and the copied stack to verify that the copy method worked as expected.

Example:

Before the call to copy, stack1 contains 1, 3, 5

Call the copy method: Stack stack2 = copy(stack1);

After call to copy, stack1 contains 1, 3, 5 and stack2 (the copied stack) contains 1, 3, 5

(note that the order of stack2 is the same as stack1)

The Queue interface extends java.util.Collection with the following methods:

public void add(E e) - adds a new value onto the Queue; throws IllegalStateException if no space is currently available

public boolean offer(E e) - adds a new value onto the Queue; returns true if e was added to the queue, returns false if not

public remove() removes and returns the head of the Queue; throws NoSuchElementException if queue is empty

public poll() removes and returns the head of the Queue; returns null if queue is empty

public element() retrieves, but does not remove, the head of the queue; throws NoSuchElementException if queue is empty

You can print a queue with the toString() method.

Declaring a queue: Because the queue is an interface, it may not be instantiated. However, you can create a Queue object and then instantiate it with a LinkedList:

Queue myQueue = new LinkedList<>();

2. In your driver program, implement and test the following method:

public static Queue evenOddMerge(Queue q1, Queue q2)

The evenOddMerge method should destructively merge 2 pre sorted queues into a new larger sorted queue such that all the evens are in order then all of the odds are in order. You may assume that the elements in q1 and q2 are in order then the merge method is called.

In the main method of your driver program, create two queues with several items each, print the queues, then call the merge method. Then print the original and merged queues.

Example:

Before the call to merge, q1 contains 1, 2, 4, 6 and q2 contains 0, 1, 2, 3, 5

Call the merge method: Queue q3 = evenOddMerge(q1, q2);

After the call to merge, q1 and q2 are empty and q3 contains 0, 2, 2, 4, 6, 1, 1, 3, 5