11-stack-and-queue.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "# Stack and Queue\n",
    "\n",
    "## Agenda\n",
    "\n",
    "- Overview\n",
    "\n",
    "1. Stacks\n",
    "     - ... for delimiter pairing\n",
    "     - ... for postfix expression evaluation\n",
    "     - ... for tracking execution and *backtracking*\n",
    "2. Queues\n",
    "    - ... for tracking execution and *backtracking*\n",
    "    - ... for fair scheduling (aka \"round-robin\" scheduling)\n",
    "    - ... for doling out work\n",
    "3. Run-time analysis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Overview"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "While the list ADT is incredibly useful, both styles of implementation we explored (array-backed and linked) have operations that run in $O(N)$ time, which give them unpredictable runtime behavior.\n",
    "\n",
    "By further restricting the list API, however — in particular, by *isolating points of access to either the front or end of the underlying data* — we can create data structures whose operations are uniformly $O(1)$, and remain very useful in their own right."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## 1. Stacks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **stack** is an ADT which only permit access to one \"end\" of the data collection. We can only append (\"push\") items onto the tail end (a.k.a. the \"top\") of a stack, and only the most recently added item can be removed (\"popped\"). The last item to be pushed onto a stack is therefore the first one to be popped off, which is why we refer to stacks as last-in, first out (LIFO) structures.\n",
    "\n",
    "![](images/stack-adt.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Array-backed Stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# array-backed implementation\n",
    "\n",
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self.data = []\n",
    "        \n",
    "    def push(self, val):\n",
    "        pass\n",
    "\n",
    "    def pop(self):\n",
    "        assert not self.empty()\n",
    "        pass\n",
    "    \n",
    "    def peek(self):\n",
    "        assert not self.empty()\n",
    "        pass\n",
    "\n",
    "    def empty(self):\n",
    "        pass\n",
    "\n",
    "    def __bool__(self):\n",
    "        return not self.empty()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = Stack()\n",
    "for x in range(10):\n",
    "    s.push(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s.peek()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "while s:\n",
    "    print(s.pop())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Singly-linked Stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# linked implementation\n",
    "\n",
    "class Stack:\n",
    "    class Node:\n",
    "        def __init__(self, val, next=None):\n",
    "            self.val = val\n",
    "            self.next  = next\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.top = None\n",
    "\n",
    "    def push(self, val):\n",
    "        pass\n",
    "        \n",
    "    def pop(self):\n",
    "        assert not self.empty()\n",
    "        pass    \n",
    "\n",
    "    def peek(self):\n",
    "        assert not self.empty()\n",
    "        pass\n",
    "        \n",
    "    def empty(self):\n",
    "        pass\n",
    "    \n",
    "    def __bool__(self):\n",
    "        return not self.empty()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = Stack()\n",
    "for x in range(10):\n",
    "    s.push(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s.peek()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "while s:\n",
    "    print(s.pop())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "### ... for delimiter pairing\n",
    "\n",
    "Stacks are used by parsers to decide if expressions which make use of paired delimiters (e.g., `()`, `[]`, `<>`, `<tag></tag>`) are *well-formed*.\n",
    "\n",
    "e.g., are all the parentheses in `'(1 + 2 * (3 - 4 / 5 + 6) - (7 + 8))'` matched up correctly?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def check_parens(expr):\n",
    "    s = Stack()\n",
    "    for c in expr:\n",
    "        pass\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "check_parens('()')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "check_parens('((()))')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "check_parens('()(()()(()))')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "check_parens('(')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "check_parens('())')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "check_parens('(1 + 2 * (3 - 4 / 5 + 6) - (7 + 8))')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "### ... for postfix expression evaluation\n",
    "\n",
    "Arithmetic expressions are commonly written in *infix form* (e.g., \"(1 + 2 * (3 - 4 / 5 + 6) - (7 + 8))\"), as it is more intuitive for humans to read and write. However, to evaluate such expressions implicit rules of precedence and associativity must be known and correctly applied. For this reason, it is not an ideal notation for automated evaluation.\n",
    "\n",
    "*Postfix form* (aka \"reverse polish notation\") allows arithmetic expressions to be specified unambiguously and evaluated without applying any rules of precedence or associativity. The infix expression \"(1 + 2 * (3 - 4 / 5 + 6) - (7 + 8))\" in postfix looks like this: \"1 2 3 4 5 / - 6 + * + 7 8 + -\".\n",
    "\n",
    "Stacks are used to help evaluate postfix arithmetic expressions. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def eval_postfix(expr):\n",
    "    s = Stack()\n",
    "    toks = expr.split()\n",
    "    for t in toks:\n",
    "        pass\n",
    "    return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# (1 + 2) * 5\n",
    "eval_postfix('?')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 1 + 2 * 5\n",
    "eval_postfix('?')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 10 + (1 + 2) * (3 + 2)\n",
    "eval_postfix('?')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note: a stack can also be used to translate infix expressions to postfix!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "### ... for tracking execution and backtracking"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "maze_str = \"\"\"######   \n",
    "              I    #   \n",
    "              # ## #   \n",
    "              # ####   \n",
    "              #    O   \n",
    "              ######\"\"\"\n",
    "\n",
    "def parse_maze(maze_str):\n",
    "    '''Parses a string representing a maze into a 2D array.'''\n",
    "    grid = []\n",
    "    for line in maze_str.split('\\n'):\n",
    "        grid.append(['# IO'.index(c) for c in line.strip()])\n",
    "    return grid\n",
    "\n",
    "def print_maze(grid):\n",
    "    '''Takes a 2D array maze representation and pretty-prints it.\n",
    "       The contents of the 2D maze are in the range 0-5, which are interpreted as:\n",
    "    \n",
    "        0: a wall\n",
    "        1: an unvisited (i.e., not previously traversed) path\n",
    "        2: the maze entrance\n",
    "        3: the maze exit\n",
    "        4: a discovered but unvisited path\n",
    "        5: a visited path\n",
    "    '''\n",
    "    for r in grid:\n",
    "        print(''.join('# IO!+'[c] for c in r))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "parse_maze(maze_str)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print_maze(parse_maze(maze_str))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "maze = parse_maze(maze_str)\n",
    "maze[1][0] = maze[1][1] = 5\n",
    "maze[1][2] = maze[2][1] = 4\n",
    "print_maze(maze)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Move:\n",
    "    '''Represents a move in the maze between orthogonally adjacent locations\n",
    "      `frm` and `to`, which are both (row,col) tuples.'''\n",
    "    def __init__(self, frm, to):\n",
    "        self.frm = frm\n",
    "        self.to  = to\n",
    "        \n",
    "    def __repr__(self):\n",
    "        return f'({self.frm[0]},{self.frm[1]}) -> ({self.to[0]},{self.to[1]})'\n",
    "\n",
    "def moves(maze, loc):\n",
    "    '''Returns all possible moves within a maze from the provide location.'''\n",
    "    moves = [Move(loc, (loc[0]+d[0], loc[1]+d[1]))\n",
    "            for d in ((-1, 0), (1, 0), (0, -1), (0, 1))\n",
    "            if loc[0]+d[0] in range(len(maze)) and \n",
    "               loc[1]+d[1] in range(len(maze[0])) and\n",
    "               maze[loc[0]+d[0]][loc[1]+d[1]] in (1, 2, 3)]\n",
    "    return moves"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "maze = parse_maze(maze_str)\n",
    "print_maze(maze)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "moves(maze, (1, 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "moves(maze, (1, 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "maze[1][0] = 5\n",
    "moves(maze, (1, 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from time import sleep\n",
    "from IPython.display import clear_output\n",
    "\n",
    "def mark(maze, loc):\n",
    "    '''Marks a loc in the maze as having been discovered'''\n",
    "    if maze[loc[0]][loc[1]] != 3:\n",
    "        maze[loc[0]][loc[1]] = 4\n",
    "\n",
    "def visit(maze, loc):\n",
    "    '''Marks a loc in the maze as having been visited'''\n",
    "    maze[loc[0]][loc[1]] = 5    \n",
    "    \n",
    "def display(maze):\n",
    "    '''Prints out the maze after clearing the cell -- useful for animation.'''\n",
    "    clear_output(True)\n",
    "    print_maze(maze)\n",
    "    sleep(0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve_maze(maze, entry):\n",
    "    '''Searches for the exit in a maze starting from the given entry point.\n",
    "    \n",
    "       The algorithm works as follows:\n",
    "       \n",
    "       1. Visit the entry point and save all possible moves from that location.\n",
    "       2. Remove and consider one of the saved moves. If it is the exit, we are done, \n",
    "          otherwise visit the destination and save all possible moves from there.\n",
    "       3. If we run out of saved moves, we can't find an exit.\n",
    "       \n",
    "       When we save a move, we also mark it as \"discovered\" in the maze.\n",
    "       \n",
    "       The data structure used to save moves plays a critical role in how maze\n",
    "       exploration proceeds! \n",
    "    '''\n",
    "    for m in moves(maze, entry):\n",
    "        save_move(m)\n",
    "    visit(maze, entry)\n",
    "    while not out_of_moves():\n",
    "        move = next_move()\n",
    "        if maze[move.to[0]][move.to[1]] == 3:\n",
    "            break\n",
    "        display(maze)\n",
    "        visit(maze, move.to)\n",
    "        for m in moves(maze, move.to):\n",
    "            mark(maze, m.to)\n",
    "            save_move(m)\n",
    "    display(maze)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "move_stack = Stack()\n",
    "\n",
    "def save_move(move):\n",
    "    pass\n",
    "\n",
    "def next_move():\n",
    "    pass\n",
    "\n",
    "def out_of_moves():\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/stack-maze-traversal.jpg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "maze_str = \"\"\"######   \n",
    "              I    #   \n",
    "              # ## #   \n",
    "              # ####   \n",
    "              #    O   \n",
    "              ######\"\"\"\n",
    "solve_maze(parse_maze(maze_str), (1, 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "maze_str = \"\"\"#################\n",
    "              I #       #     #\n",
    "              # ##### # # # # #\n",
    "              #     # # # # # #\n",
    "              # ### ### # # ###\n",
    "              #   #       #   O\n",
    "              #################\"\"\"\n",
    "\n",
    "solve_maze(parse_maze(maze_str), (1, 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "maze_str = \"\"\"#################\n",
    "              I               #\n",
    "              # # # # # # # # #\n",
    "              # # # # # # # # #\n",
    "              # ###############\n",
    "              #               O\n",
    "              #################\"\"\"\n",
    "\n",
    "solve_maze(parse_maze(maze_str), (1, 0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Intuitively, because the stack is a last-in, first-out data structure, it keeps following moves down the most recently discovered path until it either reaches the exit or reaches a dead end. It then picks up from the previously discovered path. We call this type of exploration *depth-first traversal*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## 2. Queues"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **queue** is an ADT which only permits us to append (\"enqueue\") items at the tail end, and remove (\"dequeue\") items from the front. The oldest item still in a queue is therefore the next one to be dequeued, which is why we refer to a queue as a first-in, first-out (FIFO) structure. It is helpful to think of a queue as being the model for a line at a typical supermarket checkout aisle (first customer in, first customer to be checked out).\n",
    "\n",
    "![](images/queue-adt.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Array-backed Queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# array-backed implementation\n",
    "\n",
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self.data = []\n",
    "\n",
    "    def enqueue(self, val):\n",
    "        pass\n",
    "        \n",
    "    def dequeue(self):\n",
    "        assert not self.empty()\n",
    "        pass\n",
    "\n",
    "    def empty(self):\n",
    "        pass\n",
    "        \n",
    "    def __bool__(self):\n",
    "        return not self.empty()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "q = Queue()\n",
    "for x in range(10):\n",
    "    q.enqueue(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "while q:\n",
    "    print(q.dequeue())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Circular Array-backed Queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# circular array-backed implementation (partial)\n",
    "\n",
    "class Queue:\n",
    "    def __init__(self, size):\n",
    "        self.data = [None] * size\n",
    "        self.head = self.tail = -1\n",
    "\n",
    "    def enqueue(self, val):\n",
    "        pass\n",
    "        \n",
    "    def dequeue(self):\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "q = Queue(10)\n",
    "for x in range(6):\n",
    "    q.enqueue(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "q.data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for x in range(5):\n",
    "    print(q.dequeue())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "q.data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for x in range(6, 12):\n",
    "    q.enqueue(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "q.data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Singly-linked Queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# linked implementation\n",
    "\n",
    "class Queue:\n",
    "    class Node:\n",
    "        def __init__(self, val, next=None):\n",
    "            self.val = val\n",
    "            self.next  = next\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.head = self.tail = None\n",
    "\n",
    "    def enqueue(self, val):\n",
    "        pass\n",
    "    \n",
    "    def dequeue(self):\n",
    "        assert not self.empty()\n",
    "        pass\n",
    "    \n",
    "    def empty(self):\n",
    "        pass\n",
    "\n",
    "    def __bool__(self):\n",
    "        return not self.empty()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "q = Queue()\n",
    "for x in range(10):\n",
    "    q.enqueue(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "while q:\n",
    "    print(q.dequeue())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "### ... for tracking execution and backtracking"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "move_queue = Queue()\n",
    "\n",
    "def save_move(move):\n",
    "    pass\n",
    "\n",
    "def next_move():\n",
    "    pass\n",
    "\n",
    "def out_of_moves():\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "maze_str = \"\"\"######   \n",
    "              I    #   \n",
    "              # ## #   \n",
    "              # ####   \n",
    "              #    O   \n",
    "              ######\"\"\"\n",
    "\n",
    "solve_maze(parse_maze(maze_str), (1, 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "maze_str = \"\"\"#################\n",
    "              I #       #     #\n",
    "              # ##### # # # # #\n",
    "              #     # # # # # #\n",
    "              # ### ### # # ###\n",
    "              #   #       #   O\n",
    "              #################\"\"\"\n",
    "\n",
    "solve_maze(parse_maze(maze_str), (1, 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "maze_str = \"\"\"#################\n",
    "              I               #\n",
    "              # # # # # # # # #\n",
    "              # # # # # # # # #\n",
    "              # ###############\n",
    "              #               O\n",
    "              #################\"\"\"\n",
    "\n",
    "solve_maze(parse_maze(maze_str), (1, 0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Intuitively, because the queue is a first-in, first-out -- i.e., *fair* -- data structure, it keeps rotating through all the paths which haven't yet dead-ended, making just one move further down each time. We call this type of exploration *breadth-first traversal*.\n",
    "\n",
    "Are there types of mazes which might be more suitably tackled using one approach over the other (i.e., depth-first vs. breadth-first)? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true,
    "tags": []
   },
   "source": [
    "### ... for fair scheduling (aka \"round-robin\" scheduling)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Queues are often used to help allocate resources in a fair way to different entities that require them. E.g., an operating system may use a queue to allocate processing time to different jobs running on a computer. A **round-robin scheduler** allows each job to run for a fixed *time quantum* on the processor; if it does not complete in that time then it re-enters the queue at the end:\n",
    "\n",
    "![](images/queue-rr.jpg)\n",
    "\n",
    "Here we implement a \"round-robin\" scheduler for permitting different tasks to run for small, fixed periods of time until they complete:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint\n",
    "\n",
    "# create a bunch of jobs with random lengths\n",
    "job_queue = Queue()\n",
    "for i in range(5):\n",
    "    job_queue.enqueue((f'Job {i}', randint(1, 5)))\n",
    "\n",
    "# manually print out the jobs\n",
    "n = job_queue.head\n",
    "while n:\n",
    "    print(n.val)\n",
    "    n = n.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from time import sleep\n",
    "\n",
    "# scheduler loop\n",
    "while job_queue:\n",
    "    job, time_left = job_queue.dequeue()  # grab job at front of queue\n",
    "    print(f'[\\x1b[31mRUNNING\\x1b[0m] {job}')\n",
    "    sleep(1)  # run it for 1 second\n",
    "    time_left -= 1\n",
    "    \n",
    "    # requeue if necessary\n",
    "    if time_left > 0:\n",
    "        print(f'[\\x1b[33mREQUEUE\\x1b[0m] {job} with time remaining = {time_left}')\n",
    "        job_queue.enqueue((job, time_left))\n",
    "    else:\n",
    "        print(f'[\\x1b[32mCOMPLETED\\x1b[0m] {job}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true,
    "tags": []
   },
   "source": [
    "### ... for doling out work"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Queues are also frequently used as a sort of conveyer belt for a pool of homogeneous workers to draw from. \n",
    "\n",
    "![](images/queue-pool.jpg)\n",
    "\n",
    "Here we implement this \"work queue\" pattern and use it to communicate work items to a pool of concurrent threads of execution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from threading import Thread\n",
    "from queue import Queue\n",
    "from time import sleep\n",
    "from random import random\n",
    "\n",
    "\n",
    "class Worker(Thread):\n",
    "    def __init__(self, wid, queue):\n",
    "        super().__init__()\n",
    "        self.wid= wid\n",
    "        self.queue = queue\n",
    "        \n",
    "    def run(self):\n",
    "        print(f'Worker {self.wid} starting up')\n",
    "        while True:\n",
    "            work = self.queue.get()    # retrieve a work item from the queue\n",
    "            if work == 'Stop':\n",
    "                print(f'Worker {self.wid} stopping.')\n",
    "                break\n",
    "            else:\n",
    "                print(f'Worker {self.wid} processing {work}')\n",
    "                sleep(random())        # pretend to do some work (with random duration)\n",
    "                self.queue.task_done() # indicate that we've finished the work item\n",
    "                \n",
    "\n",
    "# create a work queue\n",
    "work_queue = Queue()\n",
    "\n",
    "# create a bunch of workers that monitor the queue for work items\n",
    "for i in range(5):\n",
    "    w = Worker(i, work_queue)\n",
    "    w.start()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add a bunch of work items to the queue\n",
    "for i in range(50):\n",
    "    work_queue.put(i)\n",
    "    \n",
    "# wait for all work items to be processed\n",
    "work_queue.join()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# order all workers to terminate\n",
    "for i in range(5):\n",
    "    work_queue.put('Stop')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Run-time analysis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Stack & Queue implementations:\n",
    "\n",
    "- Insertion (push and enqueue) = $O(1)$\n",
    "- Deletion (pop and dequeue) = $O(1)$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}