Stack_implementation.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Stack implementation.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/bpradeep508/matrix2d/blob/master/Stack_implementation.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Implementation of stack using dynamic array**"
      ],
      "metadata": {
        "id": "M2dssALNz_cM"
      }
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "irI41E2Oza4O"
      },
      "outputs": [],
      "source": [
        "stack = [] ## dynamic array\n",
        "stack.append('https://leetcode.com/')\n",
        "stack.append('https://leetcode.com/problemset/all/')\n",
        "stack.append('https://leetcode.com/problems/two-sum/')"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "print(stack)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "5Vl0KL7Wzkf4",
        "outputId": "cd29a31d-5d59-4ba8-b801-4b359308e471"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "['https://leetcode.com/', 'https://leetcode.com/problemset/all/', 'https://leetcode.com/problems/two-sum/']\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "stack.pop()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "id": "I02cZPbbzhq5",
        "outputId": "ad16d822-ad7a-4f36-c8ea-9d4dd4704c6b"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "'https://leetcode.com/problems/two-sum/'"
            ],
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            }
          },
          "metadata": {},
          "execution_count": 3
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "stack.pop()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "id": "FIrXJHTIzmpX",
        "outputId": "4cfae74b-5dfd-4c4f-d332-f07f5b0df39e"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "'https://leetcode.com/problemset/all/'"
            ],
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            }
          },
          "metadata": {},
          "execution_count": 4
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "stack"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "IFn2LyoFzprW",
        "outputId": "741225c6-9e2d-4a65-eee4-6aa9877dbff5"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "['https://leetcode.com/']"
            ]
          },
          "metadata": {},
          "execution_count": 5
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Implementation of stack using linked list -> collections.deque()**"
      ],
      "metadata": {
        "id": "y_Do5TbX0EpZ"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from collections import deque"
      ],
      "metadata": {
        "id": "s5IG3HjJzrsW"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "stack_LL = deque()"
      ],
      "metadata": {
        "id": "AmL_T97f0qP6"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "dir(stack_LL)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ZcR5if7v0u7e",
        "outputId": "bf27df1e-6682-4087-e182-e1985d8e80c2"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "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']"
            ]
          },
          "metadata": {},
          "execution_count": 8
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "stack_LL.append('https://leetcode.com/')\n",
        "stack_LL.append('https://leetcode.com/problemset/all/')\n",
        "stack_LL.append('https://leetcode.com/problems/two-sum/')"
      ],
      "metadata": {
        "id": "ARvHvfnN02cG"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "stack_LL"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "M8xHcH061O4Y",
        "outputId": "14c87d1a-3c8c-4fb2-c25a-ea6176b530bb"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "deque(['https://leetcode.com/',\n",
              "       'https://leetcode.com/problemset/all/',\n",
              "       'https://leetcode.com/problems/two-sum/'])"
            ]
          },
          "metadata": {},
          "execution_count": 10
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "stack_LL.pop()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "id": "IAQ85O5e1P-Y",
        "outputId": "a5d6c89d-0334-470d-9c56-43ab49013917"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "'https://leetcode.com/problems/two-sum/'"
            ],
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            }
          },
          "metadata": {},
          "execution_count": 11
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "stack_LL"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "DLP5A3201ZPW",
        "outputId": "cab59e70-d024-4fcc-f519-3e46b80cd11e"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "deque(['https://leetcode.com/', 'https://leetcode.com/problemset/all/'])"
            ]
          },
          "metadata": {},
          "execution_count": 12
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "class Stack:\n",
        "\n",
        "  def __init__(self):\n",
        "    self.container = deque()\n",
        "\n",
        "  def push(self, value):\n",
        "    self.container.append(value)\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)"
      ],
      "metadata": {
        "id": "3M-gXJJV1jhO"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "st = Stack()\n",
        "st.push(12)"
      ],
      "metadata": {
        "id": "lsh_hrgH3zG8"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "st.push(14)\n",
        "st.push(16)\n",
        "st.push(18)"
      ],
      "metadata": {
        "id": "yK-4b_9937Hv"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "st.peek()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "VF8j3hTw4BDH",
        "outputId": "a856f1d9-2344-49bd-982d-d7128cdd2b97"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "18"
            ]
          },
          "metadata": {},
          "execution_count": 22
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "st.pop()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "d2UbeVS24BuX",
        "outputId": "2b3a940d-4d37-4890-a57e-7200f912d008"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "18"
            ]
          },
          "metadata": {},
          "execution_count": 23
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "st.peek()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "bgu6qQwa4NO_",
        "outputId": "bdcbb4b3-8983-4a38-c666-eb35613553a8"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "16"
            ]
          },
          "metadata": {},
          "execution_count": 24
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "st.peek()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "KI_0Mkd_4cG3",
        "outputId": "7c04971f-da94-45f4-9790-fe477c1538ab"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "16"
            ]
          },
          "metadata": {},
          "execution_count": 25
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "st.is_empty()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "p3PtFGFT4fLo",
        "outputId": "f9765686-37f2-4d94-89fc-4eb1304efe47"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "False"
            ]
          },
          "metadata": {},
          "execution_count": 26
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "st.size()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "sDFh9RRD4ogY",
        "outputId": "5221b06c-c2fc-4bac-855d-1cc28c4bdd10"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "3"
            ]
          },
          "metadata": {},
          "execution_count": 27
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Interview Problem: Given a string containing the characters '(',')','{','}','[',']', determine if the input string entered by the user is valid or not.\n",
        "\n",
        "An input string is valid if it satisfies below condition:\n",
        "1. Open brackets must be closed by the same type of brackets.\n",
        "2. Open brackets must be closed in the correct order."
      ],
      "metadata": {
        "id": "IsVX9qad46Ww"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "## method definition of isValid(str) \n",
        "def isValid(str):\n",
        "  ##write your code here\n",
        "  \n",
        "\n",
        "\n",
        "\n",
        "## driver code\n",
        "str = \"{[]}\"\n",
        "if isValid(str):\n",
        "  print(\"Given string contains valid parenthesis\")\n",
        "else:\n",
        "  print(\"Given string contains invalid parenthesis\")"
      ],
      "metadata": {
        "id": "3u6ZkHc14q8X"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}