Misc Data Structures.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stack"
   ]
  },
  {
   "cell_type": "code",
<<<<<<< HEAD
   "execution_count": null,
=======
   "execution_count": 1,
>>>>>>> 8fd55a64ed3aa6820e41d3d04064e62a93184ac4
   "metadata": {},
   "outputs": [],
   "source": [
    "class Stack:\n",
    "    \"\"\"\n",
    "    Stack data structure using list\n",
    "    \"\"\"\n",
    "    def __init__(self,value=None,name=None,verbose=False):\n",
    "        \"\"\"\n",
    "        Class initializer: Produces a stack with a single value or a list of values\n",
    "        value: The initial value. Could be a list of a single item.\n",
    "        name: Optional name for the stack.\n",
    "        verbose: Boolean. Determines if each stack operation prints the item being pushed or popped.\n",
    "        \"\"\"\n",
    "        self._items = []\n",
    "        self._height=0\n",
    "        self._verbose=verbose\n",
    "        \n",
    "        if value!=None:            \n",
    "            if type(value)==list:\n",
    "                for v in value:\n",
    "                    self._items.append(v)\n",
    "                self._height = len(value)\n",
    "            else:\n",
    "                self._items.append(value)\n",
    "                self._height = 1\n",
    "        else:\n",
    "            print(\"Empty stack created.\")\n",
    "        \n",
    "        if name!=None:\n",
    "            self._name=str(name)\n",
    "        else:\n",
    "            self._name=''\n",
    "        \n",
    "    def pop(self):\n",
    "        if self._height == 0:\n",
    "            print (\"Stack is empty. Nothing to pop.\")\n",
    "            return None\n",
    "        else:\n",
    "            self._height -=1\n",
    "            item=self._items.pop()\n",
    "            if self._verbose:\n",
    "                print(\"{} popped\".format(item))\n",
    "            return item\n",
    "    \n",
    "    def push(self,value=None):\n",
    "        \"\"\"\n",
    "        Pushes a a single value or a list of values onto the stack\n",
    "        \"\"\"\n",
    "        if value!=None:            \n",
    "            if type(value)==list:\n",
    "                for v in value:\n",
    "                    self._items.append(v)\n",
    "                    if self._verbose:\n",
    "                        print(\"{} pushed\".format(v))\n",
    "                self._height += len(value)\n",
    "            else:\n",
    "                self._height +=1\n",
    "                self._items.append(value)\n",
    "                if self._verbose:\n",
    "                        print(\"{} pushed\".format(value))\n",
    "        else:\n",
    "            if self._verbose:\n",
    "                print(\"No value supplied, nothing was pushed.\")\n",
    "            \n",
    "    def isEmpty(self):\n",
    "        \"\"\"\n",
    "        Returns (Boolean) if the stack is empty\n",
    "        \"\"\"\n",
    "        return self._height==0\n",
    "    \n",
    "    def draw(self):\n",
    "        \"\"\"\n",
    "        Prints the stack structure as a vertical representation \n",
    "        \"\"\"\n",
    "        if self.isEmpty():\n",
    "            pass\n",
    "            return None\n",
    "        else:\n",
    "            print(\"=\"*15)\n",
    "            n=self._height\n",
    "            print('['+str(self._items[n-1])+']')\n",
    "            for i in range(n-2,-1,-1):\n",
    "                print(\" | \")\n",
    "                print('['+str(self._items[i])+']')\n",
    "            print(\"=\"*15)\n",
    "    \n",
    "    def height(self):\n",
    "        \"\"\"\n",
    "        Returns stack height\n",
    "        \"\"\"\n",
    "        return (self._height)\n",
    "    \n",
    "    def __str__(self):\n",
    "        \"\"\"\n",
    "        Returns stack name to print method\n",
    "        \"\"\"\n",
    "        return (self._name)\n",
    "    \n",
    "    def set_verbosity(self,boolean):\n",
    "        \"\"\"\n",
    "        Sets the verbosity of the stack operation\n",
    "        \"\"\"\n",
    "        self._verbose=boolean"
   ]
  },
  {
   "cell_type": "code",
<<<<<<< HEAD
   "execution_count": null,
   "metadata": {},
   "outputs": [],
=======
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "===============\n",
      "[10]\n",
      " | \n",
      "[8]\n",
      " | \n",
      "[6]\n",
      " | \n",
      "[4]\n",
      " | \n",
      "[2]\n",
      " | \n",
      "[start]\n",
      "===============\n"
     ]
    }
   ],
