# 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:

```python
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!


```python
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."



<!-- ### Uses for stacks

Because they have so few methods,
it may seem like stacks are not that powerful.
But in fact, stacks are useful for many things.
For instance, they can be used to check for balanced parentheses
in a mathematical expression.  And consider the execution of a Python program.
We have talked about frames that store the names available at a given moment in its execution.
What happens when `f` calls `g`, which calls `h`?
When `h` is over, we go back to `g` and when `g` is over we go back to `f`.
To make this happen, our frames go on a stack!
Typically,
we refer to this as the "call stack", and the frames as "stack frames"


<!-- ## More ADTs

A **Priority Queue** is another ADT and is similar to a Queue,
except that every item has some measure of its "priority".
Items are removed from a Priority Queue according to their priority.
Highest priority items come out first, but if there are ties,
they come out in FIFO order.

Notice that Stack, Queue, and PriorityQueue all share the same operations:
add an item, remove an item, and check if empty.
We can define an even more general ADT called **Container**
that has these operations
and treat Stack, Queue, and PriorityQueue
as children of Container. -->


[^1]: The name "stack" is a deliberate metaphor for a stack of cafeteria trays or books on a table.
[^2]: Imagine if every time you wanted to do `s.split()`
    you had to think through how your string `s` was represented
    and how the `split` method worked.
    It would be a huge distraction from your real task.