.. include:: global.rst

=========================
4- Stacks and Queues
=========================

- **Stack (LIFO):** returns the most recently inserted item first.  
- **Queue (FIFO):** returns the oldest inserted item first.  

This difference significantly affects algorithms and efficiency.  
For example:

- **Stacks** form the core of *depth-first search (DFS)*.  
- **Queues** enable *breadth-first search (BFS)*.  

---------------------------------
Stacks
---------------------------------

A **stack** is a *Last-In, First-Out (LIFO)* structure.

- **Push:** Add a new element to the top.  
- **Pop:** Remove the top element.  

Example: pushing `1, 2, 3, 4, 5` → popping returns `5, 4, 3, 2, 1`.

We can implement stacks with either arrays or linked lists.

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Stacks as Arrays
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

A stack can be represented with an array and a variable ``top``:

.. code-block:: text

   Stack {
       Integer: array_size
       Integer: top
       Array of values: array
   }

- ``top = -1`` initially means the stack is empty.

**Push Operation**

.. code-block:: text

   Push(Stack: s, Type: value):
       IF s.top == s.array_size – 1:
           Expand the size of the array
       s.top = s.top + 1
       s.array[s.top] = value

**Pop Operation**

.. code-block:: text

   Pop(Stack: s):
       Type: value = null
       IF s.top > -1:
           value = s.array[s.top]
           s.top = s.top – 1
       return value

.. note::
   Both push and pop run in constant time, except when resizing the array.

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Stacks as Linked Lists
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

A stack can also be represented as a linked list:

.. code-block:: text

   Stack {
       LinkedListNode: head
   }

**Push Operation**

.. code-block:: text

   Push(Stack: s, Type: value):
       LinkedListNode: node = LinkedListNode(value)
       node.next = s.head
       s.head = node

**Pop Operation**

.. code-block:: text

   Pop(Stack: s):
       Type: value = null
       IF s.head != null:
           value = s.head.value
           s.head = s.head.next
       return value

- Linked lists avoid resizing issues but add pointer overhead.  
- Still O(1) for push and pop.

---------------------------------
Queues
---------------------------------

A **queue** is a *First-In, First-Out (FIFO)* structure.

- **Enqueue:** Add a new element at the back.  
- **Dequeue:** Remove the element at the front.  

Queues can be implemented with arrays or linked lists.

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Queues as Arrays
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

A queue needs two indices: ``front`` and ``back``.

- **Enqueue:** Insert at ``back``.  
- **Dequeue:** Remove from ``front``.  

Challenge: empty space accumulates at the front.  
Solutions:

- **Shifting elements** (inefficient).  
- **Wrapping indices** (circular queue).

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Queues as Linked Lists
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

More efficient implementation with head and tail pointers:

.. code-block:: text

   Queue {
       LinkedListNode: front
       LinkedListNode: back
   }

**Enqueue Operation**

.. code-block:: text

   Enqueue(Queue: q, Type: value):
       LinkedListNode: node = LinkedListNode(value)
       IF q.back == null:
           q.front = node
           q.back = node
       ELSE:
           q.back.next = node
           q.back = node

**Dequeue Operation**

.. code-block:: text

   Dequeue(Queue: q):
       IF q.front == null:
           return null
       Type: value = q.front.value
       q.front = q.front.next
       IF q.front == null:
           q.back = null
       return value

Both enqueue and dequeue run in O(1) time.

---------------------------------
The Importance of Order
---------------------------------

- **Stacks (LIFO):** process newest items first.  
  - Example: function calls use stacks.  
- **Queues (FIFO):** process oldest items first.  
  - Example: network requests.  

The order of access **changes algorithm behavior**.

---------------------------------
Depth-First Search (DFS)
---------------------------------

- Uses a **stack** to track unexplored options.  
- Explores *deep* into one path before backtracking.  
- Ideal when focusing on the most recent discovery.

---------------------------------
Breadth-First Search (BFS)
---------------------------------

- Uses a **queue** to track unexplored options.  
- Explores *all neighbors* before going deeper.  
- Ideal when surveying all possibilities evenly.

---------------------------------
Why This Matters
---------------------------------

Both stacks and queues:

- Can be implemented with arrays or linked lists.  
- Support efficient O(1) insertion and removal.  

But:

- **Stacks → newest-first behavior.**  
- **Queues → oldest-first behavior.**  

This ordering difference shapes algorithm performance and behavior.  
Swapping one data structure for another can transform a depth-first process into a breadth-first one.

---------------------------------
Stack Clone
---------------------------------
.. literalinclude:: stack_clone.cpp
   :language: cpp