> For the complete documentation index, see [llms.txt](https://notes.danfitz.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://notes.danfitz.com/other/algo-expert/h-stacks-and-queues.md).

# Stacks And Queues

## What is a Stack?

An example of a **stack** is a stack of books on a table. When you want to **add** a book to the stack, you add it to the top (because putting it in the middle or bottom is too hard). Then when you want to **remove** a book from the stack, you similarly remove it from the top. This means the same book you added gets removed first.

This is known as the **last in, first out** (LIFO) principle and is the key aspect of stacks.

### Spacetime complexity of stack operations

In a lot of cases, stacks use **dynamic arrays under the hood**, where you add to and remove from the stack via the *end* of the array.

As a result, **push** (insertion) and **pop** (removal) operations for stacks are always `O(1)`, since the end of the array doesn't require re-indexing/shifting memory slots for every item.

Like dynamic arrays, here are some other operations' spacetime complexities:

* Traversal and search are `O(n)` time and `O(1)` space since it's about traversing the input size
* Initialization is `O(n)` spacetime

**Note**: Linked lists also work under the hood for stacks.

## What is a Queue?

An example of a **queue** is a line of people waiting to buy tickets at a movie theatre. When someone wants to **add** themselves to the line, they go to the back of the line. Then when the theatre wants to **remove** someone from the line, they sell a ticket to someone at the front of the line.

This is known as the **first in, first out** (FIFO) principle and is the key aspect of queues.

### Spacetime complexity of queue operations

In a lot of cases, queues use **linked lists under the hood**, where you add to the *head* of the linked list and remove from the *tail* of the linked list.

As a result, **enqueue** (insertion) and **dequeue** (removal) operations for queues are always `O(1)`, since it's a trivial operation to just replace the head or remove the tail and switch up some pointers.

Like linked lists, here are some other operations' spacetime complexities:

* Traversal and search are `O(n)` time and `O(1)` space since it's about traversing the input size
* Initialization is `O(n)` spacetime

**Note**: We don't typically use dynamic arrays for queues because insertion at the beginning isn't a constant spacetime operation. However, since many languages don't have linked lists built in, it's reasonable in interviews to *pretend* to treat them as efficient data structures for queues. *Just make sure to note that to your interviewer*.

## Peek

Stacks and queues typically have a `peek` operation implemented. It's basically `O(1)` spacetime like pop and dequeue except you only *look* at the element to be removed. You don't actually remove it.

## More Complex Stacks and Queues

* `MinStack` and `MaxStack` keep track of the smallest and largest element in it respectively
* Priority queues keep track of high-priority elements