{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# deque\n",
    "\n",
    "A Python `list` is brilliant at the *end* — `append` and `pop` are fast — but slow at the *front*. Inserting or removing at index 0 forces every other element to shift along, which costs time proportional to the list's length. When you need a queue, a buffer, or anything that works at both ends, `collections.deque` (\"deck\", a double-ended queue) gives you fast operations at *either* end."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Both ends are fast\n",
    "\n",
    "`deque` adds `appendleft` and `popleft` to the familiar `append` and `pop`. All four are O(1) — constant time regardless of size."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "from collections import deque\n",
    "\n",
    "d = deque([1, 2, 3])\n",
    "d.append(4)         # add on the right\n",
    "d.appendleft(0)     # add on the left\n",
    "print(d)            # deque([0, 1, 2, 3, 4])\n",
    "\n",
    "print(d.pop())      # 4  — remove from the right\n",
    "print(d.popleft())  # 0  — remove from the left\n",
    "print(d)            # deque([1, 2, 3])"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Why not just use a list?\n",
    "\n",
    "For a stack (work at the end only) a `list` is perfect. The difference appears at the *front*: `list.pop(0)` and `list.insert(0, x)` are O(n) because everything shifts; `deque`'s left operations are O(1). Over many front operations that's the difference between linear and quadratic time. Here's the gap on a modest workload — the exact numbers vary, but the ratio is the point."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "from collections import deque\n",
    "import time\n",
    "\n",
    "N = 50_000\n",
    "\n",
    "lst = list(range(N))\n",
    "start = time.perf_counter()\n",
    "while lst:\n",
    "    lst.pop(0)          # O(n) each time -> O(n^2) overall\n",
    "list_time = time.perf_counter() - start\n",
    "\n",
    "dq = deque(range(N))\n",
    "start = time.perf_counter()\n",
    "while dq:\n",
    "    dq.popleft()        # O(1) each time -> O(n) overall\n",
    "deque_time = time.perf_counter() - start\n",
    "\n",
    "print(f'list.pop(0): {list_time:.3f}s   deque.popleft(): {deque_time:.4f}s')\n",
    "print(f'deque was ~{list_time / deque_time:.0f}x faster here')"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A bounded deque with `maxlen`\n",
    "\n",
    "Give a `deque` a `maxlen` and it becomes a fixed-size window: once full, each new item on one end pushes the oldest off the other. This is a ring buffer in one argument — perfect for \"the last N things\"."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "from collections import deque\n",
    "\n",
    "last_three = deque(maxlen=3)\n",
    "for n in range(6):\n",
    "    last_three.append(n)\n",
    "    print(list(last_three))    # window slides: [0] [0,1] [0,1,2] [1,2,3] [2,3,4] [3,4,5]\n",
    "\n",
    "print(last_three)              # deque([3, 4, 5], maxlen=3)"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Using it as a queue or a stack\n",
    "\n",
    "A `deque` is the idiomatic **FIFO queue**: `append` to add, `popleft` to take the oldest. (It also works as a stack with `append`/`pop`, though a list is fine for that.)"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "from collections import deque\n",
    "\n",
    "queue = deque()\n",
    "queue.append('first')\n",
    "queue.append('second')\n",
    "queue.append('third')\n",
    "\n",
    "print(queue.popleft())   # 'first'  — oldest out first (FIFO)\n",
    "print(queue.popleft())   # 'second'\n",
    "print(queue)             # deque(['third'])"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `rotate`, and an `extendleft` surprise\n",
    "\n",
    "`rotate(n)` shifts items around the ends — positive `n` moves them right, negative moves them left. And a gotcha worth knowing: `extendleft` appends items one at a time on the left, so the result ends up **reversed** relative to the input."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "from collections import deque\n",
    "\n",
    "d = deque([1, 2, 3, 4, 5])\n",
    "d.rotate(2)             # last two wrap to the front\n",
    "print(d)                # deque([4, 5, 1, 2, 3])\n",
    "d.rotate(-2)            # and back\n",
    "print(d)                # deque([1, 2, 3, 4, 5])\n",
    "\n",
    "e = deque()\n",
    "e.extendleft([1, 2, 3]) # each is appendleft-ed -> order flips\n",
    "print(e)                # deque([3, 2, 1])"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Recap\n",
    "\n",
    "- `deque` gives O(1) `append`/`appendleft`/`pop`/`popleft` — fast at **both** ends.\n",
    "- A `list` is fine as a stack but slow at the front (`pop(0)` is O(n)); use `deque` for queues and front-work.\n",
    "- `maxlen` makes a fixed-size sliding window / ring buffer that drops the oldest item automatically.\n",
    "- It's the natural FIFO queue: `append` + `popleft`.\n",
    "- `rotate(n)` shifts around the ends; `extendleft` reverses its input.\n",
    "\n",
    "Next: [namedtuple and friends](https://agilearn.co.uk/guides/collections/learn/04-namedtuple-and-friends) — named records, plus `OrderedDict` and `ChainMap`."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}