{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "title",
   "metadata": {},
   "source": [
    "# Stacks & Queues\n",
    "\n",
    "Stacks and queues are linear abstract data types. Both store ordered collections, but they remove items in different orders.\n",
    "\n",
    "```text\n",
    "Outline\n",
    "\n",
    "Stacks\n",
    "  o Last-in, first-out behavior\n",
    "  o Python list implementation\n",
    "Queues\n",
    "  o First-in, first-out behavior\n",
    "  o collections.deque implementation\n",
    "Stack or Queue?\n",
    "Summary\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "stacks",
   "metadata": {},
   "source": [
    "## Stacks\n",
    "\n",
    "A **stack** is a last-in, first-out structure. The newest item is the first item removed.\n",
    "\n",
    "Common stack operations:\n",
    "\n",
    "- `push(item)`: add an item to the top\n",
    "- `pop()`: remove and return the top item\n",
    "- `peek()`: look at the top item without removing it\n",
    "- `is_empty()`: check whether the stack has no items\n",
    "\n",
    "Stacks are useful for undo history, browser back buttons, expression evaluation, recursion, and depth-first traversal."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "stack-code",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self._items = []\n",
    "\n",
    "    def push(self, item):\n",
    "        self._items.append(item)\n",
    "\n",
    "    def pop(self):\n",
    "        if self.is_empty():\n",
    "            raise IndexError(\"pop from empty stack\")\n",
    "        return self._items.pop()\n",
    "\n",
    "    def peek(self):\n",
    "        if self.is_empty():\n",
    "            raise IndexError(\"peek from empty stack\")\n",
    "        return self._items[-1]\n",
    "\n",
    "    def is_empty(self):\n",
    "        return len(self._items) == 0\n",
    "\n",
    "\n",
    "history = Stack()\n",
    "history.push(\"open file\")\n",
    "history.push(\"edit line 10\")\n",
    "history.push(\"rename variable\")\n",
    "\n",
    "print(history.pop())\n",
    "print(history.pop())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "exercise-stack",
   "metadata": {
    "tags": [
     "thebe-interactive"
    ]
   },
   "outputs": [],
   "source": [
    "### Exercise: Reverse Words with a Stack\n",
    "# Write a function named reverse_words(sentence) that uses a Stack\n",
    "# to reverse the order of words in a sentence.\n",
    "#\n",
    "# Example: reverse_words(\"data structures matter\") should return\n",
    "# \"matter structures data\".\n",
    "### Your code starts here.\n",
    "\n",
    "\n",
    "\n",
    "### Your code ends here."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "solution-stack",
   "metadata": {
    "tags": [
     "hide-input"
    ]
   },
   "outputs": [],
   "source": [
    "### Solution\n",
    "def reverse_words(sentence):\n",
    "    stack = Stack()\n",
    "    for word in sentence.split():\n",
    "        stack.push(word)\n",
    "\n",
    "    reversed_words = []\n",
    "    while not stack.is_empty():\n",
    "        reversed_words.append(stack.pop())\n",
    "\n",
    "    return \" \".join(reversed_words)\n",
    "\n",
    "\n",
    "print(reverse_words(\"data structures matter\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "queues",
   "metadata": {},
   "source": [
    "## Queues\n",
    "\n",
    "A **queue** is a first-in, first-out structure. The oldest item is the first item removed.\n",
    "\n",
    "Common queue operations:\n",
    "\n",
    "- `enqueue(item)`: add an item to the back\n",
    "- `dequeue()`: remove and return the front item\n",
    "- `is_empty()`: check whether the queue has no items\n",
    "\n",
    "In Python, `collections.deque` is usually the right implementation for a queue."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "queue-code",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "\n",
    "\n",
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self._items = deque()\n",
    "\n",
    "    def enqueue(self, item):\n",
    "        self._items.append(item)\n",
    "\n",
    "    def dequeue(self):\n",
    "        if self.is_empty():\n",
    "            raise IndexError(\"dequeue from empty queue\")\n",
    "        return self._items.popleft()\n",
    "\n",
    "    def is_empty(self):\n",
    "        return len(self._items) == 0\n",
    "\n",
    "\n",
    "line = Queue()\n",
    "line.enqueue(\"alice\")\n",
    "line.enqueue(\"bob\")\n",
    "line.enqueue(\"charlie\")\n",
    "\n",
    "print(line.dequeue())\n",
    "print(line.dequeue())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "exercise-queue",
   "metadata": {
    "tags": [
     "thebe-interactive"
    ]
   },
   "outputs": [],
   "source": [
    "### Exercise: Serve a Customer Line\n",
    "# Create a Queue. Add apple, banana, and cherry as customer names.\n",
    "# Serve two customers by calling dequeue twice and printing the result.\n",
    "### Your code starts here.\n",
    "\n",
    "\n",
    "\n",
    "### Your code ends here."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "solution-queue",
   "metadata": {
    "tags": [
     "hide-input"
    ]
   },
   "outputs": [],
   "source": [
    "### Solution\n",
    "customers = Queue()\n",
    "customers.enqueue(\"apple\")\n",
    "customers.enqueue(\"banana\")\n",
    "customers.enqueue(\"cherry\")\n",
    "\n",
    "print(customers.dequeue())\n",
    "print(customers.dequeue())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "compare",
   "metadata": {},
   "source": [
    "## Stack or Queue?\n",
    "\n",
    "| Problem | Better structure | Reason |\n",
    "| --- | --- | --- |\n",
    "| Undo edits | Stack | Undo the newest action first |\n",
    "| Print jobs | Queue | Print the oldest waiting job first |\n",
    "| Browser back button | Stack | Return to the most recent page |\n",
    "| Help desk tickets | Queue | Serve earlier requests first |\n",
    "| Depth-first search | Stack | Explore one path deeply before backing up |\n",
    "| Breadth-first search | Queue | Explore nearby nodes first |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "exercise-compare",
   "metadata": {
    "tags": [
     "thebe-interactive"
    ]
   },
   "outputs": [],
   "source": [
    "### Exercise: Pick the Structure\n",
    "# For each workflow, write \"stack\" or \"queue\" in the dictionary value.\n",
    "# 1. Undo history\n",
    "# 2. Waiting room check-in\n",
    "# 3. Browser back button\n",
    "### Your code starts here.\n",
    "\n",
    "choices = {\n",
    "    \"undo history\": \"\",\n",
    "    \"waiting room\": \"\",\n",
    "    \"browser back\": \"\",\n",
    "}\n",
    "\n",
    "print(choices)\n",
    "\n",
    "### Your code ends here."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "solution-compare",
   "metadata": {
    "tags": [
     "hide-input"
    ]
   },
   "outputs": [],
   "source": [
    "### Solution\n",
    "choices = {\n",
    "    \"undo history\": \"stack\",\n",
    "    \"waiting room\": \"queue\",\n",
    "    \"browser back\": \"stack\",\n",
    "}\n",
    "\n",
    "print(choices)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "summary",
   "metadata": {},
   "source": [
    "## Summary\n",
    "\n",
    "Stacks and queues are simple but powerful. Use a stack when the newest item should be handled first. Use a queue when the oldest waiting item should be handled first."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}