{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Stacks, Queues & Heaps\n",
    "© Joe James, 2019.\n",
    "\n",
    "### Stack using Python List\n",
    "Stack is a LIFO data structure -- last-in, first-out.  \n",
    "Use append() to push an item onto the stack.  \n",
    "Use pop() to remove an item."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[4, 7, 12, 19]\n"
     ]
    }
   ],
   "source": [
    "my_stack = list()\n",
    "my_stack.append(4)\n",
    "my_stack.append(7)\n",
    "my_stack.append(12)\n",
    "my_stack.append(19)\n",
    "print(my_stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "19\n",
      "12\n",
      "[4, 7]\n"
     ]
    }
   ],
   "source": [
    "print(my_stack.pop())\n",
    "print(my_stack.pop())\n",
    "print(my_stack)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Stack using List with a Wrapper Class\n",
    "We create a Stack class and a full set of Stack methods.  \n",
    "But the underlying data structure is really a Python List.  \n",
    "For pop and peek methods we first check whether the stack is empty, to avoid exceptions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Stack():\n",
    "    def __init__(self):\n",
    "        self.stack = list()\n",
    "    def push(self, item):\n",
    "        self.stack.append(item)\n",
    "    def pop(self):\n",
    "        if len(self.stack) > 0:\n",
    "            return self.stack.pop()\n",
    "        else:\n",
    "            return None\n",
    "    def peek(self):\n",
    "        if len(self.stack) > 0:\n",
    "            return self.stack[len(self.stack)-1]\n",
    "        else:\n",
    "            return None\n",
    "    def __str__(self):\n",
    "        return str(self.stack)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Test Code for Stack Wrapper Class"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 3]\n",
      "3\n",
      "1\n",
      "1\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "my_stack = Stack()\n",
    "my_stack.push(1)\n",
    "my_stack.push(3)\n",
    "print(my_stack)\n",
    "print(my_stack.pop())\n",
    "print(my_stack.peek())\n",
    "print(my_stack.pop())\n",
    "print(my_stack.pop())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "### Queue using Python Deque\n",
    "Queue is a FIFO data structure -- first-in, first-out.  \n",
    "Deque is a double-ended queue, but we can use it for our queue.  \n",
    "We use append() to enqueue an item, and popleft() to dequeue an item.  \n",
    "See [Python docs](https://docs.python.org/3/library/collections.html#collections.deque) for deque."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([5, 10])\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "from collections import deque\n",
    "my_queue = deque()\n",
    "my_queue.append(5)\n",
    "my_queue.append(10)\n",
    "print(my_queue)\n",
    "print(my_queue.popleft())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Fun exercise:\n",
    "Write a wrapper class for the Queue class, similar to what we did for Stack, but using Python deque.  \n",
    "Try adding enqueue, dequeue, and get_size methods."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Python Single-ended Queue Wrapper Class using Deque\n",
    "We rename the append method to enqueue, and popleft to dequeue.  \n",
    "We also add peek and get_size operations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "class Queue():\n",
    "    def __init__(self):\n",
    "        self.queue = deque()\n",
    "        self.size = 0\n",
    "    def enqueue(self, item):\n",
    "        self.queue.append(item)\n",
    "        self.size += 1\n",
    "    def dequeue(self, item):\n",
    "        if self.size > 0:\n",
    "            self.size -= 1\n",
    "            return self.queue.popleft()\n",
    "        else: \n",
    "            return None\n",
    "    def peek(self):\n",
    "        if self.size > 0:\n",
    "            ret_val = self.queue.popleft()\n",
    "            queue.appendleft(ret_val)\n",
    "            return ret_val\n",
    "        else:\n",
    "            return None\n",
    "    def get_size(self):\n",
    "        return self.size"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Python MaxHeap\n",
    "A MaxHeap always bubbles the highest value to the top, so it can be removed instantly.  \n",
    "Public functions: push, peek, pop  \n",
    "Private functions: __swap, __floatUp, __bubbleDown, __str__."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MaxHeap:\n",
    "    def __init__(self, items=[]):\n",
    "        super().__init__()\n",
    "        self.heap = [0]\n",
    "        for item in items:\n",
    "            self.heap.append(item)\n",
    "            self.__floatUp(len(self.heap) - 1)\n",
    "\n",
    "    def push(self, data):\n",
    "        self.heap.append(data)\n",
    "        self.__floatUp(len(self.heap) - 1)\n",
    "\n",
    "    def peek(self):\n",
    "        if self.heap[1]:\n",
    "            return self.heap[1]\n",
    "        else:\n",
    "            return False\n",
    "            \n",
    "    def pop(self):\n",
    "        if len(self.heap) > 2:\n",
    "            self.__swap(1, len(self.heap) - 1)\n",
    "            max = self.heap.pop()\n",
    "            self.__bubbleDown(1)\n",
    "        elif len(self.heap) == 2:\n",
    "            max = self.heap.pop()\n",
    "        else: \n",
    "            max = False\n",
    "        return max\n",
    "\n",
    "    def __swap(self, i, j):\n",
    "        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]\n",
    "\n",
    "    def __floatUp(self, index):\n",
    "        parent = index//2\n",
    "        if index <= 1:\n",
    "            return\n",
    "        elif self.heap[index] > self.heap[parent]:\n",
    "            self.__swap(index, parent)\n",
    "            self.__floatUp(parent)\n",
    "\n",
    "    def __bubbleDown(self, index):\n",
    "        left = index * 2\n",
    "        right = index * 2 + 1\n",
    "        largest = index\n",
    "        if len(self.heap) > left and self.heap[largest] < self.heap[left]:\n",
    "            largest = left\n",
    "        if len(self.heap) > right and self.heap[largest] < self.heap[right]:\n",
    "            largest = right\n",
    "        if largest != index:\n",
    "            self.__swap(index, largest)\n",
    "            self.__bubbleDown(largest)\n",
    "            \n",
    "    def __str__(self):\n",
    "        return str(self.heap)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### MaxHeap Test Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 95, 10, 21, 3]\n",
      "95\n",
      "21\n"
     ]
    }
   ],
   "source": [
    "m = MaxHeap([95, 3, 21])\n",
    "m.push(10)\n",
    "print(m)\n",
    "print(m.pop())\n",
    "print(m.peek())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}