CMUQ 15-121 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
    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();
}

2.2. Real World Stacks

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.

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
    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();
}

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?