CMUQ 15-121 Stacks and Queues

Here is a simple interface that could be used to describe a stack:

public interface Stack<DataType> {
    // Return true if the stack is empty, false otherwise
    boolean isEmpty();

    // Put a new item on top of the stack
    void push(DataType value);

    // Remove the top item from the stack and return it
    DataType pop();

    // Return the top item from the stack, but don't remove it from the stack
    DataType peek();
}

Here are some real-world example of stack usage:

1. Stacks of plates at a buffet. (New plates are put on top, and plates are also removed from the top.)
2. “Undo” operations in programs. (You undo the last change made.)
3. RPN calculators.

Here is a simple interface that could be used to describe a queue:

public interface Queue<DataType> {
    // Return true if the queue is empty
    boolean isEmpty();

    // Put a new item onto the end of the queue
    void enqueue(DataType value);

    // Remove an item from the head the queue and return it
    DataType dequeue();

    // Return the item from the head of the queue, but don't remove it from the queue
    DataType peek();
}

Here are some real-world examples of queue usage:

1. The check-out line at the grocery store.
2. The list of students on the whiteboard during a busy office hours session.
3. The way food should be stored and used in your refrigerator.