5_stack (1).ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "VW5WEJ310bo7"
      },
      "source": [
        "<h2 style='color:purple' align='center'>Data Structures : Stack</h2>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "CvH3Kpzf0bo_"
      },
      "source": [
        "<h3 style='color:blue'>Using a list as a stack</h3>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "vAqVMnJk0bpA"
      },
      "outputs": [],
      "source": [
        "s = []\n",
        "s.append('https://www.cnn.com/')\n",
        "s.append('https://www.cnn.com/world')\n",
        "s.append('https://www.cnn.com/india')\n",
        "s.append('https://www.cnn.com/china')"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "YyzkCg6K0bpD",
        "outputId": "a7402fbe-0acb-45da-e671-9c50325b62aa"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "'https://www.cnn.com/china'"
            ]
          },
          "execution_count": 25,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "s.pop()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "u6NbTJdo0bpF",
        "outputId": "fa1ba9dd-f0c8-406c-da81-b92dd04bf542"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "'https://www.cnn.com/india'"
            ]
          },
          "execution_count": 26,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "s.pop()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "scrolled": true,
        "id": "1bt4whKV0bpG",
        "outputId": "3cbd4755-d984-43d8-fb7a-616f90057750"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "['https://www.cnn.com/', 'https://www.cnn.com/world']"
            ]
          },
          "execution_count": 27,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "s"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "scrolled": true,
        "id": "5H556jvq0bpG",
        "outputId": "78841535-27b7-4ab2-a4bd-420362ed67d0"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "'https://www.cnn.com/world'"
            ]
          },
          "execution_count": 28,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "s[-1]"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9sBqNsaV0bpH"
      },
      "source": [
        "**The issue with using a list as a stack is that list uses dymanic array internally and when it reaches its capacity it will reallocate a big chunk of memory somewhere else in memory area and copy all the elements. For example in below diagram if a list has a capacity of 10 and we try to insert 11th element, it will not allocate new memory in a different memory region, copy all 10 elements and then insert the 11th element. So overhead here is (1) allocate new memory plus (2) copy all existing elements in new memory area**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "sU1-j0YM0bpH"
      },
      "source": [
        "<img src=\"dynamic_memory.png\" />"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cK9JiW4z0bpI"
      },
      "source": [
        "<h3 style='color:blue'>Using deque as a stack</h3>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "O6L0rCPr0bpI"
      },
      "outputs": [],
      "source": [
        "from collections import deque\n",
        "stack = deque()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "Vvw_eH470bpJ",
        "outputId": "6be81936-8d74-46bc-f930-ac095f8d7f60"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "['__add__',\n",
              " '__bool__',\n",
              " '__class__',\n",
              " '__contains__',\n",
              " '__copy__',\n",
              " '__delattr__',\n",
              " '__delitem__',\n",
              " '__dir__',\n",
              " '__doc__',\n",
              " '__eq__',\n",
              " '__format__',\n",
              " '__ge__',\n",
              " '__getattribute__',\n",
              " '__getitem__',\n",
              " '__gt__',\n",
              " '__hash__',\n",
              " '__iadd__',\n",
              " '__imul__',\n",
              " '__init__',\n",
              " '__init_subclass__',\n",
              " '__iter__',\n",
              " '__le__',\n",
              " '__len__',\n",
              " '__lt__',\n",
              " '__mul__',\n",
              " '__ne__',\n",
              " '__new__',\n",
              " '__reduce__',\n",
              " '__reduce_ex__',\n",
              " '__repr__',\n",
              " '__reversed__',\n",
              " '__rmul__',\n",
              " '__setattr__',\n",
              " '__setitem__',\n",
              " '__sizeof__',\n",
              " '__str__',\n",
              " '__subclasshook__',\n",
              " 'append',\n",
              " 'appendleft',\n",
              " 'clear',\n",
              " 'copy',\n",
              " 'count',\n",
              " 'extend',\n",
              " 'extendleft',\n",
              " 'index',\n",
              " 'insert',\n",
              " 'maxlen',\n",
              " 'pop',\n",
              " 'popleft',\n",
              " 'remove',\n",
              " 'reverse',\n",
              " 'rotate']"
            ]
          },
          "execution_count": 29,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "dir(stack)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "ggtL_CmB0bpK",
        "outputId": "e0e3648b-ca98-4a9e-9f1f-0c4f4df0351f"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "deque(['https://www.cnn.com/'])"
            ]
          },
          "execution_count": 13,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "stack.append(\"https://www.cnn.com/\")\n",
        "stack"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "H2RWxHUJ0bpL",
        "outputId": "2a7f3918-63ae-4159-fad2-c6e4b4d8b719"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "deque(['https://www.cnn.com/', 'https://www.cnn.com/world'])"
            ]
          },
          "execution_count": 14,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "stack.append(\"https://www.cnn.com/world\")\n",
        "stack"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "skOK12o30bpL",
        "outputId": "13a577fe-75af-43f0-d933-9fd332535491"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "deque(['https://www.cnn.com/',\n",
              "       'https://www.cnn.com/world',\n",
              "       'https://www.cnn.com/india',\n",
              "       'https://www.cnn.com/china'])"
            ]
          },
          "execution_count": 15,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "stack.append(\"https://www.cnn.com/india\")\n",
        "stack.append(\"https://www.cnn.com/china\")\n",
        "stack"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "51sOBZ2q0bpM",
        "outputId": "0bf588e2-0da2-4fe7-8efa-0d178ba7707b"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "'https://www.cnn.com/china'"
            ]
          },
          "execution_count": 16,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "stack.pop()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "scrolled": true,
        "id": "4qjTAxZh0bpN",
        "outputId": "6b45859f-98a1-4e4b-b921-01103fa52ff9"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "'https://www.cnn.com/india'"
            ]
          },
          "execution_count": 17,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "stack.pop()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "v2gJ5VcY0bpN",
        "outputId": "e9e011b7-88e6-4885-d641-fcccab327a06"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "deque(['https://www.cnn.com/', 'https://www.cnn.com/world'])"
            ]
          },
          "execution_count": 18,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "stack"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "14-1MVNa0bpO",
        "outputId": "5a33b630-9653-4199-b0b6-0009a3beb5dd"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "'https://www.cnn.com/world'"
            ]
          },
          "execution_count": 20,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "stack.pop()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "uBe8PwJR0bpO",
        "outputId": "5e323dcc-af85-450e-df1f-64c82dbc9db6"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "'https://www.cnn.com/'"
            ]
          },
          "execution_count": 21,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "stack.pop()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "scrolled": false,
        "id": "qzlccegD0bpP",
        "outputId": "c379b8ca-c16d-49c4-b0e6-e701721ad637"
      },
      "outputs": [
        {
          "ename": "IndexError",
          "evalue": "pop from an empty deque",
          "output_type": "error",
          "traceback": [
            "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[1;31mIndexError\u001b[0m                                Traceback (most recent call last)",
            "\u001b[1;32m<ipython-input-22-415460d3b717>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mstack\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mpop\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
            "\u001b[1;31mIndexError\u001b[0m: pop from an empty deque"
          ]
        }
      ],
      "source": [
        "stack.pop()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xHnFMjnB0bpP"
      },
      "source": [
        "<h3 style='color:blue'>Implement Stack class using a deque</h3>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "vadcuY1A0bpP"
      },
      "outputs": [],
      "source": [
        "class Stack:\n",
        "    def __init__(self):\n",
        "        self.container = deque()\n",
        "\n",
        "    def push(self,val):\n",
        "        self.container.append(val)\n",
        "\n",
        "    def pop(self):\n",
        "        return self.container.pop()\n",
        "\n",
        "    def peek(self):\n",
        "        return  self.container[-1]\n",
        "\n",
        "    def is_empty(self):\n",
        "        return len(self.container)==0\n",
        "\n",
        "    def size(self):\n",
        "        return len(self.container)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "V_-RMzqV0bpQ"
      },
      "outputs": [],
      "source": [
        "s = Stack()\n",
        "s.push(5)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "KWHJ-Zn50bpQ",
        "outputId": "96a39eec-6776-4bad-b593-d1cb457a3288"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "False"
            ]
          },
          "execution_count": 43,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "s.is_empty()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "5hNZ9Fzq0bpQ",
        "outputId": "e20fcc69-1b4e-4e46-8c9c-0336883af771"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "5"
            ]
          },
          "execution_count": 44,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "s.pop()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "V3OLLeoO0bpQ",
        "outputId": "d0c6ef3a-ad26-4104-8b51-5c95f9feac7b"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "True"
            ]
          },
          "execution_count": 45,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "s.is_empty()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "W7mpexK60bpR"
      },
      "outputs": [],
      "source": [
        "s.push(9)\n",
        "s.push(34)\n",
        "s.push(78)\n",
        "s.push(12)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "MDO_Zpn90bpS",
        "outputId": "b16562cf-1c35-489e-c190-bde11c2d1c79"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "12"
            ]
          },
          "execution_count": 47,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "s.peek()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "FFaRNkTd0bpS",
        "outputId": "26484232-7765-4765-980e-b8bccec3fbdc"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "12"
            ]
          },
          "execution_count": 48,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "s.pop()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "scrolled": true,
        "id": "dUzy59J-0bpT",
        "outputId": "f14a891d-e1a6-4113-b28d-c398d684a4af"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "78"
            ]
          },
          "execution_count": 49,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "s.pop()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "OQ3P7cy70bpT",
        "outputId": "d267a929-a882-4d41-d428-62f125c80607"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "34"
            ]
          },
          "execution_count": 50,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "s.pop()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "tL4Sv5j-0bpU",
        "outputId": "651ebe19-ca56-4157-f3d0-a55d30d73979"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "9"
            ]
          },
          "execution_count": 51,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "s.pop()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "zSN43nJU0bpV",
        "outputId": "9a3be835-5950-451a-bdf6-fd801ffaf5e6"
      },
      "outputs": [
        {
          "ename": "IndexError",
          "evalue": "pop from an empty deque",
          "output_type": "error",
          "traceback": [
            "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[1;31mIndexError\u001b[0m                                Traceback (most recent call last)",
            "\u001b[1;32m<ipython-input-52-c88c8c48122b>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0ms\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mpop\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
            "\u001b[1;32m<ipython-input-41-f432a50cab7c>\u001b[0m in \u001b[0;36mpop\u001b[1;34m(self)\u001b[0m\n\u001b[0;32m      7\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      8\u001b[0m     \u001b[1;32mdef\u001b[0m \u001b[0mpop\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 9\u001b[1;33m         \u001b[1;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mcontainer\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mpop\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     10\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     11\u001b[0m     \u001b[1;32mdef\u001b[0m \u001b[0mpeek\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
            "\u001b[1;31mIndexError\u001b[0m: pop from an empty deque"
          ]
        }
      ],
      "source": [
        "s.pop()"
      ]
    }
  ],
  "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.3"
    },
    "colab": {
      "provenance": []
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}