>>>>>>> 8fd55a64ed3aa6820e41d3d04064e62a93184ac4
   "source": [
    "s=Stack('start',name='TestStack')\n",
    "for i in range(2,12,2):\n",
    "    s.push(i)\n",
    "s.draw()"
   ]
  },
  {
   "cell_type": "code",
<<<<<<< HEAD
   "execution_count": null,
   "metadata": {},
   "outputs": [],
=======
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "===============\n",
      "[6]\n",
      " | \n",
      "[4]\n",
      " | \n",
      "[2]\n",
      " | \n",
      "[start]\n",
      "===============\n"
     ]
    }
   ],
>>>>>>> 8fd55a64ed3aa6820e41d3d04064e62a93184ac4
   "source": [
    "s.pop()\n",
    "s.pop()\n",
    "s.draw()"
   ]
  },
  {
   "cell_type": "code",
<<<<<<< HEAD
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
=======
   "execution_count": 4,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "===============\n",
      "[start]\n",
      "===============\n",
      "===============\n",
      "[2]\n",
      " | \n",
      "[start]\n",
      "===============\n",
      "===============\n",
      "[4]\n",
      " | \n",
      "[2]\n",
      " | \n",
      "[start]\n",
      "===============\n",
      "===============\n",
      "[6]\n",
      " | \n",
      "[4]\n",
      " | \n",
      "[2]\n",
      " | \n",
      "[start]\n",
      "===============\n",
      "===============\n",
      "[8]\n",
      " | \n",
      "[6]\n",
      " | \n",
      "[4]\n",
      " | \n",
      "[2]\n",
      " | \n",
      "[start]\n",
      "===============\n",
      "===============\n",
      "[10]\n",
      " | \n",
      "[8]\n",
      " | \n",
      "[6]\n",
      " | \n",
      "[4]\n",
      " | \n",
      "[2]\n",
      " | \n",
      "[start]\n",
      "===============\n",
      "===============\n",
      "[8]\n",
      " | \n",
      "[6]\n",
      " | \n",
      "[4]\n",
      " | \n",
      "[2]\n",
      " | \n",
      "[start]\n",
      "===============\n",
      "===============\n",
      "[6]\n",
      " | \n",
      "[4]\n",
      " | \n",
      "[2]\n",
      " | \n",
      "[start]\n",
      "===============\n",
      "===============\n",
      "[4]\n",
      " | \n",
      "[2]\n",
      " | \n",
      "[start]\n",
      "===============\n",
      "===============\n",
      "[100]\n",
      " | \n",
      "[4]\n",
      " | \n",
      "[2]\n",
      " | \n",
      "[start]\n",
      "===============\n",
      "===============\n",
      "[2]\n",
      " | \n",
      "[start]\n",
      "===============\n",
      "===============\n",
      "[7]\n",
      " | \n",
      "[5]\n",
      " | \n",
      "[3]\n",
      " | \n",
      "[2]\n",
      " | \n",
      "[start]\n",
      "===============\n",
      "===============\n",
      "[7]\n",
      " | \n",
      "[5]\n",
      " | \n",
      "[3]\n",
      " | \n",
      "[2]\n",
      " | \n",
      "[start]\n",
      "===============\n"
     ]
    }
   ],
