implement-stacks-queues-hashes-lists-trees.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# implement stacks, with push/pop functions\n",
    "\n",
    "class stack:\n",
    "    def __init__(self, max_size):\n",
    "        self.items = []\n",
    "        self.max_size = max_size\n",
    "        \n",
    "    def push(self, x):\n",
    "        if len(self.items) < self.max_size:\n",
    "            self.items.append(x)\n",
    "        else: \n",
    "            print('Max size exceeded.')\n",
    "    \n",
    "    def pop(self):\n",
    "        if len(self.items) > 0:\n",
    "            val = self.items[-1]\n",
    "            self.items = self.items[0:-1]\n",
    "            return val\n",
    "        else:\n",
    "            print('Min size violated.')\n",
    "    \n",
    "    def stack_len(self):\n",
    "        return len(self.items)\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Max size exceeded.\n",
      "[4, 10, 3, 0, 8]\n",
      "[4, 10, 3, 0]\n",
      "8\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "mystack = stack(5)\n",
    "\n",
    "mystack.push(4)\n",
    "mystack.push(10)\n",
    "mystack.push(3)\n",
    "mystack.push(0)\n",
    "mystack.push(8)\n",
    "mystack.push(9)\n",
    "print(mystack.items)\n",
    "x = mystack.pop()\n",
    "print(mystack.items)\n",
    "print(x)\n",
    "print(mystack.stack_len())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# implement queues, with enqueue/dequeue\n",
    "\n",
    "class queue:\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "        \n",
    "    def enqueue(self, x):\n",
    "        self.items.append(x)\n",
    "        \n",
    "    def dequeue(self):\n",
    "        val = self.items[0]\n",
    "        self.items = self.items[1:]\n",
    "        return val\n",
    "    \n",
    "    def size(self):\n",
    "        return size(self.items)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[4, 2, 0]\n",
      "[2, 0]\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "myqueue = queue()\n",
    "#print(myqueue.items)\n",
    "\n",
    "myqueue.enqueue(4)\n",
    "myqueue.enqueue(2)\n",
    "myqueue.enqueue(0)\n",
    "print(myqueue.items)\n",
    "\n",
    "x = myqueue.dequeue()\n",
    "print(myqueue.items)\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# implement hash table with hash function, insert and search methods\n",
    "\n",
    "class hashtable:\n",
    "    def __init__(self):\n",
    "        self.table = {}\n",
    "        \n",
    "    def insert(self, insert_value):\n",
    "        if self._hashfunction(insert_value) in self.table:\n",
    "            print('\\nCollision!')\n",
    "        else:\n",
    "            self.table[self._hashfunction(insert_value)] = insert_value\n",
    "        \n",
    "    def _hashfunction(self, value):\n",
    "        return '%03u' % ((value**10) % 1000)\n",
    "    \n",
    "    def search(self, search_value):\n",
    "        if self._hashfunction(search_value) in self.table:\n",
    "            print('\\n%u in table.' % search_value)\n",
    "        else:\n",
    "            print('\\n%u not in table.' % search_value)\n",
    "    \n",
    "    def print_table(self):\n",
    "        for key in self.table:\n",
    "            print('\\n%s: %u' % (key, self.table.get(key)))                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "401: 9\n",
      "\n",
      "176: 94\n",
      "\n",
      "000: 10\n",
      "\n",
      "11 not in table.\n"
     ]
    }
   ],
   "source": [
    "my_table = hashtable()\n",
    "\n",
    "my_table.insert(9)\n",
    "my_table.insert(94)\n",
    "my_table.insert(10)\n",
    "#my_table.insert(100)\n",
    "\n",
    "my_table.print_table()\n",
    "\n",
    "my_table.search(11)\n",
    "\n",
    "#d = {}\n",
    "#d['dog'] = 'labrador'\n",
    "#d['dog'] = 'retriever'\n",
    "\n",
    "#for key in d:\n",
    "#    print('\\n%s : %s' % (key, d[key]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# linked list \n",
    "\n",
    "class Node:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "        \n",
    "    def traverse(self):\n",
    "        node = self\n",
    "        while node != None:\n",
    "            print(node.val)\n",
    "            node = node.next\n",
    "            \n",
    "    def insert(self, x, k):\n",
    "        counter = 0\n",
    "        node = self\n",
    "        while counter < k:\n",
    "            node = node.next\n",
    "            counter += 1\n",
    "        temp = node.next\n",
    "        node.next = Node(x)\n",
    "        node = node.next\n",
    "        node.next = temp\n",
    "        \n",
    "    def reverse(self):\n",
    "        curr = self\n",
    "        prev = self\n",
    "        nextn = curr.next\n",
    "        self.next = None\n",
    "        while nextn != None:\n",
    "            curr = nextn\n",
    "            nextn = curr.next\n",
    "            curr.next = prev\n",
    "            prev = curr\n",
    "        return curr\n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "5\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "node1 = Node(3)\n",
    "node2 = Node(5)\n",
    "node3 = Node(0)\n",
    "\n",
    "node1.next = node2\n",
    "node2.next = node3\n",
    "\n",
    "head = node1\n",
    "#head.traverse()\n",
    "#print(head.next.next.val)\n",
    "\n",
    "#head.insert(4,0)\n",
    "\n",
    "head = head.reverse()\n",
    "\n",
    "head.traverse()\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# binary search trees"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [],
   "source": [
    "# implement a binary search tree class\n",
    "\n",
    "class bst_node:\n",
    "    def __init__(self, val=None):\n",
    "        self.val = val\n",
    "        self.l = None\n",
    "        self.r = None\n",
    "        \n",
    "    def print_crazy(self):\n",
    "        if self.l != None:\n",
    "            node = self.l\n",
    "            node.print_crazy()\n",
    "            print('\\n %u l--> %u' % (self.val, node.val))\n",
    "        else:\n",
    "            l = bst_node()\n",
    "            print('\\n %u l--> None' % self.val)\n",
    "        if self.r != None:\n",
    "            node = self.r\n",
    "            node.print_crazy()\n",
    "            print('\\n %u r--> %u' % (self.val, node.val))\n",
    "        else:\n",
    "            r = bst_node()\n",
    "            print('\\n %u r--> None' % self.val)\n",
    "        \n",
    "    def insert(self, val):\n",
    "        node = self\n",
    "        if val <= node.val:\n",
    "            if node.l == None:\n",
    "                node.l = bst_node(val)\n",
    "            else:\n",
    "                node = node.l\n",
    "                node.insert(val)\n",
    "        else:\n",
    "            if node.r == None:\n",
    "                node.r = bst_node(val)\n",
    "            else:\n",
    "                node = node.r\n",
    "                node.insert(val)\n",
    "    \n",
    "    def search(self, val):\n",
    "        if self.val == val:\n",
    "            print('%u is in the tree.' % val)\n",
    "        elif val <= self.val:\n",
    "            if self.l == None:\n",
    "                print('%u is NOT in the tree.' % val)\n",
    "            else:\n",
    "                l = self.l\n",
    "                print('%u l--> %u' % (self.val, l.val))\n",
    "                l.search(val)\n",
    "        elif val > self.val:\n",
    "            if self.r == None:\n",
    "                print('%u is NOT in the tree.' % val)\n",
    "            else:\n",
    "                r = self.r\n",
    "                print('%u r--> %u' % (self.val, r.val))\n",
    "                r.search(val)\n",
    "        \n",
    "    def traverse_inorder(self):\n",
    "        if self.l != None:\n",
    "            self.l.traverse_inorder()    \n",
    "        print(self.val)\n",
    "        if self.r != None:\n",
    "            self.r.traverse_inorder()\n",
    "    \n",
    "    def traverse_inorder_iterative(self):\n",
    "        stack = []\n",
    "        node = self\n",
    "        while not (node == None and len(stack) == 0):\n",
    "        #for _ in range(6):\n",
    "            if node != None:\n",
    "                stack.append(node)\n",
    "                node = node.l\n",
    "            else:\n",
    "                lastnode = stack.pop()\n",
    "                print(lastnode.val)\n",
    "                #print(stack)\n",
    "                node = lastnode.r        \n",
    "                \n",
    "    def traverse_preorder(self):\n",
    "        if self.val != None:\n",
    "            print(self.val)\n",
    "            if self.l != None:\n",
    "                self.l.traverse_preorder()\n",
    "            if self.r != None:\n",
    "                self.r.traverse_preorder()\n",
    "                \n",
    "    def traverse_postorder(self):\n",
    "        if self.val != None:\n",
    "            if self.l != None:\n",
    "                self.l.traverse_postorder()\n",
    "            if self.r != None:\n",
    "                self.r.traverse_postorder()\n",
    "            print(self.val)\n",
    "                                \n",
    "    def invert(self):\n",
    "        if self.val != None:\n",
    "            if self.l != None:\n",
    "                self.l.invert()\n",
    "            if self.r != None:\n",
    "                self.r.invert()\n",
    "            self.r, self.l = self.l, self.r\n",
    "            print('Swap!')\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "head = bst_node(21)\n",
    "head.insert(11)\n",
    "head.insert(8)\n",
    "head.insert(17)\n",
    "head.insert(34)\n",
    "head.insert(22)\n",
    "head.insert(22)\n",
    "head.insert(39)\n",
    "#head.print_crazy()\n",
    "#head.search(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n",
      "11\n",
      "17\n",
      "21\n",
      "22\n",
      "22\n",
      "34\n",
      "39\n"
     ]
    }
   ],
   "source": [
    "head.traverse_inorder()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n",
      "11\n",
      "17\n",
      "21\n",
      "22\n",
      "22\n",
      "34\n",
      "39\n"
     ]
    }
   ],
   "source": [
    "head.traverse_inorder_iterative()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "21\n",
      "11\n",
      "8\n",
      "17\n",
      "34\n",
      "22\n",
      "22\n",
      "39\n"
     ]
    }
   ],
   "source": [
    "head.traverse_preorder()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n",
      "17\n",
      "11\n",
      "22\n",
      "22\n",
      "39\n",
      "34\n",
      "21\n"
     ]
    }
   ],
   "source": [
    "head.traverse_postorder()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Swap!\n",
      "Swap!\n",
      "Swap!\n",
      "Swap!\n",
      "Swap!\n",
      "Swap!\n",
      "Swap!\n",
      "Swap!\n",
      "39\n",
      "34\n",
      "22\n",
      "22\n",
      "21\n",
      "17\n",
      "11\n",
      "8\n"
     ]
    }
   ],
   "source": [
    "head.invert()\n",
    "head.traverse_inorder()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [default]",
   "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}