Home Stacks and queues

Allowable methods

You may only use the push, pop, peek, size, and isEmpty methods of stacks. You may only use the add, remove, peek, size, and isEmpty methods of queues.

Furthermore, you may not iterate over stacks and queues by using foreach loops or iterators.

In this class, we want to make sure that you understand the idea of how to work with stacks and queues. As a result, we have restricted you from working with any extra methods Java provides that deviate from the standard expected behavior of stacks and queues.

For example, you may not iterate over Java Stacks or Queues in the following way:

for (String item : myQueue) {
    // ...
}

If you want to iterate over a queue, you must do so by using one of the methods listed above. This means it would be acceptable to write code like the following:

// Note that queue is empty afterwards
while (!myQueue.isEmpty()) {
    String item = myQueue.remove();
    // ...
}

// Alternative approach that preserves the queue
for (int i = 0; i < myQueue.size(); i++) {
    String item = myQueue.remove();
    // ...
    myQueue.add(item);
}

Do not destroy client data structures

When a client gives you a data structure of some kind, you should always make sure that the data structure remains unmodified once your method is finished, unless the spec explicitly tells you otherwise.

When a client gives you a data structure, they are almost always making the implicit assumption that all you are planning on doing is reading from the data structure.

If you suddenly go out and have your method modify the data structure you were given, then you run the risk of catching the client by surprise.

This tends to happen especially when working with stacks and queues. Suppose we were given a queue of integers, and needed to keep track of all even numbers in an internal field. Naively, we might try doing this:

public void copyEvens(Queue input) {
    while (!input.isEmpty()) {
        this.internalField.add(input.remove());
    }
}

The problem is then that after the client runs this method, the queue they gave to you will be empty, which is very surprising.

So then, you should either:

Document the unexpected destructiveness as a precondition
Make sure your method leaves the queue unchanged

Here is an example of how we can do the latter:

public void copyEvens(Queue input) {
    int size = input.size();
    for (int i = 0; i < size; i++) {
        int item = input.remove()
        this.internalField.add(item);
        input.add(item);
    }
}

Preserving stacks is harder and often requires an extra data structure.