{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Build a queue or sliding window\n",
    "\n",
    "**The question.** You need a structure that works at the ends: a FIFO queue, a record of the last N things, a moving average over a window, or an undo history. A `list` is slow at the front and unbounded; `deque` is built for exactly this.\n",
    "\n",
    "Below are the four shapes you'll reach for, each a couple of lines with `deque`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A FIFO queue\n",
    "\n",
    "Add with `append`, take the oldest with `popleft`. This is the standard first-in-first-out queue — and unlike `list.pop(0)`, every operation is fast."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "from collections import deque\n",
    "\n",
    "tasks = deque()\n",
    "tasks.append('email')      # arrivals join the back\n",
    "tasks.append('build')\n",
    "tasks.append('deploy')\n",
    "\n",
    "while tasks:\n",
    "    print('handling:', tasks.popleft())   # leave from the front, oldest first\n",
    "# handling: email / build / deploy"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The last N items (bounded history)\n",
    "\n",
    "A `deque(maxlen=N)` keeps only the most recent N items — each new arrival past the limit pushes the oldest out. No manual trimming."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "from collections import deque\n",
    "\n",
    "recent = deque(maxlen=5)\n",
    "for event in ['login', 'view', 'click', 'view', 'logout', 'login', 'error']:\n",
    "    recent.append(event)\n",
    "\n",
    "print(list(recent))        # ['click', 'view', 'logout', 'login', 'error'] — last 5 only"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A moving average over a window\n",
    "\n",
    "A bounded deque holds the current window; sum it for a rolling statistic. Each step appends one value (dropping the oldest automatically) and recomputes over the window."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "from collections import deque\n",
    "\n",
    "def moving_average(values, window):\n",
    "    win = deque(maxlen=window)\n",
    "    averages = []\n",
    "    for v in values:\n",
    "        win.append(v)\n",
    "        averages.append(sum(win) / len(win))   # len(win) grows then stays at `window`\n",
    "    return averages\n",
    "\n",
    "readings = [10, 20, 30, 40, 50]\n",
    "print(moving_average(readings, 3))\n",
    "# [10.0, 15.0, 20.0, 30.0, 40.0]"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A bounded undo history\n",
    "\n",
    "`append` to record a state, `pop` to undo the most recent — a LIFO stack. Adding `maxlen` caps how far back you can undo, quietly discarding the oldest states so memory stays bounded."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "from collections import deque\n",
    "\n",
    "history = deque(maxlen=3)        # remember at most 3 steps\n",
    "for state in ['', 'H', 'He', 'Hel', 'Hell', 'Hello']:\n",
    "    history.append(state)\n",
    "\n",
    "print(list(history))             # ['Hel', 'Hell', 'Hello'] — older states dropped\n",
    "print('undo to:', history.pop()) # 'Hello' off; previous is now on top\n",
    "print('then:', history[-1])      # 'Hell'"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## In short\n",
    "\n",
    "- FIFO queue: `append` + `popleft` (fast at both ends, unlike a list).\n",
    "- Last N items: `deque(maxlen=N)` trims itself.\n",
    "- Moving window stat: a bounded deque you sum/average each step.\n",
    "- Undo stack: `append`/`pop`, with `maxlen` to bound the history."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}