Stacks and Queues

Introduction

Your goal in this lab is to solve several problems in which you must process items in a certain order. Stacks and queues will help you manage these items.

Your solutions should make use of the following Stack and Queue interfaces and implementations:

• Stack.java
• Queue.java
• ArrayListStack.java
• LinkedListQueue.java

You can put your solution code in the following file:

• Exercises.java

(Java provides a Queue interface and several implementations that add extra behaviors. Their enqueue operation is named offer, and their dequeue operation is named poll. Java also provides a Stack class, but the documentation discourages its use.)

Exercises

In the Exercises class, implement the static methods described below.

Odd First

Method oddFirst accepts a Queue of Integer objects as a parameter. It rearranges the elements of the given queue such that all the odd numbers appear before the even numbers. But the odds remain in their same relative order, as do the evens. For example, if the queue originally contains the sequence 7 10 4 3 5 6, then afterward it contains 7 3 5 10 4 6. Do not return a new queue. Modify the parameter queue.

The provided LinkedListQueue implementation only supports dequeueing and enqueueing at the ends. Do not add any new operations, and do not use any types besides Integer and LinkedListQueue in your solution.

Wander

The method wander accepts a String containing 0 or more lines of movement commands, like this:

up 5
save
right 2
restore
left 3

This method moves from (0, 0) to the location described by the commands and returns the location as a java.awt.Point. For the example, this sequence of operations is performed:

Move up 5 units to (0, 5).
Remember (0, 5).
Move right 2 units to (2, 5).
Recall (0, 5), discarding the current location.
Move left 3 units to (-3, 5).

You may encounter an arbitrary number of save commands. Assume that each restore command was preceded at some point by a corresponding save. Each restore refers to the most recent non-restored save.

Use a Scanner to access the commands and integers. You do not need to consider the line formatting of the input. Just use the next and nextInt methods to consume the next token. These will skip over whitespace, including line breaks.

Text blocks, or multi-line string literals, appeared in Java 15. You can use them to test this method:

Point destination = wander("""
  down 2
  save
  right 7
  restore
""");
System.out.println(destination);     // prints (0, -2)

Postfix Expression Evaluation

The method evaluatePostfix must accept a string containing an arithmetic expression in postfix format. Each token in the expression will be separated by a single space. You may access the tokens by using a Scanner or by using the split method of the String class. The method must return an integer represented the value of the expression. You may assume that the expression will be well-formed. Here is an example invocation along with the expected output.

    int value = evaluatePostfix("3 5 2 * + 6 -");
    System.out.println(value);  // prints 7

If you are using the split method, you can convert a string to an integer using the Integer.parseInt method. That method will throw a NumberFormatException if the string cannot be converted.

Submission

Once you are confident that your solutions are correct, submit Exercises.java through Gradescope.

Acknowledgments

Portions of this lab were developed by Chris Johnson.