Python_Data_Structures_Stacks_Deques_and_Queues.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "983a4780-e62a-4867-a8c7-33f1309bf77c",
   "metadata": {},
   "source": [
    "# LinkedIn Learning\n",
    "# Python Data Structures : Stacks, Deques and Queues"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "20287228-b4a0-4ba3-9c79-6af41435bac1",
   "metadata": {},
   "source": [
    "## 1. Stacks"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6432794b-d7e8-4b6d-80c8-494820cd567b",
   "metadata": {},
   "source": [
    "##### LIFO --> Last In First Out \n",
    "##### push() --> When an element is added to the top, it is pushed on\n",
    "##### pop() --> When an element is taken off the top of the stack , it is popped off\n",
    "##### peek() --> See the element on the stack without popping it off "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "45101c13-0315-45f3-a7d2-ec8f922a0813",
   "metadata": {},
   "source": [
    "### A. push()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "9ed6dceb-00c1-4a0f-9cc1-b70023308e55",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5]\n"
     ]
    }
   ],
   "source": [
    "stack = [1,2,3,4]\n",
    "stack.append(5)\n",
    "print(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "1d833638-9a63-4ba3-a77d-257d20f62534",
   "metadata": {},
   "outputs": [],
   "source": [
    "def push(stack, item):\n",
    "    stack.insert(0, item)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "7a3ce54a-4a95-4c49-8c42-8124ec15a80b",
   "metadata": {},
   "outputs": [],
   "source": [
    "push(stack, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "4cd83425-b9b6-4dac-9b49-f1d98b6a8a1c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 5]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "stack"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eb941723-5097-40e7-83a7-81380bfed659",
   "metadata": {},
   "source": [
    "### B. pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "7a2b2a44-840a-42ed-9de8-323b06b80c94",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4]\n",
      "4\n",
      "[1, 2, 3]\n"
     ]
    }
   ],
   "source": [
    "stack = [1,2,3,4]\n",
    "print(stack)\n",
    "print(stack.pop())\n",
    "print(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "409f7419-01d0-4ae2-bd33-5fe64ec28fc6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "[1, 2, 3]\n"
     ]
    }
   ],
   "source": [
    "stack = [1,2,3,4]\n",
    "top = stack.pop()\n",
    "print(top)\n",
    "print(stack)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6aa70012-1cd5-4bec-965f-5ab22838d9dc",
   "metadata": {},
   "source": [
    "### C. peek()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "9594085b-7331-494b-85ab-b5bcda476794",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "[1, 2, 3, 4]\n"
     ]
    }
   ],
   "source": [
    "stack = [1,2,3,4]\n",
    "print(stack[-1])\n",
    "print(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "c5fdc41c-05a2-46e3-a929-0f52a8c686a1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Stack is empty!!!\n"
     ]
    }
   ],
   "source": [
    "stack = []\n",
    "try:\n",
    "    print(stack[-1])\n",
    "except IndexError:\n",
    "    print(\"Stack is empty!!!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4d0a61e6-b847-430a-9678-771c7cb7d06a",
   "metadata": {},
   "source": [
    "### 2. Queues "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f29f2026-dd25-4f6c-b1e4-fdcce9a3889a",
   "metadata": {},
   "source": [
    "##### FIFO --> First In First Out"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "47c8a175-bd73-409d-bd21-b759f63b3f7c",
   "metadata": {},
   "source": [
    "### A. List Based"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "d250c624-f03e-4370-ba58-c7b3c9c299df",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self.queue = []\n",
    "    def enqueue(self, item):\n",
    "        self.queue.append(item)\n",
    "    def dequeue(self):\n",
    "        if len(self.queue) == 0:\n",
    "            return None\n",
    "        else:\n",
    "            item = self.queue[0]\n",
    "            self.queue = self.queue[1:]\n",
    "            return item\n",
    "    def is_empty(self):\n",
    "        return len(self.queue) == 0\n",
    "    def size(self):\n",
    "        return len(self.queue)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "19e60a19-7a7d-45fb-8697-0e6753832fdd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n"
     ]
    }
   ],
   "source": [
    "q = Queue()\n",
    "q.enqueue(10)\n",
    "q.enqueue(20)\n",
    "q.enqueue(30)\n",
    "q.enqueue(40)\n",
    "print(q.size())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "ec5c1dd7-7ebc-42b9-adfa-6833379d00e5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n"
     ]
    }
   ],
   "source": [
    "value = q.dequeue()\n",
    "print(value)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c2fe4709-ab9a-485f-99ad-c9d2558840a3",
   "metadata": {},
   "source": [
    "### B. Stack Based"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "f5c6fd8e-8b32-4e81-8fd9-d18b393fc635",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self.enqueue_stack = []\n",
    "        self.dequeue_stack = []\n",
    "    def enqueue(self, item):\n",
    "        self.enqueue_stack.append(item)\n",
    "    def dequeue(self):\n",
    "        if len(self.dequeue_stack) == 0:\n",
    "            while len(self.enqueue_stack) > 0:\n",
    "                item = self.self.enqueue_stack.pop()\n",
    "                self.dequeue_stack.append(item)\n",
    "        if len(self.dequeue_stack) == 0:\n",
    "            return None\n",
    "    def is_empty(self):\n",
    "        return len(self.enqueue_stack) == 0 and len(self.dequeue_stack) == 0\n",
    "    def size(self):\n",
    "        return len(self.enqueue_stack) + len(self.dequeue_stack)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "22b1c5b2-e6fe-4ed9-aa51-8e43fbc5f009",
   "metadata": {},
   "source": [
    "### C. Node Based"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "90cb9502-9ff6-49b3-8622-3228ccaa86b2",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.next = None\n",
    "\n",
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        self.tail = None\n",
    "    def enqueue(self, value):\n",
    "        new_node = Node(value)\n",
    "        if self.tail is not None:\n",
    "            self.tail.next = new_node\n",
    "        self.tail = new_node\n",
    "        if self.head is None:\n",
    "            self.head = self.tail\n",
    "    def dequeue(self):\n",
    "        if self.head is None:\n",
    "            return None\n",
    "        item = self.head.value\n",
    "        self.head = self.head.next\n",
    "        if self.head is None:\n",
    "            self.tail = None\n",
    "        return item\n",
    "    def is_empty(self):\n",
    "        return self.head is None"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "39a8fb10-10fd-4e0b-9863-97d213464a4f",
   "metadata": {},
   "source": [
    "## 3. Deques"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a3c5b7f7-f8ec-44d6-97f1-4b692a81d5ad",
   "metadata": {},
   "source": [
    "##### reverse() --> Allows to reverse the order of the elements in the deque\n",
    "##### rotate() --> Allows to rotate the elements in the deque to the right or left\n",
    "##### extend() --> Allows to extend the deque with another iterable, such as a list"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d1381511-c7b8-43d2-9307-d093b9b9d5ce",
   "metadata": {},
   "source": [
    "##### Hybrid --> LIFO and FIFO models"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b6562a94-7f0e-46e3-8933-5b8abb4d3b07",
   "metadata": {},
   "source": [
    "### A. Appending Lists with deque"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "e2fab7b1-e972-4b7e-808a-58d82bc9853b",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "3e3d21f7-353a-409f-a424-90b6878edfcc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([2, 1])\n"
     ]
    }
   ],
   "source": [
    "my_deque = deque()\n",
    "my_deque.append(1)\n",
    "my_deque.appendleft(2)\n",
    "print(my_deque)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "867ac055-f3ae-4700-8dcd-c35c558e1a0e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([])\n"
     ]
    }
   ],
   "source": [
    "my_deque.pop()\n",
    "my_deque.popleft()\n",
    "print(my_deque)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5cb33aa8-7dcb-4bf5-bb83-dd78f21cc2d8",
   "metadata": {},
   "source": [
    "### B. rotate(), reverse() and extend()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "e90c5119-7f64-4443-8eef-a81056c99f6a",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "7b5bd186-58d5-4a1e-9f35-d433ef4d67bf",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([1, 2, 3, 4, 5])\n"
     ]
    }
   ],
   "source": [
    "my_deque = deque([1,2,3,4,5])\n",
    "print(my_deque)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "e7f86f8f-3078-45ff-b532-20a5768c7565",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([4, 5, 1, 2, 3])\n"
     ]
    }
   ],
   "source": [
    "my_deque.rotate(2)\n",
    "print(my_deque)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "a6dcd5a7-2702-4f6d-af82-f477a56857d3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([3, 2, 1, 5, 4])\n"
     ]
    }
   ],
   "source": [
    "my_deque.reverse()\n",
    "print(my_deque)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "647c60e5-070e-4d81-823b-86c556998697",
   "metadata": {},
   "outputs": [],
   "source": [
    "my_deque.extend([6,7,8])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "f5eb39fe-3b70-41f4-bfc7-5940552fb32f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([3, 2, 1, 5, 4, 6, 7, 8])\n"
     ]
    }
   ],
   "source": [
    "print(my_deque)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "966dde7f-087b-4d6f-a339-0f5fe8cd2d77",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.12.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}