>>>>>>> 8fd55a64ed3aa6820e41d3d04064e62a93184ac4
   "source": [
    "s=Stack('start',name='TestStack')\n",
    "s.draw()\n",
    "for i in range(2,12,2):\n",
    "    s.push(i)\n",
    "    s.draw()\n",
    "for i in range(3):\n",
    "    s.pop()\n",
    "    s.draw()\n",
    "s.push(100)\n",
    "s.draw()\n",
    "s.pop()\n",
    "s.pop()\n",
    "s.draw()\n",
    "s.push([3,5,7])\n",
    "s.draw()\n",
    "s.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Queue"
   ]
  },
  {
   "cell_type": "code",
<<<<<<< HEAD
   "execution_count": null,
=======
   "execution_count": 5,
>>>>>>> 8fd55a64ed3aa6820e41d3d04064e62a93184ac4
   "metadata": {},
   "outputs": [],
   "source": [
    "class Queue:\n",
    "    \"\"\"\n",
    "    Queue data structure using list\n",
    "    \"\"\"\n",
    "    def __init__(self,value=None,name=None,verbose=False):\n",
    "        \"\"\"\n",
    "        Class initializer: Produces a queue with a single value or a list of values\n",
    "        value: The initial value. Could be a list of a single item.\n",
    "        name: Optional name for the queue.\n",
    "        verbose: Boolean. Determines if each queue operation prints the item being pushed or popped.\n",
    "        \"\"\"\n",
    "        self._items = []\n",
    "        self._length=0\n",
    "        self._verbose=verbose\n",
    "        \n",
    "        if value!=None:            \n",
    "            if type(value)==list:\n",
    "                for v in value:\n",
    "                    self._items.append(v)\n",
    "                self._length = len(value)\n",
    "            else:\n",
    "                self._items.append(value)\n",
    "                self._length = 1\n",
    "        else:\n",
    "            print(\"Empty queue created.\")\n",
    "        \n",
    "        if name!=None:\n",
    "            self._name=str(name)\n",
    "        else:\n",
    "            self._name=''\n",
    "        \n",
    "    def dequeue(self):\n",
    "        if self._length == 0:\n",
    "            print (\"Queue is empty. Nothing to pop.\")\n",
    "            return None\n",
    "        else:\n",
    "            self._length -=1\n",
    "            item=self._items.pop(0)\n",
    "            if self._verbose:\n",
    "                print(\"{} dequeued\".format(item))\n",
    "            return item\n",
    "    \n",
    "    def enqueue(self,value=None):\n",
    "        \"\"\"\n",
    "        Pushes a a single value or a list of values onto the queue\n",
    "        \"\"\"\n",
    "        if value!=None:            \n",
    "            if type(value)==list:\n",
    "                for v in value:\n",
    "                    self._items.append(v)\n",
    "                    if self._verbose:\n",
    "                        print(\"{} enqueued\".format(v))\n",
    "                self._length += len(value)\n",
    "            else:\n",
    "                self._length +=1\n",
    "                self._items.append(value)\n",
    "                if self._verbose:\n",
    "                        print(\"{} enqueued\".format(value))\n",
    "        else:\n",
    "            if self._verbose:\n",
    "                print(\"No value supplied, nothing was enqueued.\")\n",
    "            \n",
    "    def isEmpty(self):\n",
    "        \"\"\"\n",
    "        Returns (Boolean) if the queue is empty\n",
    "        \"\"\"\n",
    "        return self._length==0\n",
    "    \n",
    "    def draw(self):\n",
    "        if self.isEmpty():\n",
    "            pass\n",
    "            return None\n",
    "        else:\n",
    "            n=self._length\n",
    "            for i in range(n-1):\n",
    "                print('['+str(self._items[i])+']-',end='')\n",
    "            print('['+str(self._items[n-1])+']')\n",
    "    \n",
    "    def length(self):\n",
    "        \"\"\"\n",
    "        Returns queue height\n",
    "        \"\"\"\n",
    "        return (self._length)\n",
    "    \n",
    "    def __str__(self):\n",
    "        \"\"\"\n",
    "        Returns queue name to print method\n",
    "        \"\"\"\n",
    "        return (self._name)\n",
    "    \n",
    "    def set_verbosity(self,boolean):\n",
    "        \"\"\"\n",
    "        Sets the verbosity of the queue operation\n",
    "        \"\"\"\n",
    "        self._verbose=boolean"
   ]
  },
  {
   "cell_type": "code",
<<<<<<< HEAD
   "execution_count": null,
=======
   "execution_count": 6,
>>>>>>> 8fd55a64ed3aa6820e41d3d04064e62a93184ac4
   "metadata": {},
   "outputs": [],
   "source": [
    "q=Queue([2,3,6],verbose=True)"
   ]
  },
  {
   "cell_type": "code",
<<<<<<< HEAD
   "execution_count": null,
   "metadata": {},
   "outputs": [],
=======
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.Queue at 0x165b0b74240>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
>>>>>>> 8fd55a64ed3aa6820e41d3d04064e62a93184ac4
   "source": [
    "q"
   ]
  },
  {
   "cell_type": "code",
<<<<<<< HEAD
   "execution_count": null,
   "metadata": {},
   "outputs": [],
=======
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2]-[3]-[6]\n"
     ]
    }
   ],
