Chapter_10_Elementary_Data_Structures/exercises_10.1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 10.1 Stacks and queues"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10.1-1\n",
    "\n",
    "> Using Figure 10.1 as a model, illustrate the result of each operation in the sequence PUSH$(S,4)$, PUSH$(S,1)$, PUSH$(S,3)$, POP$(S)$, PUSH$(S,8)$, and POP$(S)$ on an initially empty stack $S$ stored in array $S[1 \\dots 6]$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](./img/10.1-1_1.png)\n",
    "![](./img/10.1-1_2.png)\n",
    "![](./img/10.1-1_3.png)\n",
    "![](./img/10.1-1_4.png)\n",
    "![](./img/10.1-1_5.png)\n",
    "![](./img/10.1-1_6.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10.1-2\n",
    "\n",
    "> Explain how to implement two stacks in one array $A[1 \\dots n]$ in such a way that neither stack overflows unless the total number of elements in both stacks together is $n$. The PUSH and POP operations should run in $O(1)$ time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 100\n",
    "a = [-1 for _ in range(n)]\n",
    "\n",
    "\n",
    "class Stack1:\n",
    "    def __init__(self):\n",
    "        self.top = -1\n",
    "\n",
    "    def is_empty(self):\n",
    "        return self.top == -1\n",
    "\n",
    "    def push(self, x):\n",
    "        global a\n",
    "        self.top += 1\n",
    "        a[self.top] = x\n",
    "\n",
    "    def pop(self):\n",
    "        global a\n",
    "        self.top -= 1\n",
    "        return a[self.top + 1]\n",
    "\n",
    "\n",
    "class Stack2:\n",
    "    def __init__(self):\n",
    "        self.top = n\n",
    "\n",
    "    def is_empty(self):\n",
    "        return self.top == n\n",
    "\n",
    "    def push(self, x):\n",
    "        global a\n",
    "        self.top -= 1\n",
    "        a[self.top] = x\n",
    "\n",
    "    def pop(self):\n",
    "        global a\n",
    "        self.top += 1\n",
    "        return a[self.top - 1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10.1-3\n",
    "\n",
    "> Using Figure 10.2 as a model, illustrate the result of each operation in the sequence ENQUEUE$(Q,4)$, ENQUEUE$(Q,1)$, ENQUEUE$(Q,3)$, DEQUEUE$(Q)$, ENQUEUE$(Q,8)$, and DEQUEUE$(Q)$ on an initially empty queue $Q$ stored in array $Q[1 \\dots 6]$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](./img/10.1-3_1.png)\n",
    "![](./img/10.1-3_2.png)\n",
    "![](./img/10.1-3_3.png)\n",
    "![](./img/10.1-3_4.png)\n",
    "![](./img/10.1-3_5.png)\n",
    "![](./img/10.1-3_6.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10.1-4\n",
    "\n",
    "> Rewrite ENQUEUE and DEQUEUE to detect underflow and overflow of a queue."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Queue:\n",
    "    def __init__(self, size):\n",
    "        self.q = [-1 for _ in xrange(size)]\n",
    "        self.head = 0\n",
    "        self.tail = 0\n",
    "\n",
    "    def enqueue(self, x):\n",
    "        if (self.tail + 1) % len(self.q) == self.head:\n",
    "            raise Exception('overflow')\n",
    "        self.q[self.tail] = x\n",
    "        self.tail += 1\n",
    "        if self.tail == len(self.q):\n",
    "            self.tail = 0\n",
    "\n",
    "    def dequeue(self):\n",
    "        if self.head == self.tail:\n",
    "            raise Exception('underflow')\n",
    "        x = self.q[self.head]\n",
    "        self.head += 1\n",
    "        if self.head == len(self.q):\n",
    "            self.head = 0\n",
    "        return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10.1-5\n",
    "\n",
    "> Whereas a stack allows insertion and deletion of elements at only one end, and a queue allows insertion at one end and deletion at the other end, a __*deque*__ (doubleended queue) allows insertion and deletion at both ends. Write four $O(1)$-time procedures to insert elements into and delete elements from both ends of a deque implemented by an array."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Deque:\n",
    "    def __init__(self, size):\n",
    "        self.q = [-1 for _ in xrange(size)]\n",
    "        self.front = 0\n",
    "        self.back = 0\n",
    "\n",
    "    def push_front(self, x):\n",
    "        if (self.back + 1) % len(self.q) == self.front:\n",
    "            raise Exception('overflow')\n",
    "        self.front -= 1\n",
    "        if self.front == -1:\n",
    "            self.front = len(self.q) - 1\n",
    "        self.q[self.front] = x\n",
    "\n",
    "    def push_back(self, x):\n",
    "        if (self.back + 1) % len(self.q) == self.front:\n",
    "            raise Exception('overflow')\n",
    "        self.q[self.back] = x\n",
    "        self.back += 1\n",
    "        if self.back == len(self.q):\n",
    "            self.back = 0\n",
    "\n",
    "    def pop_front(self):\n",
    "        if self.front == self.back:\n",
    "            raise Exception('underflow')\n",
    "        x = self.q[self.front]\n",
    "        self.front += 1\n",
    "        if self.front == len(self.q):\n",
    "            self.front = 0\n",
    "        return x\n",
    "\n",
    "    def pop_back(self):\n",
    "        if self.front == self.back:\n",
    "            raise Exception('underflow')\n",
    "        self.back -= 1\n",
    "        if self.back == -1:\n",
    "            self.back = len(self.q) - 1\n",
    "        return self.q[self.back]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10.1-6\n",
    "\n",
    "> Show how to implement a queue using two stacks. Analyze the running time of the queue operations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Enqueue: $\\Theta(1)$. \n",
    "\n",
    "Dequeue: worst $O(n)$, amortized $\\Theta(1)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BlackBoxStack:\n",
    "    def __init__(self):\n",
    "        self.s = []\n",
    "\n",
    "    def is_empty(self):\n",
    "        return len(self.s) == 0\n",
    "\n",
    "    def push(self, x):\n",
    "        self.s.append(x)\n",
    "\n",
    "    def pop(self):\n",
    "        x = self.s[-1]\n",
    "        del self.s[-1]\n",
    "        return x\n",
    "\n",
    "\n",
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self.stack_in = BlackBoxStack()\n",
    "        self.stack_out = BlackBoxStack()\n",
    "\n",
    "    def is_empty(self):\n",
    "        return self.stack_in.is_empty() and self.stack_out.is_empty()\n",
    "\n",
    "    def enqueue(self, x):\n",
    "        self.stack_in.push(x)\n",
    "\n",
    "    def dequeue(self):\n",
    "        if self.stack_out.is_empty():\n",
    "            if self.stack_in.is_empty():\n",
    "                raise Exception('underflow')\n",
    "            while not self.stack_in.is_empty():\n",
    "                self.stack_out.push(self.stack_in.pop())\n",
    "        return self.stack_out.pop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10.1-7\n",
    "\n",
    "> Show how to implement a stack using two queues. Analyze the running time of the stack operations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Push: $\\Theta(1)$. \n",
    "\n",
    "Pop: $\\Theta(n)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BlackBoxQueue:\n",
    "    def __init__(self):\n",
    "        self.s = []\n",
    "\n",
    "    def is_empty(self):\n",
    "        return len(self.s) == 0\n",
    "\n",
    "    def enqueue(self, x):\n",
    "        self.s.append(x)\n",
    "\n",
    "    def dequeue(self):\n",
    "        x = self.s[0]\n",
    "        del self.s[0]\n",
    "        return x\n",
    "\n",
    "\n",
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self.queue_in = BlackBoxQueue()\n",
    "        self.queue_out = BlackBoxQueue()\n",
    "\n",
    "    def is_empty(self):\n",
    "        return self.queue_in.is_empty()\n",
    "\n",
    "    def push(self, x):\n",
    "        self.queue_in.enqueue(x)\n",
    "\n",
    "    def pop(self):\n",
    "        if self.queue_in.is_empty():\n",
    "            raise Exception('underflow')\n",
    "        while True:\n",
    "            x = self.queue_in.dequeue()\n",
    "            if self.queue_in.is_empty():\n",
    "                break\n",
    "            self.queue_out.enqueue(x)\n",
    "        self.queue_in, self.queue_out = self.queue_out, self.queue_in\n",
    "        return x"
   ]
  }
 ],
 "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.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}