4.2 Stacks and Queues

4.2 Stacks and Queues#

To round out our study of ADTs, we’ll learn about two new ADTs this week: the Stack and the Queue. Both of these ADTs store a collection of items, and support operations to add an item and remove an item. However, unlike a Set or Multiset, in which the client code may specify which item to remove, Stacks and Queues remove and return their items in a fixed order—client code is allowed no choice. This might seem very restrictive and simplistic, but you’ll soon learn how the power of these ADTs lies in their simplicity. Once you learn about them, you’ll start seeing them everywhere, and be able to effectively communicate about these ADTs to any other computer scientist.

The Stack ADT#

The Stack ADT is very simple. A stack contains zero or more items. When you add an item, it goes “on the top” of the stack (we call this “pushing” onto the stack) and when you remove an item, it is removed from the top also (we call this “popping” from the stack).[1] The net effect is that the first item removed from the stack is the last item that was added. We call this Last-In-First-Out (or LIFO) behaviour. To summarize:

  • Stack

    • Data: a collection of items

    • Operations: determine whether the stack is empty, add an item (push), remove the most recently-added item (pop)

In code:

class Stack:
    """A last-in-first-out (LIFO) stack of items.

    Stores data in last-in, first-out order. When removing an item from the
    stack, the most recently-added item is the one that is removed.
    """
    def __init__(self) -> None:
        """Initialize a new empty stack."""

    def is_empty(self) -> bool:
        """Return whether this stack contains no items.

        >>> s = Stack()
        >>> s.is_empty()
        True
        >>> s.push('hello')
        >>> s.is_empty()
        False
        """

    def push(self, item: Any) -> None:
        """Add a new element to the top of this stack.
        """

    def pop(self) -> Any:
        """Remove and return the element at the top of this stack.

        >>> s = Stack()
        >>> s.push('hello')
        >>> s.push('goodbye')
        >>> s.pop()
        'goodbye'
        """

At this point in CSC148, you may immediately picture implementing this with a Python list. You may be wondering “which end of the list is the top of the stack?” But this is irrelevant when you are using the ADT. You are much better off thinking of a pile of objects stacked up. When you are a client of a stack, you don’t need to know the implementation. The reduction in your cognitive load that the abstraction brings is very important. Without it, complex, modern software would not be possible.

The Queue ADT#

Another important ADT is a Queue. Like a stack, a queue contains zero or more items, but items come out of a queue in the order in which they entered. In other words, a queue exhibits First-in-First-Out (FIFO) behaviour. The lineup at the corner store is—one hopes—a queue. We call adding an item to a queue an enqueue operation, and the removal of an item a dequeue operation.

  • Queue

    • Data: a collection of items

    • Operations: determine whether the queue is empty, add an item (enqueue), remove the least recently-added item (dequeue)

List-based implementation of the Stack ADT#

In this section, we’ll now implement the Stack ADT using a built-in Python data structure: the list. Note that here, we’ve chosen to use the end of the list to represent the top of the stack. This wasn’t the only viable option!

class Stack:
    """A last-in-first-out (LIFO) stack of items.

    Stores data in first-in, last-out order. When removing an item from the
    stack, the most recently-added item is the one that is removed.

    Private Instance Attributes:
    - _items:
        The items stored in this stack. The end of the list represents
        the top of the stack.
    """
    _items: list

    def __init__(self) -> None:
        """Initialize a new empty stack.
        """
        self._items = []

    def is_empty(self) -> bool:
        """Return whether this stack contains no items.

        >>> s = Stack()
        >>> s.is_empty()
        True
        >>> s.push('hello')
        >>> s.is_empty()
        False
        """
        return self._items == []

    def push(self, item: Any) -> None:
        """Add a new element to the top of this stack.
        """
        self._items.append(item)

    def pop(self) -> Any:
        """Remove and return the element at the top of this stack.

        >>> s = Stack()
        >>> s.push('hello')
        >>> s.push('goodbye')
        >>> s.pop()
        'goodbye'
        """
        return self._items.pop()

We’ll leave a list-based Queue implementation as an exercise for this week’s lab.

Abstraction is critical#

Abstraction is one of the most powerful concepts in computer science. An ADT is an abstraction so general it transcends any specific programming language. This kind of abstraction has profound implications.

Looking at the class from the outside, a programmer writing client code needs to understand only its public interface. This frees them to focus on what they want to do with the class and ignore everything about how it is implemented.[2] If a client creates a Stack object in their code, they know there are exactly three operations that can be performed on it: checking whether it’s empty, pushing an item onto it, and popping an item from it. This reduces cognitive load for the programmer dramatically. Modern, complex software would be impossible otherwise.

Looking at the class from the inside, the implementer has complete freedom to change implementation details with no effect on client code. For example, the software can be redesigned to be more efficient, or more elegant (and maintainable). The entire implementation can even change, and every program that uses the class will still work exactly the same as before. We call this “plug-out, plug-in compatibility.”