>>>>>>> 8fd55a64ed3aa6820e41d3d04064e62a93184ac4
   "source": [
    "q.draw()"
   ]
  },
  {
   "cell_type": "code",
<<<<<<< HEAD
   "execution_count": null,
   "metadata": {},
   "outputs": [],
=======
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 enqueued\n"
     ]
    }
   ],
>>>>>>> 8fd55a64ed3aa6820e41d3d04064e62a93184ac4
   "source": [
    "q.enqueue(10)"
   ]
  },
  {
   "cell_type": "code",
<<<<<<< HEAD
   "execution_count": null,
   "metadata": {},
   "outputs": [],
=======
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2]-[3]-[6]-[10]\n"
     ]
    }
   ],
>>>>>>> 8fd55a64ed3aa6820e41d3d04064e62a93184ac4
   "source": [
    "q.draw()"
   ]
  },
  {
   "cell_type": "code",
<<<<<<< HEAD
   "execution_count": null,
   "metadata": {},
   "outputs": [],
=======
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 dequeued\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
>>>>>>> 8fd55a64ed3aa6820e41d3d04064e62a93184ac4
   "source": [
    "q.dequeue()"
   ]
  },
  {
   "cell_type": "code",
<<<<<<< HEAD
   "execution_count": null,
   "metadata": {},
   "outputs": [],
=======
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "No value supplied, nothing was enqueued.\n"
     ]
    }
   ],
>>>>>>> 8fd55a64ed3aa6820e41d3d04064e62a93184ac4
   "source": [
    "q.enqueue()"
   ]
  },
  {
   "cell_type": "code",
<<<<<<< HEAD
   "execution_count": null,
   "metadata": {},
   "outputs": [],
=======
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100 enqueued\n",
      "101 enqueued\n",
      "102 enqueued\n",
      "103 enqueued\n",
      "[3]-[6]-[10]-[100]-[101]-[102]-[103]\n"
     ]
    }
   ],
>>>>>>> 8fd55a64ed3aa6820e41d3d04064e62a93184ac4
   "source": [
    "for i in range(100,104):\n",
    "    q.enqueue(i)\n",
    "q.draw()"
   ]
  },
  {
   "cell_type": "code",
<<<<<<< HEAD
   "execution_count": null,
   "metadata": {},
   "outputs": [],
=======
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 dequeued\n",
      "6 dequeued\n",
      "10 dequeued\n",
      "[100]-[101]-[102]-[103]\n"
     ]
    }
   ],
