Stacks, Queues and Deques.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "4bf932c7",
   "metadata": {},
   "source": [
    "# Implementation of a Stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "id": "6d05459d",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Stack(object):\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "    \n",
    "    def isEmpty(self):\n",
    "        return self.items == []\n",
    "    \n",
    "    def push(self, item):\n",
    "        self.items.append(item)\n",
    "    \n",
    "    def pop(self):\n",
    "        return self.items.pop()\n",
    "    \n",
    "    def peek(self):\n",
    "        return self.items[len(self.items)-1]\n",
    "    \n",
    "    def size(self):\n",
    "        return len(self.items)\n",
    "    \n",
    "    def _print(self):\n",
    "        print(self.items)\n",
    "        \n",
    "s = Stack()\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "id": "136f0ed8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "print(s.isEmpty())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "id": "c8328119",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 'two', 'SS']\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s.push(1)\n",
    "s.push(\"two\")\n",
    "s.push(\"SS\")\n",
    "s._print()\n",
    "s.isEmpty()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "id": "dfe96fdb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s.size()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "id": "0fc5b437",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'SS'"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s.peek()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "id": "24bcd57d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 'two']\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s.pop()\n",
    "s._print()\n",
    "s.isEmpty()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3deb9c05",
   "metadata": {},
   "source": [
    "# Implementation Of Queue\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "id": "4eb7fc79",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Queue():\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "        \n",
    "    def isEmpty(self):\n",
    "        return self.iemts == []\n",
    "    \n",
    "    def enqueue(self,item):\n",
    "        self.items.insert(0,item)\n",
    "        \n",
    "    def dequeue(self):\n",
    "        self.items.pop()\n",
    "        \n",
    "    def size(self):\n",
    "        return len(self.items)\n",
    "    \n",
    "    def _print(self):\n",
    "        print(self.items)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "id": "8c926732",
   "metadata": {},
   "outputs": [],
   "source": [
    "q = Queue()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "id": "b2d48ebc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 102,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q.size()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "id": "e6a70174",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[8, 6, 5]\n"
     ]
    }
   ],
   "source": [
    "q.enqueue(5)\n",
    "q.enqueue(6)\n",
    "q.enqueue(8)\n",
    "q._print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "id": "badab093",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[8, 6]\n"
     ]
    }
   ],
   "source": [
    "q.dequeue()\n",
    "q._print()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43c33fae",
   "metadata": {},
   "source": [
    "# Implementation of a Deque"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "id": "ccc91bcd",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Deque(object):\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "        \n",
    "    def isEmpty(self):\n",
    "        self.items = []\n",
    "    \n",
    "    def addFront(self, item):\n",
    "        self.items.append(item)\n",
    "        \n",
    "    def addRear(self, item):\n",
    "        self.items.insert(0,item)\n",
    "        \n",
    "    def removeFront(self):\n",
    "        return self.items.pop()\n",
    "    \n",
    "    def removeRear(self):\n",
    "        return self.items.pop(0)\n",
    "    \n",
    "    def size(self):\n",
    "        return len(self.items)\n",
    "    \n",
    "    def _print(self):\n",
    "        print(self.items)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "id": "661f2238",
   "metadata": {},
   "outputs": [],
   "source": [
    "de = Deque()\n",
    "de.addFront(\"Hello\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "id": "5973344a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Hello']\n"
     ]
    }
   ],
   "source": [
    "de._print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "id": "c9cca8ec",
   "metadata": {},
   "outputs": [],
   "source": [
    "de.addFront(\"World\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "id": "7bb04025",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Hello', 'World']\n"
     ]
    }
   ],
   "source": [
    "de._print()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e50334dd",
   "metadata": {},
   "source": [
    "# Balenced Parentheses Check\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "id": "ffc96338",
   "metadata": {},
   "outputs": [],
   "source": [
    "def balance_check(s):\n",
    "    \n",
    "    if len(s) % 2 != 0:\n",
    "        return False\n",
    "    \n",
    "    matches = set([(\"(\",\")\"),(\"{\",\"}\"),(\"[\",\"]\")])\n",
    "    opening = set(\"[{(\")\n",
    "    stack =[]\n",
    "    \n",
    "    \n",
    "    for paren in s:\n",
    "        \n",
    "        if paren in opening:\n",
    "            stack.append(paren)\n",
    "            \n",
    "        else:\n",
    "            if len(stack) == 0:\n",
    "                return False\n",
    "            \n",
    "            last_open = stack.pop()\n",
    "            \n",
    "            if (last_open, paren) not in matches:\n",
    "                return False\n",
    "            \n",
    "    return len(stack) == 0\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 150,
   "id": "48f9d686",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 150,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "balance_check(\"[{{({})}}]\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 151,
   "id": "7f42a849",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 151,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "balance_check(\"[({}()])\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b86dd9cc",
   "metadata": {},
   "source": [
    "# Implement a Queue - Using  two Stacks\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 188,
   "id": "1d784fdc",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Queue2Stacks(object):\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.instack = []\n",
    "        self.outstack = []\n",
    "        \n",
    "    def enqueue(self, element):\n",
    "        self.instack.append(element)\n",
    "        \n",
    "    def dequeue(self):\n",
    "        if not self.outstack:\n",
    "            self.outstack.append(self.instack.pop())\n",
    "        return self.outstack.pop()\n",
    "    def _print(self):\n",
    "        print(self.outstack)\n",
    "        print(self.instack)\n",
    "q2s = Queue2Stacks()\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 189,
   "id": "7b150d20",
   "metadata": {},
   "outputs": [],
   "source": [
    "q2s.enqueue(5)\n",
    "q2s.enqueue(4)\n",
    "q2s.enqueue(3)\n",
    "q2s.enqueue(2)\n",
    "q2s.enqueue(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 190,
   "id": "8e9dd48f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[]\n",
      "[5, 4, 3, 2, 1]\n"
     ]
    }
   ],
   "source": [
    "q2s._print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 191,
   "id": "7740aa7c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 191,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q2s.dequeue()\n",
    "q2s.dequeue()\n",
    "q2s.dequeue()\n",
    "q2s.dequeue()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 192,
   "id": "8db90f06",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[]\n",
      "[5]\n"
     ]
    }
   ],
   "source": [
    "q2s._print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "98da5a72",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}