Basic Data Structures.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Implementing a Stack in Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## class Stack:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* __init__: constructor\n",
    "* isEmpty: check if the stack is empty\n",
    "* push: add element at the top\n",
    "* pop: remove element at the top\n",
    "* peek: look at the top element\n",
    "* size: size of stack\n",
    "\n",
    "We implement Stack by list in the following."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self.items=[]\n",
    "        \n",
    "    def isEmpty(self):\n",
    "        return self.items==[]\n",
    "        \n",
    "    def push(self,e):\n",
    "        self.items.append(e)\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)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "a=Stack()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.push(3)\n",
    "a.push(4)\n",
    "a.push(5)\n",
    "a.pop()\n",
    "a.pop()\n",
    "a.pop()\n",
    "a.isEmpty()\n",
    "a.size()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stack application: Simple balanced parentheses"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def parChecker(parentheses):\n",
    "    s=Stack()\n",
    "    for i in range(len(parentheses)):\n",
    "        if(parentheses[i]==\"(\"):\n",
    "            s.push(parentheses[i])\n",
    "        if(parentheses[i]==\")\"):\n",
    "            if(not s.isEmpty()):\n",
    "                s.pop()\n",
    "            else:\n",
    "                return False\n",
    "    return s.isEmpty()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "parChecker(\"(()()()()()))))\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stack application: Converting Decimal numbers to Binary numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=http://interactivepython.org/runestone/static/pythonds/_images/dectobin.png \\>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def divideBy2(decNum):\n",
    "    s=Stack()\n",
    "    \n",
    "    while(decNum>0):\n",
    "        rem=decNum%2\n",
    "        s.push(str(rem))\n",
    "        decNum=decNum/2\n",
    "    \n",
    "    output=\"\"\n",
    "    while(not s.isEmpty()):\n",
    "        output+=s.pop()\n",
    "        \n",
    "    return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'11101001'"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "divideBy2(233)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stack application: Infix, Prefix and Postfix Expressions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## class Queue:\n",
    "\n",
    "* __init__: constructor\n",
    "* isEmpty: check if queue has element\n",
    "* enqueue: add element at the end of the queue\n",
    "* dequeue: remove element from the end of the queue\n",
    "* size: return the number of elements in the queue\n",
    "\n",
    "We implement the queue by a list in the following"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self.items=[]\n",
    "        \n",
    "    def isEmpty(self):\n",
    "        return self.items==[]\n",
    "        \n",
    "    def enqueue(self,e):\n",
    "        self.items.append(e)\n",
    "        \n",
    "    def dequeue(self):\n",
    "        return self.items.pop(0)\n",
    "        \n",
    "    def size(self):\n",
    "        return len(self.items)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q=Queue()\n",
    "q.enqueue(\"a\")\n",
    "q.enqueue(\"b\")\n",
    "q.enqueue(\"c\")\n",
    "print q.size()\n",
    "q.dequeue()\n",
    "q.dequeue()\n",
    "q.dequeue()\n",
    "q.isEmpty()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Queue application: Hot Potato"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this game (see Figure) children line up in a circle and pass an item from neighbor to neighbor as fast as they can. At a certain point in the game, the action is stopped and the child who has the item (the potato) is removed from the circle. Play continues until only one child is left.\n",
    "\n",
    "<img src=http://interactivepython.org/runestone/static/pythonds/_images/hotpotato.png \\>\n",
    "\n",
    "To simulate the circle, we will use a queue (see Figure 3). Assume that the child holding the potato will be at the front of the queue. Upon passing the potato, the simulation will simply dequeue and then immediately enqueue that child, putting her at the end of the line. She will then wait until all the others have been at the front before it will be her turn again. After num dequeue/enqueue operations, the child at the front will be removed permanently and another cycle will begin. This process will continue until only one name remains (the size of the queue is 1).\n",
    "\n",
    "<img src=http://interactivepython.org/runestone/static/pythonds/_images/namequeue.png \\>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def hotPotato(namelist, num):\n",
    "    q = Queue()\n",
    "    # construct queue\n",
    "    for e in namelist:\n",
    "        q.enqueue(e)\n",
    "        \n",
    "    while(q.size()>1):\n",
    "        for i in range(num):\n",
    "            q.enqueue(q.dequeue())\n",
    "        q.dequeue()\n",
    "    \n",
    "    return q.dequeue()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Jane\n"
     ]
    }
   ],
   "source": [
    "print hotPotato([\"Bill\",\"David\",\"Susan\",\"Jane\",\"Kent\",\"Brad\"],5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementing an Unordered List: Linked Lists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Node class"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self,initdata):\n",
    "        self.data=initdata\n",
    "        self.next=None\n",
    "        \n",
    "    def getData(self):\n",
    "        return self.data\n",
    "        \n",
    "    def getNext(self):\n",
    "        return self.next\n",
    "        \n",
    "    def setData(self,newdata):\n",
    "        self.data=newdata\n",
    "        \n",
    "    def setNext(self,newnext):\n",
    "        self.next=newnext"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LinkedList\n",
    "\n",
    "* __init__: constructor\n",
    "* isEmpty: check if the list is empty\n",
    "* add: add an element at the end\n",
    "* remove: remove an element at the end\n",
    "* printlist: check linkedlist by printing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=http://interactivepython.org/runestone/static/pythonds/_images/linkedlist.png \\>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class UnorderedList:\n",
    "    def __init__(self):\n",
    "        self.head=None\n",
    "        \n",
    "    def isEmpty(self):\n",
    "        return self.head==None\n",
    "        \n",
    "    def add(self,item):\n",
    "        if(self.isEmpty()):\n",
    "            self.head=Node(item)\n",
    "        else:\n",
    "            current=self.head\n",
    "            while(current.next!=None):\n",
    "                current=current.next\n",
    "            current.next=Node(item)\n",
    "                    \n",
    "    def remove(self,item):\n",
    "        found=False\n",
    "        current=self.head\n",
    "        if(self.head.getData()==item):\n",
    "            found=True\n",
    "            temp=self.head\n",
    "            self.head=self.head.next\n",
    "            temp=None\n",
    "            \n",
    "        while(found==False and current.next!=None):            \n",
    "            if(current.next.getData()==item):\n",
    "                found=True\n",
    "                temp=current.next\n",
    "                current.next=current.next.next\n",
    "                temp=None\n",
    "                \n",
    "            current=current.next\n",
    "                \n",
    "        return found\n",
    "    \n",
    "    def printList(self):\n",
    "        LL=[]\n",
    "        current=self.head\n",
    "        while(current!=None):\n",
    "            LL.append(current.getData())\n",
    "            current=current.next\n",
    "        return LL    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "LL=UnorderedList()\n",
    "LL.add(\"a\")\n",
    "LL.add(\"b\")\n",
    "LL.add(\"c\")\n",
    "LL.add(\"d\")\n",
    "LL.remove(\"a\")\n",
    "LL.remove(\"d\")\n",
    "LL.remove(\"c\")\n",
    "LL.remove(\"b\")\n",
    "print LL.isEmpty()\n",
    "LL.printList()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## The Deque Abstract Data Type"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The deque abstract data type is defined by the following structure and operations. A deque is structured, as described above, as an ordered collection of items **where items are added and removed from either end, either front or rear**. The deque operations are given below.\n",
    "\n",
    "* Deque() creates a new deque that is empty. It needs no parameters and returns an empty deque.\n",
    "* addFront(item) adds a new item to the front of the deque. It needs the item and returns nothing.\n",
    "* addRear(item) adds a new item to the rear of the deque. It needs the item and returns nothing.\n",
    "* removeFront() removes the front item from the deque. It needs no parameters and returns the item. The deque is modified.\n",
    "* removeRear() removes the rear item from the deque. It needs no parameters and returns the item. The deque is modified.\n",
    "* isEmpty() tests to see whether the deque is empty. It needs no parameters and returns a boolean value.\n",
    "* size() returns the number of items in the deque. It needs no parameters and returns an integer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementing a Deque in Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we have done in previous sections, we will create a new class for the implementation of the abstract data type deque. Again, the Python list will provide a very nice set of methods upon which to build the details of the deque. Our implementation (Listing 1) will assume that the rear of the deque is at position 0 in the list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Deque:\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "\n",
    "    def isEmpty(self):\n",
    "        return 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)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Palindrome-Checker"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=http://interactivepython.org/runestone/static/pythonds/_images/palindromesetup.png \\>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def palchecker(astring):\n",
    "    d=Deque()\n",
    "    for c in astring:\n",
    "        d.addRear(c)\n",
    "    while d.size()>1:\n",
    "        if(d.removeFront()!=d.removeRear()):\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "palchecker('radar')\n",
    "palchecker('lsdkjfskf')\n",
    "palchecker('adlsdkjfskfda')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}