array-list.ipynb

balanced-bsts-demo.ipynb

binary-search-trees.ipynb

bst-ds-demo.ipynb

hashtable-demo.ipynb

iterators-demo.ipynb

lang-intro-part1.ipynb

lang-intro-part2.ipynb

lang-intro-part3.ipynb

linked-list-demo.ipynb

linked-structures-demo.ipynb

on-recursion-demo.ipynb

priority-queues-demo.ipynb

searching-sorting-timing.ipynb

stacks-and-queues-demo.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Stacks and Queues\n",
    "\n",
    "## Agenda\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 apportioning work\n",
    "3. Run-time analysis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Overview"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "While the list data structure is incredibly useful, both implementations we explored (array-backed and linked) have operations that run in $O(N)$ time, which make them non-ideal for use with large, growing collections of data.\n",
    "\n",
    "By further restricting the list API, however — in particular, by *isolating points of access to either the front or end of the data set* — we can create data structures whose operations are all $O(1)$, and remain very useful in their own right."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Stacks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Stacks are linear data structures 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."
   ]
  },
  {
   "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": [
    "while s:\n",
    "    print(s.pop())"
   ]
  },
  {
   "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": [
    "while s:\n",
    "    print(s.pop())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ... for delimiter pairing\n",
    "\n",
    "Stacks are used by parsers to decide if delimited expressions are well-formed.\n",
    "\n",
    "e.g., `'(1 + 2 * (3 - (4 / 2) + 5) - (6 + 1))'`"
   ]
  },
  {
   "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 / 2) + 5) - (6 + 1))')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ... for postfix expression (aka \"reverse polish notation\") evaluation\n",
    "\n",
    "Stacks are used for the evaluation of postfix arithmetic expressions (which can be easily converted back and forth between the more common infix expressions). \n",
    "\n",
    "e.g., `'(1 + 2) * 5'` $\\rightarrow$ `'1 2 + 5 *'`"
   ]
  },
  {
   "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": [
    "eval_postfix('1 2 + 5 *')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "eval_postfix('1 2 5 * +')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ((1 + 2) * (3 + 2)) * 10\n",
    "eval_postfix('1 2 + 3 2 + * 10 *')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "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 '({},{}) -> ({},{})'.format(self.frm[0], self.frm[1],\n",
    "                                           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": "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": {},
   "source": [
    "## 2. Queues"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Queues are linear data structures wherein we are only permitted to append (\"enqueue\") items onto the rear, 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)."
   ]
  },
  {
   "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": "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": "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": {},
   "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": {},
   "source": [
    "### ... for fair scheduling (aka \"round-robin\" scheduling)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Queues are often used to either carry out or simulate the fair allocation of resources. 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",
    "from time import sleep\n",
    "\n",
    "task_queue = Queue()\n",
    "for i in range(3):\n",
    "    task_queue.enqueue(('Job {}'.format(i), randint(3, 6)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = task_queue.head\n",
    "while n:\n",
    "    print(n.val)\n",
    "    n = n.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "while not task_queue.empty():\n",
    "    job, time_left = task_queue.dequeue()\n",
    "    print('Running', job)\n",
    "    sleep(1)\n",
    "    time_left -= 1\n",
    "    if time_left > 0:\n",
    "        print('Re-queueuing', job, 'with remaining time =', time_left)\n",
    "        task_queue.enqueue((job, time_left))\n",
    "    else:\n",
    "        print('*', job, 'done')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ... for doling out work"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Queues are also frequently used as a sort of conveyer belt for multiple worker functions to draw from. Here we implement a \"work queue\" pattern used by multiple threads of execution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from threading import Thread, Lock\n",
    "from time import sleep\n",
    "import random\n",
    "\n",
    "lock = Lock()\n",
    "def worker_fn(cid, q):\n",
    "    while True:\n",
    "        try:\n",
    "            with lock:\n",
    "                work = q.dequeue()\n",
    "        except: # queue is empty\n",
    "            sleep(1)\n",
    "            continue\n",
    "        if work == 'Stop':\n",
    "            print('Consumer', cid, 'stopping.')\n",
    "            break\n",
    "        else:\n",
    "            print('Consumer', cid, 'processing', work)\n",
    "            sleep(random.random())\n",
    "\n",
    "work_queue = Queue()\n",
    "for i in range(5):\n",
    "    Thread(target=worker_fn, args=(i, work_queue)).start()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import threading\n",
    "threading.active_count()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(10):\n",
    "    with lock:\n",
    "        work_queue.enqueue(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(5):\n",
    "    with lock:\n",
    "        work_queue.enqueue('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",
   "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.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}