Stacks and Queues

1. Introduction

In this set of notes, we will talk about two new abstract data types: Stacks and Queues.

Before we get into those, however, let’s talk a little bit more about Abstract Data Types and a special type of Java class called an interface.

2. Side Note: Abstract Data Types and Interfaces

In a previous set of notes we discussed the concept of an Abstract Data Type (ADT). Recall that we defined it as follows:

An abstract data type (ADT) is a formal description of the behavior of a data type. This means that an ADT is where we define what kind of operations we would like the data type to have.

We then described the ADT for a list and decided that a list should have the following operations:

  1. You should be able to add items to it.
  2. You should be able to remove items from it.
  3. You should be able to access items that are it by specifying their index.
  4. You should be able to determine how many items are in it.

Java has a special kind of class that can be used to define an ADT. It is called an Interface. Here is an example of an interface for a list:

public interface TheList<DataType> {
    // Add an item to the list
    public void add(DataType item);

    // Remove an item from the list
    public boolean remove(DataType item);

    // Retrieve an item from the list by index
    public DataType get(int index);

    // Return the number of items in the list
    public int size();
}

If we were to build a data structure that implements the four methods specified in TheList interface, we could say that the data structure implements TheList ADT.

When creating an interface for an ADT, we only need to specify the prototypes for any methods we want any data structures that implement that ADT to have, we don’t specify any method bodies. That is because an ADT only specifies the high-level operations we want, it doesn’t specify how they should be implemented.

We’ll talk more about interfaces in a later set of notes, but for now the most important take-away is that an interface is a convenient way to specify an ADT.

3. 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.

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

3.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.

4. 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.

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

4.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.

5. 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?