14. Queues.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "5d513d8d",
   "metadata": {},
   "source": [
    "### Queue"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4a7657d9",
   "metadata": {},
   "source": [
    "- Linear data structure \n",
    "- Queues follows the First In, First Out (FIFO) order."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3948737d",
   "metadata": {},
   "source": [
    "Ex : Scheduling of tasks by computer's CPU is an example where the queue data structure is useful."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "65aa156c",
   "metadata": {},
   "source": [
    "### Stacks vs Queues"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cf35c5b2",
   "metadata": {},
   "source": [
    "A stack follows the ‘Last In, First Out’ order, and so, elements are inserted and removed from the same end of the data structure. On the other hand, a queue follows the ‘First In, First Out’ order, and so, elements are inserted from one end and removed from the other."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7d9cbfcf",
   "metadata": {},
   "source": [
    "Operations on a queue:\n",
    "- Enqueue(object element): It inserts an element to the rear of the queue.\n",
    "- Dequeue(): It removes an element from the front of a queue.\n",
    "- isEmpty(): It returns true if a queue is empty; otherwise false.\n",
    "- size() : It returns the size of the queue."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eaa42fc5",
   "metadata": {},
   "source": [
    "### Enqueue\n",
    "\n",
    "- Enqueue adds an element at the rear of the queue.\n",
    "- The front of the queue moves ahead when element is inserted\n",
    "\n",
    "- Add 5 to the queue , rear=0 and front=0 , Queue |5|\n",
    "- Add 8 to the queue, rear=0 and front=1, Queue |8|5|\n",
    "- Add 6 to the queue, rear=0 and front=2, Queue |6|8|5| , element at rear(index 0) = 6 and element at the front(index=2) = 5"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2f111efa",
   "metadata": {},
   "source": [
    "### Dequeue\n",
    "\n",
    "- Dequeue deletes an element from the front end of the queue.\n",
    "\n",
    "- Queue |6|8|5| , element at rear(index 0) = 6 and element at the front(index=2) = 5\n",
    "- Dequeue, element 5 removed , |6|8| , element at rear=6 and element at front = 8\n",
    "- Dequeue, element 8 removed , |6| , element at rear=6 and element at front = 6"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f6a5fcc4",
   "metadata": {},
   "source": [
    "### Implementation of Queue Operations"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e09d7e94",
   "metadata": {},
   "source": [
    "The most common ways are:\n",
    "\n",
    "- Python lists\n",
    "- Inbuilt Python classes - queue.Queue and collections.deque\n",
    "- Linked lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 168,
   "id": "c8168177",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self.items=[]\n",
    "    \n",
    "    def enqueue(self, item):\n",
    "        self.items.insert(0,item)\n",
    "        \n",
    "    def dequeue(self):\n",
    "        if self.isEmpty():\n",
    "            return -1\n",
    "        self.items.pop()\n",
    "        \n",
    "    def isEmpty(self):\n",
    "        return self.items==[]\n",
    "                    \n",
    "    def size(self):\n",
    "        return len(self.items)\n",
    "    \n",
    "    def peek(self):\n",
    "        return self.items[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "id": "a9238811",
   "metadata": {},
   "outputs": [],
   "source": [
    "# create object of class Queue\n",
    "q= Queue()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "id": "17fe173d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# print items of the Queue\n",
    "q.items"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "id": "c3861799",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q.isEmpty()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "id": "bd31abdd",
   "metadata": {},
   "outputs": [],
   "source": [
    "# insert elements\n",
    "q.enqueue(10)\n",
    "q.enqueue(\"A\")\n",
    "q.enqueue(20)\n",
    "q.enqueue(\"F\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "id": "0f3cf0a3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['F', 20, 'A', 10]"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# print items of the stack\n",
    "q.items"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "id": "095370e2",
   "metadata": {},
   "outputs": [],
   "source": [
    "# element added at the rear of the queue\n",
    "q.enqueue(100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "id": "44a6c432",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[100, 'F', 20, 'A', 10]"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q.items"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "id": "76ca391b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# size of the queue\n",
    "q.size()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "id": "dc4e8c44",
   "metadata": {},
   "outputs": [],
   "source": [
    "# remove elements at the front of the queue\n",
    "\n",
    "q.dequeue()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "id": "5f1da48c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[100, 'F', 20, 'A']"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q.items"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "id": "1e0a6547",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 89,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q.isEmpty()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8c8cbfea",
   "metadata": {},
   "source": [
    "- As you can see, the class has not included the condition for queue underflow or overflow. Note that, similar to stacks, we can check for underflow conditions by including if self.isEmpty() statement in the dequeue method.\n",
    "- An overflow condition is not checked since we have created an empty list with variable sizes. Suppose, there is a constraint on the size of the list, then you keep a count variable to keep track of the size of the queue to avoid overflow conditions."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c7adabb8",
   "metadata": {},
   "source": [
    "Here is a brief summary of important concepts in queue:\n",
    "\n",
    "- The right end of the list is considered the front, and the left end of the queue is the rear (rear-->front). Dequeue operation happens at the front, and enqueue operation occurs at the rear end.\n",
    "\n",
    "- Note that you can swap the rear and front end convention as well and write your class methods accordingly. But just ensure that enqueuing and dequeuing happens on opposite ends of the queue as per the methods you define in the class. Python inbuilt class uses the convention of the front-->rear, which is opposite to the convention we used.\n",
    "\n",
    "- We did not create any method to print the queue. ‘s.items’ (object_name.list_name) is used to print the elements of the stack. However, you can also write a method inside the class to print the contents of the queue.  In the OOP construct, any attribute of the class can be accessed by object_name.attribute_name. Class attributes include all variables and methods written inside the class."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "id": "d894baea",
   "metadata": {},
   "outputs": [],
   "source": [
    "# You are given a queue with n integers and you need to print the 'k'th element from the front(head) of the queue\n",
    "\n",
    "def print_element(q,k):\n",
    "    \n",
    "    if k > q.size():\n",
    "        print(\"There are not enough elements in the queue\")\n",
    "        return\n",
    "    \n",
    "    for i in range(1,k):\n",
    "        print(q.items)\n",
    "        q.dequeue()\n",
    "        \n",
    "    print(q.items)    \n",
    "    print(q.items[-1]) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "id": "d726a2fa",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 6 7 8 9 10 11 12\n",
      "3\n",
      "['1', '2', '3', '4', '5', '6', '7', '8', '9', '10', '11', '12']\n",
      "['1', '2', '3', '4', '5', '6', '7', '8', '9', '10', '11']\n",
      "['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "q=Queue()\n",
    "\n",
    "inp = reversed(input().split())\n",
    "k=int(input())\n",
    "\n",
    "\n",
    "for ele in inp:\n",
    "    q.enqueue(ele)\n",
    "    \n",
    "print_element(q,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 140,
   "id": "143bf81c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_element(q,k):\n",
    "    \n",
    "    if k > q.size():\n",
    "        print(\"There are not enough elements in the queue\")\n",
    "        return\n",
    "        \n",
    "    print(q.items[-k]) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "id": "435aee98",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 6 7 8 9 10 11 12\n",
      "3\n",
      "['1', '2', '3', '4', '5', '6', '7', '8', '9', '10', '11', '12']\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "q=Queue()\n",
    "\n",
    "inp = input().split()\n",
    "k=int(input())\n",
    "\n",
    "\n",
    "for i in range(len(inp)-1, -1, -1):\n",
    "    q.enqueue(inp[i])\n",
    "    \n",
    "print_element(q,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 144,
   "id": "66300230",
   "metadata": {},
   "outputs": [],
   "source": [
    "# print the kth element from the rear end of queue\n",
    "\n",
    "\n",
    "def print_element(q,k):\n",
    "    \n",
    "    if k > q.size():\n",
    "        print(\"There are not enough elements in the queue\")\n",
    "        return\n",
    "    \n",
    "    print(q.items[k-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 145,
   "id": "db402875",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 6 7 8 9 10 11 12\n",
      "3\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "q=Queue()\n",
    "\n",
    "inp = input().split()\n",
    "k=int(input())\n",
    "\n",
    "\n",
    "for ele in inp:\n",
    "    q.enqueue(ele)\n",
    "    \n",
    "print_element(q,k)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3f73454f",
   "metadata": {},
   "source": [
    "### Hot Potato problem"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "26d75af8",
   "metadata": {},
   "source": [
    "In this game, a group of people line up in a circle, and once the music starts, players pass an object(say a ball or a potato) to the next person and keep doing that as long as the music is still playing. The moment the music stops, whoever has the ball in their hand will be removed from the circle, and the next round of the game starts. The loop continues until only one player is left, and that person is declared the winner. For the sake of simplicity, we will assume that after a constant number of passes' n', whoever has the ball should be eliminated in each round. The objective is to find the winner of the game. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "403db741",
   "metadata": {},
   "source": [
    "5 participants and 3 passes. Whoever has the ball at 3d pass was eliminated."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "36e8f417",
   "metadata": {},
   "source": [
    "- Round 1 : S-> G-> M-> J R , J is eliminated\n",
    "- Round 2 : R-> S-> G-> M , M is eliminated\n",
    "- Round 3 : R-> S-> G-> R , R is eliminated\n",
    "- Round 4:  S-> G-> S-> G, G is eliminated and S is the winner"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "02ac6182",
   "metadata": {},
   "source": [
    "it took four rounds to find the winner when k=3 and number of players=5."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ad51596",
   "metadata": {},
   "source": [
    "- Store the given list of players in a queue. Since the first person in the given list of players starts the game, keep the first player at the front of the queue, the second player in the input list will be behind the first player. The order of the player is in the original list is retained in the queue.\n",
    "- The number of passes, after which a player is eliminated is taken as an input. For simplicity, we'll assume that this number is constant.\n",
    "- Keep the position of the ball fixed in the front end of the queue. Since we have the position of the ball fixed, we will move the players instead of passing the ball.\n",
    "- The player at the front end of the queue will always be having the ball. Perform the necessary enqueue and dequeue operations based on the number of passes until only one person remains in the queue."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c76834e7",
   "metadata": {},
   "source": [
    "Sample Input: ['Smith', 'Garry', 'Michael', 'Julian', 'Robert'], 3"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "697f2976",
   "metadata": {},
   "source": [
    "We start by enqueuing the players’ list into a queue. As per our convention, the **right end of the list is the front of the queue**. Since the queue follows the FIFO principle, the final queue will look like this:\n",
    "\n",
    "**['Robert', 'Julian', 'Michael','Garry', 'Smith']**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dd16dc2c",
   "metadata": {},
   "source": [
    "#### Round 1\n",
    "The number of passes after which a player should be eliminated is 3. Instead of passing the ball three times, we have fixed the ball at the front and perform dequeue and enqueue operations three times."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bc4c3575",
   "metadata": {},
   "source": [
    "#### First pass\n",
    "The game starts with Smith having the ball who passes it to the person next to him, that is, Garry. Now, in the first pass, Smith leaves the front and joins back in the rear of the queue (imagine this as a circle).        "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ae05d61d",
   "metadata": {},
   "source": [
    "#### Second pass\n",
    "Garry leaves from the front and joins at the rear end"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d36a7921",
   "metadata": {},
   "source": [
    "### Third pass\n",
    "Now, in the third pass, Michael leaves from the front and join at the rear end of the queue "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fb0f8399",
   "metadata": {},
   "source": [
    "#### End of round 1\n",
    "At the end of the third pass, Julian, who is in the front has the ball. Hence, he will be eliminated from the game"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7f04a3ad",
   "metadata": {},
   "source": [
    "- Round 1: Smith -> Garry -> Michael -> Julian. Now, Julian has the ball and he will be eliminated.\n",
    "- Round 2: Robert -> Smith -> Garry -> Michael. Now, Michael has the ball and will be eliminated.\n",
    "- Round 3: Robert -> Smith -> Garry -> Robert. Now, Michael has the ball and he will be eliminated.\n",
    "- Round 4: Smith -> Garry -> Smith ->Garry. Now, Garry has the ball and he will be eliminated.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8dc7b3ae",
   "metadata": {},
   "source": [
    " the results remain the same even if we change the front and rear conventions as long as deletion happens at the front and insertion happens at the rear. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "85781074",
   "metadata": {},
   "source": [
    "- Take the input for the list of players and the number of passes.\n",
    "- Create an instance of class Queue and enqueue the players into a queue\n",
    "- Now, the player in the front has to start the game since he is the first player in the player list provided.\n",
    "- As long as at least one player is remaining in the queue, do the following:\n",
    "- For 'k' times dequeue the player in the front and enqueue him to the rear. After 'k' passes, dequeue the player in the front permanently.\n",
    "- The above step has to be repeated until only one player is left.\n",
    "- The only element in the queue is declared as the winner.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 203,
   "id": "6d3f8cba",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self.items=[]\n",
    "    \n",
    "    def enqueue(self, item):\n",
    "        self.items.insert(0,item)\n",
    "        \n",
    "    def dequeue(self):\n",
    "        if self.isEmpty():\n",
    "            return -1\n",
    "        return self.items.pop()\n",
    "        \n",
    "    def isEmpty(self):\n",
    "        return self.items==[]\n",
    "                    \n",
    "    def size(self):\n",
    "        return len(self.items)\n",
    "    \n",
    "    def peek(self):\n",
    "        return self.items[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 220,
   "id": "f619ddff",
   "metadata": {},
   "outputs": [],
   "source": [
    "players = [ 'Smith' , 'Garry' , 'Michael' , 'Julian', 'Robert']\n",
    "passes = 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 221,
   "id": "b8c22433",
   "metadata": {},
   "outputs": [],
   "source": [
    "q=Queue()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 222,
   "id": "f77371e8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Robert', 'Julian', 'Michael', 'Garry', 'Smith']\n"
     ]
    }
   ],
   "source": [
    "for player in players:\n",
    "    q.enqueue(player)\n",
    "print(q.items)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 223,
   "id": "c5dec68a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Michael', 'Garry', 'Smith', 'Robert']\n",
      "['Garry', 'Smith', 'Robert']\n",
      "['Garry', 'Smith']\n",
      "['Smith']\n"
     ]
    }
   ],
   "source": [
    "while q.size() > 1:\n",
    "    for i in range(passes):\n",
    "        front_player = q.dequeue()\n",
    "        q.enqueue(front_player)\n",
    "    eliminated = q.dequeue()\n",
    "    print(q.items)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 224,
   "id": "43c8b73d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Smith']\n"
     ]
    }
   ],
   "source": [
    "print(q.items)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 228,
   "id": "3d7ff748",
   "metadata": {},
   "outputs": [],
   "source": [
    "def hot_potato(players, passes):\n",
    "    q=Queue()\n",
    "    \n",
    "    for player in players:\n",
    "        q.enqueue(player)\n",
    "    \n",
    "    while q.size() > 1:\n",
    "        for i in range(passes):\n",
    "            front_player = q.dequeue()\n",
    "            q.enqueue(front_player)\n",
    "        eliminated = q.dequeue()\n",
    "        print(q.items)\n",
    "    \n",
    "    return q.items()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 230,
   "id": "ca173e28",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Michael', 'Garry', 'Smith', 'Robert']\n",
      "['Garry', 'Smith', 'Robert']\n",
      "['Garry', 'Smith']\n",
      "['Smith']\n"
     ]
    }
   ],
   "source": [
    "players = [ 'Smith' , 'Garry' , 'Michael' , 'Julian', 'Robert']\n",
    "passes = 3\n",
    "hot_potato(players, passes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 237,
   "id": "ed9d06b4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def hot_potato(players,passes):\n",
    "    \n",
    "    q=Queue()\n",
    "    \n",
    "    for player in players:\n",
    "        q.enqueue(player)\n",
    " \n",
    "    while q.size()>1:\n",
    "        for i in range(passes):\n",
    "            player_passing=q.dequeue()\n",
    "            q.enqueue(player_passing)\n",
    "        q.dequeue()\n",
    "    return q.dequeue()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 238,
   "id": "2ce92da2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Smith\n"
     ]
    }
   ],
   "source": [
    "print(hot_potato(['Smith', 'Garry', 'Michael', 'Julian', 'Robert'],3))"
   ]
  }
 ],
 "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": 5
}