udemy/algorithms-and-data-structures-in-python/data_structures_stacks_and_queues.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Data Structures - Stacks and Queues\n",
    "\n",
    "### 4.1 Stack\n",
    "\n",
    "#### Stack Introduction\n",
    "+ Abstract data type (interface)\n",
    "+ Basic operations: `pop()`, `push()`, and `peek()`\n",
    "    + `push()`: adds the given item to the top, taking `O(1)`\n",
    "    + `pop()`: removes the last item from the top, taking `O(1)`\n",
    "    + `peek()`: returns the last item from the top, taking `O(1)`\n",
    "+ **LIFO** structure: **L**ast **I**n **F**irst **O**ut\n",
    "+ Easily implemented either with arrays or linked lists\n",
    "+ Applications\n",
    "    + Graph algorithms such as depth-first search\n",
    "    + Finding Euler-cycles in a graph\n",
    "    + Finding strongly connected components in a graph\n",
    "\n",
    "#### Stack in Memory Management (Stacks and Heaps)\n",
    "+ Stack memory: automatically manages local variables\n",
    "+ Heap memory: manages reference types and objects, needs to deallocate\n",
    "+ Summary:\n",
    "\n",
    "```python\n",
    "| Management   | Stack Memory               | Heap Memory            |\n",
    "| ------------ | -------------------------- | ---------------------- | \n",
    "| size         | limited                    | no limits              |\n",
    "| access       | fast                       | slow                   |\n",
    "| storage      | local variables            | objects and references |\n",
    "| if full      | managed efficiently by CPU | may be fragmented      |\n",
    "| resizability | unresizable                | resizable              |\n",
    "```\n",
    "\n",
    "#### Stack and Recursive Method Calls\n",
    "+ Recursive methods: DFS, traversing a binary search tree, searching an item in a linked list\n",
    "+ They can be transfromed into a simple method with stacks\n",
    "+ If we use recursion, CPU will use stacks anyway\n",
    "+ factorial example:\n",
    "\n",
    "```python\n",
    "def factorial(num):\n",
    "    if num < 1:\n",
    "        return 1\n",
    "    return num * factorial(num-1)\n",
    "\n",
    "factorial(5)\n",
    "\n",
    "| return 1         |\n",
    "| 2 * factorial(1) |\n",
    "| 3 * factorial(2) |\n",
    "| 4 * factorial(3) |\n",
    "| 5 * factorial(4) |\n",
    "| factorial(5)     |\n",
    "```\n",
    "\n",
    "#### Stack Implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Stack(object):\n",
    "\n",
    "    def __init__(self):\n",
    "        self.stack = []\n",
    "        self.size = 0\n",
    "        \n",
    "    def is_empty(self):\n",
    "        return self.size == 0\n",
    "    \n",
    "    def push(self, data):\n",
    "        self.stack.insert(self.size, data)\n",
    "        # == self.stack.append(data)\n",
    "        self.size += 1\n",
    "        \n",
    "    def pop(self):\n",
    "        self.size -= 1\n",
    "        self.stack.pop(self.size)\n",
    "        \n",
    "    def peek(self):\n",
    "        return self.stack[self.size-1]\n",
    "        \n",
    "    def get_size(self):\n",
    "        return self.size\n",
    "    \n",
    "    def get_items(self):\n",
    "        return self.stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Stack is empty: True\n",
      "Items in stack: [0, 1, 2, 3, 4]\n",
      "Size of stack: 5\n",
      "Items in stack: [0, 1, 2, 3]\n",
      "Size of stack: 4\n",
      "Last item in stack: 3\n",
      "Stack is empty: False\n"
     ]
    }
   ],
   "source": [
    "# Instantiate\n",
    "stack = Stack()\n",
    "\n",
    "# Check whether stack is empty\n",
    "print 'Stack is empty: {}'.format(stack.is_empty())\n",
    "\n",
    "# Push from 0 to 4\n",
    "for i in range(5):\n",
    "    stack.push(i)\n",
    "    \n",
    "# Get items and size   \n",
    "print 'Items in stack: {}'.format(stack.get_items())\n",
    "print 'Size of stack: {}'.format(stack.get_size())\n",
    "\n",
    "# Pop the last item\n",
    "stack.pop()\n",
    "print 'Items in stack: {}'.format(stack.get_items())\n",
    "print 'Size of stack: {}'.format(stack.get_size())\n",
    "\n",
    "# Peek the last item\n",
    "print 'Last item in stack: {}'.format(stack.peek())\n",
    "\n",
    "# Check whether stack is empty\n",
    "print 'Stack is empty: {}'.format(stack.is_empty())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.2 Queue\n",
    "\n",
    "#### Queue Introduction\n",
    "+ Abstract data type (interface)\n",
    "+ Basic operations: `enqueue()`, `dequeue()`, and `peek()`\n",
    "    + `enqueue()`: adds the given item to the end, taking `O(1)`\n",
    "    + `dequeue()`: removes the item at the beginning, taking `O(1)`\n",
    "    + `peek()`: returns the item at the beginning, taking `O(1)`\n",
    "+ **FIFO** structure: **F**irst **I**n **F**irst **O**ut\n",
    "+ Easily implemented with dynamic arrays as well as linked lists\n",
    "+ Applications:\n",
    "    + CPU scheduling\n",
    "    + Asynchronous data transfer (*e.g.* IO buffers)\n",
    "    + Operational research applications or stochastic models\n",
    "    + Important when implementing BFS algorithm for graphs\n",
    "\n",
    "\n",
    "#### Queue Implementation\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Queue(object):\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.queue = []\n",
    "        self.size = 0\n",
    "        \n",
    "    def is_empty(self):\n",
    "        return self.size == 0\n",
    "    \n",
    "    def enqueue(self, data):\n",
    "        self.queue.insert(0, data)\n",
    "        self.size += 1\n",
    "        \n",
    "    def dequeue(self):\n",
    "        self.size -= 1\n",
    "        self.queue.pop(self.size)\n",
    "        \n",
    "    def peek(self):\n",
    "        return self.queue[self.size-1]\n",
    "        \n",
    "    def get_size(self):\n",
    "        return self.size\n",
    "    \n",
    "    def get_items(self):\n",
    "        return self.queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Queue is empty: True\n",
      "Items in queue: [4, 3, 2, 1, 0]\n",
      "Size of queue: 5\n",
      "Items in queue: [4, 3, 2, 1]\n",
      "Size of queue: 4\n",
      "First item in queue: 1\n",
      "Queue is empty: False\n"
     ]
    }
   ],
   "source": [
    "# Instantiate\n",
    "queue = Queue()\n",
    "\n",
    "# Check whether stack is empty\n",
    "print 'Queue is empty: {}'.format(queue.is_empty())\n",
    "\n",
    "# Enqueue from 0 to 4\n",
    "for i in range(5):\n",
    "    queue.enqueue(i)\n",
    "    \n",
    "# Get items and size   \n",
    "print 'Items in queue: {}'.format(queue.get_items())\n",
    "print 'Size of queue: {}'.format(queue.get_size())\n",
    "\n",
    "# Pop the last item\n",
    "queue.dequeue()\n",
    "print 'Items in queue: {}'.format(queue.get_items())\n",
    "print 'Size of queue: {}'.format(queue.get_size())\n",
    "\n",
    "# Peek the last item\n",
    "print 'First item in queue: {}'.format(queue.peek())\n",
    "\n",
    "# Check whether stack is empty\n",
    "print 'Queue is empty: {}'.format(queue.is_empty())"
   ]
  }
 ],
 "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}