stack.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Stacks\n",
    "\n",
    "Stacks are LIFO lists. You can implement Stacks trivially by basing them on a list. A linked list in which you insert at and remove from its beginning has a `push()` and `pop()` complexity of **`O(1)`** without even the need of an additional pointer. In contrast, using an array list, the two operations would be `O(n)` due to the need of copying around values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 size=  6\n",
      "0 10 1 2 3 4 5 size=  7\n",
      "99 0 10 1 2 3 4 5 size=  8\n",
      "99 0 1 2 3 4 5 size=  7\n",
      "99 0 1 2 3 4 5 60 size=  8\n",
      "0 1 2 3 4 5 60 size=  7\n",
      "0 1 2 3 4 5 size=  6\n",
      "0 1 2 3 4 5 60 70 80 90 size=  10\n",
      "increased capacity:  15 , size: 10\n",
      "0 1 2 3 4 5 60 70 80 90 100 size=  11\n",
      "0  1  2  3  4  5  size= 6\n",
      "0  10  1  2  3  4  5  size= 7\n",
      "99  0  10  1  2  3  4  5  900  size= 9\n",
      "99  0  1  2  3  4  5  900  size= 8\n",
      "10\n",
      "99  0  1  2  3  4  5  900  60  size= 9\n",
      "0  1  2  3  4  5  900  60  size= 8\n",
      "0  1  2  3  4  5  900  size= 7\n",
      "2\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "%run array_list.ipynb\n",
    "%run linked_list.ipynb"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MyStack:\n",
    "    def __init__(self):\n",
    "        self.mylist = MyLinkedList()\n",
    "    \n",
    "    def push(self, value):\n",
    "        self.mylist.insert(value,0)\n",
    "        \n",
    "    def pop(self):\n",
    "        return self.mylist.delete(0)\n",
    "    \n",
    "    def is_empty(self):\n",
    "        if (self.mylist.size==0): return True\n",
    "        return False\n",
    "    \n",
    "    def peek(self):\n",
    "        return self.mylist.head.val\n",
    "        \n",
    "    def print_stack(self):\n",
    "        self.mylist.print_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9  8  7  6  5  4  3  2  1  0  size= 10\n"
     ]
    }
   ],
   "source": [
    "mystack = MyStack()\n",
    "\n",
    "for i in range(10):\n",
    "    mystack.push(i)\n",
    "\n",
    "mystack.print_stack()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9 popped\n",
      "8  7  6  5  4  3  2  1  0  size= 9\n"
     ]
    }
   ],
   "source": [
    "a = mystack.pop()\n",
    "print a , \"popped\"\n",
    "mystack.print_stack()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercises\n",
    "\n",
    "#### Write a function which receives a stack and returns a new one with its elements reversed"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0  1  2  3  4  5  6  7  8  size= 9\n"
     ]
    }
   ],
   "source": [
    "revstack = MyStack()\n",
    "for i in range (mystack.mylist.size):\n",
    "    revstack.push(mystack.pop())\n",
    "    \n",
    "revstack.print_stack()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Write a function which removes all even numbers from a stack (return the same stack, not a new one)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(10):\n",
    "    mystack.push(i)\n",
    "    \n",
    "helpstack = MyStack()\n",
    "for i in range (mystack.mylist.size):\n",
    "    a = mystack.pop()\n",
    "    if a%2==1: helpstack.push(a)\n",
    "        \n",
    "for i in range (helpstack.mylist.size):\n",
    "    mystack.push(helpstack.pop())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9 7 5 3 1 size= 5\n"
     ]
    }
   ],
   "source": [
    "mystack.print_stack()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Design a stack with a `min()` function returning its minimum element with complexity **O(1)**\n",
    "\n",
    "You could include a `mimimum` field in the class and update it every time a new value gets pushed. But what happens when a value gets popped? You would need to scan the entire stack to find the min. This tactic would break the O(1) requirement. You need to retain state. Store the minimum with each push under the value that gets pushed. Remove both the value and the minimum below it (which is the minimum at the time the popping value was pushed) every time a pop is requested."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "minimum=5\n",
    "\n",
    "def push_with_min(thestack, value, mini):\n",
    "    minimum=min(value,mini)\n",
    "    thestack.push(minimum)\n",
    "    thestack.push(value)\n",
    "    return minimum\n",
    "    \n",
    "def pop_with_min(thestack, mini):\n",
    "    thestack.pop()\n",
    "    minimum = thestack.pop()\n",
    "    return minimum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3  3  size= 2\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "minstack=MyStack()\n",
    "\n",
    "minimum=push_with_min(minstack, 3, minimum)\n",
    "minstack.print_stack()\n",
    "print minimum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6 3 3 3 size= 4\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "minimum=push_with_min(minstack, 6, minimum)\n",
    "minstack.print_stack()\n",
    "print minimum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 1 6 3 3 3 size= 6\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "minimum=push_with_min(minstack, 1, minimum)\n",
    "minstack.print_stack()\n",
    "print minimum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8 1 1 1 6 3 3 3 size= 8\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "minimum=push_with_min(minstack, 8, minimum)\n",
    "minstack.print_stack()\n",
    "print minimum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 1 6 3 3 3 size= 6\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "minimum=pop_with_min(minstack, minimum)\n",
    "minstack.print_stack()\n",
    "print minimum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Implement a queue by using two stacks"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "pseudocode:\n",
    "\n",
    "stack-1: use it to push stuff\n",
    "stack-2: use it to reverse stack-1 and pop items from it, so as to emulate a queue across the two stacks\n",
    "\n",
    "push(value): #always push to stack-1\n",
    "    stack1.push() \n",
    "    \n",
    "pop(): #always pop from stack-2\n",
    "    if stack-2 is empty: push all elements from stack-1 to stack-2. Then pop it.\n",
    "    if stack-2 is not empty: stack2.pop()\n",
    "    "
   ]
  }
 ],
 "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.15"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}