>>>>>>> 8fd55a64ed3aa6820e41d3d04064e62a93184ac4
   "source": [
    "for i in range(100,103):\n",
    "    q.dequeue()\n",
    "q.draw()"
   ]
  },
  {
<<<<<<< HEAD
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
=======
>>>>>>> 8fd55a64ed3aa6820e41d3d04064e62a93184ac4
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Tree"
   ]
  },
  {
   "cell_type": "code",
<<<<<<< HEAD
   "execution_count": 51,
=======
   "execution_count": 15,
>>>>>>> 8fd55a64ed3aa6820e41d3d04064e62a93184ac4
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    def __init__(self,data=None):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.data = data\n",
    "    \n",
    "    def printNode(self):\n",
    "        print(self.data)\n",
    "        \n",
    "    def insert(self, data):\n",
    "        if self.data:\n",
    "            if data < self.data:\n",
    "                if self.left is None:\n",
    "                    self.left = Node(data)\n",
    "                else:\n",
    "                    self.left.insert(data)\n",
    "            elif data > self.data:\n",
    "                if self.right is None:\n",
    "                    self.right = Node(data)\n",
    "                else:\n",
    "                    self.right.insert(data)\n",
    "        else:\n",
    "            self.data = data\n",
    "    \n",
    "    def PrintTree(self):\n",
    "        if self.left:\n",
    "            self.left.PrintTree()\n",
    "        print( self.data),\n",
    "        if self.right:\n",
    "            self.right.PrintTree()"
   ]
  },
  {
   "cell_type": "code",
<<<<<<< HEAD
   "execution_count": 52,
=======
   "execution_count": 16,
>>>>>>> 8fd55a64ed3aa6820e41d3d04064e62a93184ac4
   "metadata": {},
   "outputs": [],
   "source": [
    "bst=Node(10)"
   ]
  },
  {
   "cell_type": "code",
<<<<<<< HEAD
   "execution_count": 53,
=======
   "execution_count": 17,
>>>>>>> 8fd55a64ed3aa6820e41d3d04064e62a93184ac4
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
<<<<<<< HEAD
       "<__main__.Node at 0x1658c0b9198>"
      ]
     },
     "execution_count": 53,
=======
       "<__main__.Node at 0x165b0b61048>"
      ]
     },
     "execution_count": 17,
>>>>>>> 8fd55a64ed3aa6820e41d3d04064e62a93184ac4
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bst"
   ]
  },
  {
   "cell_type": "code",
<<<<<<< HEAD
   "execution_count": 54,
=======
   "execution_count": 18,
>>>>>>> 8fd55a64ed3aa6820e41d3d04064e62a93184ac4
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n"
     ]
    }
   ],
   "source": [
    "bst.printNode()"
   ]
  },
  {
   "cell_type": "code",
<<<<<<< HEAD
   "execution_count": 55,
=======
   "execution_count": 19,
>>>>>>> 8fd55a64ed3aa6820e41d3d04064e62a93184ac4
   "metadata": {},
   "outputs": [],
   "source": [
    "bst.insert(6)"
   ]
  },
  {
   "cell_type": "code",
<<<<<<< HEAD
   "execution_count": 56,
=======
   "execution_count": 20,
>>>>>>> 8fd55a64ed3aa6820e41d3d04064e62a93184ac4
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
<<<<<<< HEAD
     "execution_count": 56,
=======
     "execution_count": 20,
>>>>>>> 8fd55a64ed3aa6820e41d3d04064e62a93184ac4
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bst.left.data"
   ]
  },
  {
   "cell_type": "code",
<<<<<<< HEAD
   "execution_count": 57,
=======
   "execution_count": 21,
>>>>>>> 8fd55a64ed3aa6820e41d3d04064e62a93184ac4
   "metadata": {},
   "outputs": [],
   "source": [
    "bst.insert(2)"
   ]
  },
  {
   "cell_type": "code",
<<<<<<< HEAD
   "execution_count": 58,
=======
   "execution_count": 22,
>>>>>>> 8fd55a64ed3aa6820e41d3d04064e62a93184ac4
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "6\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "bst.PrintTree()"
   ]
<<<<<<< HEAD
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
=======
>>>>>>> 8fd55a64ed3aa6820e41d3d04064e62a93184ac4
  }
 ],
 "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.6.2"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}