Stacks and Queues

1. Introduction

Let’s take a moment and talk about two new abstract data types: Stacks and Queues.

2. Stack

A stack is a data structure that is LIFO (Last-In-First-Out). You can picture it as a stack of items where you put new items on the top and also, remove items from the top.

2.1. Interface

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
    public boolean isEmpty();

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

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

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

2.2. Real World Stacks

Here are some real-world examples 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.

3. Queue

A queue is a data structure that is FIFO (First-In-First-Out). You can picture it as a tube. You put items into one end, but you remove them from the other end.

3.1. Interface

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

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

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

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

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

3.2. Real World Queues

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.

4. Questions to Think About

  1. If you implement a stack with an ArrayList, can all the operations be \(O(1)\)? Why or why not?

  2. If you implement a stack with a LinkedList, can all the operations be \(O(1)\)? Why or why not?

  3. If you implement a queue with an ArrayList, can all the operations be \(O(1)\)? Why or why not?

  4. If you implement a queue with a LinkedList, can all the operations be \(O(1)\)? Why or why not?