Ch22-Queues.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Queues\n",
    "<a href=\"https://colab.research.google.com/github/rambasnet/FDSPython-Notebooks/blob/master/Ch24-Queues.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>\n",
    "\n",
    "http://openbookproject.net/thinkcs/python/english3e/queues.html\n",
    "- another container adapter or ADT, which is typically a first-in-first-out (FIFO) data structure\n",
    "- mimics real-world queue/line of people waiting for something\n",
    "- rule that determines who goes next is called the queuing policy\n",
    "- the most general queuing policy is priority queuing, in which each item/person is assigned a priority and the element with highest priority goes first, regardless of the order of the arrival\n",
    "- built-in alternative - deque: https://docs.python.org/3/library/collections.html#collections.deque"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Queue ADT\n",
    "- can be implemented using built-in list or linked list as the container to hold the elements\n",
    "- queque ADT is defined by the following operations:\n",
    "    - \\__init__ : initialize the queue\n",
    "    - insert : add a new item to the queue\n",
    "    - remove : remove and return the first element that was added\n",
    "    - is_empty : check whether the queue is empty"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linked Queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.cargo = data\n",
    "        self.next = None\n",
    "    \n",
    "    def __str__(self):\n",
    "        return \"{}\".format(self.cargo)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self.length = 0\n",
    "        self.head = None\n",
    "        self.tail = None\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self.length == 0\n",
    "    \n",
    "    def insert(self, data):\n",
    "        node = Node(data)\n",
    "        if not self.head: # empty queue\n",
    "            self.head = self.tail = node\n",
    "        else:\n",
    "            # add new node as the last node\n",
    "            self.tail.next = node\n",
    "            self.tail = node\n",
    "        self.length += 1\n",
    "    \n",
    "    def remove(self):\n",
    "        data = self.head.cargo\n",
    "        # make the head point to 2nd element\n",
    "        self.head = self.head.next\n",
    "        self.length -= 1\n",
    "        # update tail if the queue becomes empty after removing the first node\n",
    "        if self.length == 0:\n",
    "            self.tail = None\n",
    "            \n",
    "        return data\n",
    "            \n",
    "    def __len__(self):\n",
    "        return self.length"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### quick test of Queue ADT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "q = Queue()\n",
    "q.insert(1)\n",
    "q.insert(2)\n",
    "q.insert('a')\n",
    "assert q.remove() == 1\n",
    "assert len(q) == 2\n",
    "q.insert(100)\n",
    "assert q.remove() == 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Priority Queue ADT\n",
    "- better built-in alternative: heapq- https://docs.python.org/3/library/heapq.html\n",
    "- Priority Queue ADT implementation\n",
    "- use the same methods/interfaces as Queue with only difference in remove function; where the item removed is the highest priority\n",
    "    - item removed is not necessarily the first one that was added; rather an item in the queue with highest priority\n",
    "    - e.g., if the items in the queue have names, we might choose item in alphabetical order\n",
    "    - if they're bowling scores, we might go from highest to lowest, but if they're golf scores, we would go from lowest to highest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "class PriorityQueue:\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self.items == []\n",
    "    \n",
    "    def insert(self, data):\n",
    "        self.items.append(data)\n",
    "    \n",
    "    def remove(self):\n",
    "        maxi = 0\n",
    "        for i in range(1, len(self.items)):\n",
    "            if self.items[i] > self.items[maxi]:\n",
    "                maxi = i\n",
    "        item = self.items[maxi]\n",
    "        del self.items[maxi]\n",
    "        return item\n",
    "            \n",
    "    def __len__(self):\n",
    "        return len(self.items)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### test priority queue ADT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "q = PriorityQueue()\n",
    "for num in [11, 12, 14, 13]:\n",
    "    q.insert(num)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "14\n",
      "13\n",
      "12\n",
      "11\n"
     ]
    }
   ],
   "source": [
    "while not q.is_empty():\n",
    "    print(q.remove())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Golfer class\n",
    "- keeps track of the names and scores of golfers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Golfer:\n",
    "    def __init__(self, name, score):\n",
    "        self.name = name\n",
    "        self.score = score\n",
    "    \n",
    "    def __str__(self):\n",
    "        return \"{0:16}: {1}\".format(self.name, self.score)\n",
    "    \n",
    "    # lowest score gets highest priority\n",
    "    def __gt__(self, other):\n",
    "        return self.score < other.score # lower score has the higher priority"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Hal Sutton      : 20\n"
     ]
    }
   ],
   "source": [
    "tiger = Golfer('Tigher Woods', 40)\n",
    "phil = Golfer('Phil Mickelson', 30)\n",
    "hal = Golfer('Hal Sutton', 20)\n",
    "pq = PriorityQueue()\n",
    "pq.insert(tiger)\n",
    "pq.insert(phil)\n",
    "pq.insert(hal)\n",
    "print(pq.remove())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Phil Mickelson  : 30\n",
      "Tigher Woods    : 40\n"
     ]
    }
   ],
   "source": [
    "while not pq.is_empty():\n",
    "    print(pq.remove())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## exercises"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Write an implementation of the Queue ADT using Python list. Compare the performance of this implementation to the ImprovedQueue for a range of queue lengths.\n",
    "- Write an implementation of the Priority Queue ADT using linked list. You should keep the list sorted so that removal is a constant time operation. Compare the performance of this implementation with the Python list implementation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Kattis problems that can be solved using Queue\n",
    "1. Solve kattis problem Bank Queue: https://open.kattis.com/problems/bank\n",
    "- Server - https://open.kattis.com/problems/server\n",
    "- Ferry Loading III - https://open.kattis.com/problems/ferryloading3\n",
    "- Foosball Dynasty - https://open.kattis.com/problems/foosball\n",
    "- Disastrous Downtime: https://open.kattis.com/problems/downtime"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}