Queue/Queue.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Author: OMKAR PATHAK"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What is a Queue?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* A queue is a data structure used for storing data (similar to Linked Lists and stacks). In queue, the order in which dula arrives is important.\n",
    "* A queue is an ordered list in which insertions are done at one end (rear) and deletions are done at other end (front). The first element to be inserted is the first one to be deleted. Hence, it is called First in First out (FIFO) or Last in Last out (LILO) list.\n",
    "* For example, our labs have 30 computers networked with a single printer. When students want to print, their print tasks “get in line” with all the other printing tasks that are waiting. The first task in is the next to be completed."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Applications of Queue:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*  When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk Scheduling.\n",
    "* When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes. Examples include IO Buffers, pipes, file IO, etc.\n",
    "* Keyboard: As we type, sometimes keystrokes get ahead of the characters that appear on the screen. This is due to the computer doing other work at that moment. The keystrokes are being placed in a queue-like buffer so that they can eventually be displayed on the screen in the proper order."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 6 7 8 9\n",
      "Queue Size: 10\n",
      "0 1 2 3 4 5 6 7 8\n",
      "Queue Size: 9\n"
     ]
    }
   ],
   "source": [
    "class Queue(object):\n",
    "    def __init__(self, limit = 10):\n",
    "        self.queue = []\n",
    "        self.front = None\n",
    "        self.rear = None\n",
    "        self.limit = limit\n",
    "        self.size = 0\n",
    "     \n",
    "    def __str__(self):\n",
    "        return ' '.join([str(i) for i in self.queue])\n",
    "    \n",
    "    # to check if queue is empty\n",
    "    def isEmpty(self):\n",
    "        return self.size <= 0\n",
    "    \n",
    "    # to add an element from the rear end of the queue\n",
    "    def enqueue(self, data):\n",
    "        if self.size >= self.limit:\n",
    "            return -1          # queue overflow\n",
    "        else:\n",
    "            self.queue.append(data)\n",
    "        \n",
    "        # assign the rear as size of the queue and front as 0\n",
    "        if self.front is None:\n",
    "            self.front = self.rear = 0\n",
    "        else:\n",
    "            self.rear = self.size\n",
    "            \n",
    "        self.size += 1\n",
    "    \n",
    "    # to pop an element from the front end of the queue\n",
    "    def dequeue(self):\n",
    "        if self.isEmpty():\n",
    "            return -1          # queue underflow\n",
    "        else:\n",
    "            self.queue.pop()\n",
    "            self.size -= 1\n",
    "            if self.size == 0:\n",
    "                self.front = self.rear = 0\n",
    "            else:\n",
    "                self.rear = self.size - 1\n",
    "    \n",
    "    def getSize(self):\n",
    "        return self.size\n",
    "\n",
    "myQueue = Queue()\n",
    "for i in range(10):\n",
    "    myQueue.enqueue(i)\n",
    "print(myQueue)\n",
    "print('Queue Size:',myQueue.getSize())\n",
    "myQueue.dequeue()\n",
    "print(myQueue)\n",
    "print('Queue Size:',myQueue.getSize())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Time Complexities:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* enqueue(): O(1)\n",
    "* dequeue(): O(1)\n",
    "* isEmpty(): O(1)\n",
    "* getSize(): O(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Limitations:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* The maximum size of the queue must be defined prior to the execution and cannot be changed"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Extensions of Queue:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Deque (Double ended queue): Supports insert and delete at both the ends (front as well as rear) of the queue.\n",
    "* Circular Queue: A queue in which last position is connected back to front\n",
    "* Priority Queue: Elements are added based on their priorities (higher priority elements are popped first)"
   ]
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}