{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This notebook was prepared by [Donne Martin](http://donnemartin.com). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solution Notebook"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem: Implement a queue using two stacks.\n",
    "\n",
    "* [Constraints](#Constraints)\n",
    "* [Test Cases](#Test-Cases)\n",
    "* [Algorithm](#Algorithm)\n",
    "* [Code](#Code)\n",
    "* [Unit Test](#Unit-Test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Constraints\n",
    "\n",
    "* Do we expect the methods to be enqueue and dequeue?\n",
    "    * Yes\n",
    "* Can we assume we already have a stack class that can be used for this problem?\n",
    "    * Yes\n",
    "* Can we push a None value to the Stack?\n",
    "    * No\n",
    "* Can we assume this fits memory?\n",
    "    * Yes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Test Cases\n",
    "\n",
    "* Enqueue and dequeue on empty stack\n",
    "* Enqueue and dequeue on non-empty stack\n",
    "* Multiple enqueue in a row\n",
    "* Multiple dequeue in a row\n",
    "* Enqueue after a dequeue\n",
    "* Dequeue after an enqueue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algorithm\n",
    "\n",
    "We'll use two stacks (left and right) to implement the queue.  The left stack will be used for enqueue and the right stack will be used for dequeue.\n",
    "\n",
    "To prevent multiple dequeue calls from needlessly shifting elements around between the stacks, we'll shift elements in a lazy manner.\n",
    "\n",
    "### Enqueue\n",
    "\n",
    "* If right stack is not empty\n",
    "    * Shift the elements of the right stack to the left stack\n",
    "* Push the data to the left stack\n",
    "\n",
    "Complexity:\n",
    "* Time: O(n)\n",
    "* Space: O(n)\n",
    "\n",
    "### Dequeue\n",
    "\n",
    "* If the left stack is not empty\n",
    "    * Shift the elements of the left stack to the right stack\n",
    "* Pop from the right stack and return the data\n",
    "\n",
    "Complexity:\n",
    "* Time: O(n)\n",
    "* Space: O(n)\n",
    "\n",
    "### Shift Stacks\n",
    "\n",
    "* While the source stack has elements:\n",
    "    * Pop from the source stack and push the data to the destination stack\n",
    "\n",
    "Complexity:\n",
    "* Time: O(n)\n",
    "* Space: O(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "%run ../stack/stack.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class QueueFromStacks(object):\n",
    "\n",
    "    def __init__(self):\n",
    "        self.left_stack = Stack()\n",
    "        self.right_stack = Stack()\n",
    "\n",
    "    def shift_stacks(self, source, destination):\n",
    "        while source.peek() is not None:\n",
    "            destination.push(source.pop())\n",
    "\n",
    "    def enqueue(self, data):\n",
    "        self.shift_stacks(self.right_stack, self.left_stack)\n",
    "        self.left_stack.push(data)\n",
    "\n",
    "    def dequeue(self):\n",
    "        self.shift_stacks(self.left_stack, self.right_stack)\n",
    "        return self.right_stack.pop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Unit Test\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting test_queue_from_stacks.py\n"
     ]
    }
   ],
   "source": [
    "%%writefile test_queue_from_stacks.py\n",
    "import unittest\n",
    "\n",
    "\n",
    "class TestQueueFromStacks(unittest.TestCase):\n",
    "\n",
    "    def test_queue_from_stacks(self):\n",
    "        print('Test: Dequeue on empty stack')\n",
    "        queue = QueueFromStacks()\n",
    "        self.assertEqual(queue.dequeue(), None)\n",
    "\n",
    "        print('Test: Enqueue on empty stack')\n",
    "        print('Test: Enqueue on non-empty stack')\n",
    "        print('Test: Multiple enqueue in a row')\n",
    "        num_items = 3\n",
    "        for i in range(0, num_items):\n",
    "            queue.enqueue(i)\n",
    "\n",
    "        print('Test: Dequeue on non-empty stack')\n",
    "        print('Test: Dequeue after an enqueue')\n",
    "        self.assertEqual(queue.dequeue(), 0)\n",
    "\n",
    "        print('Test: Multiple dequeue in a row')\n",
    "        self.assertEqual(queue.dequeue(), 1)\n",
    "        self.assertEqual(queue.dequeue(), 2)\n",
    "\n",
    "        print('Test: Enqueue after a dequeue')\n",
    "        queue.enqueue(5)\n",
    "        self.assertEqual(queue.dequeue(), 5)\n",
    "\n",
    "        print('Success: test_queue_from_stacks')\n",
    "\n",
    "\n",
    "def main():\n",
    "    test = TestQueueFromStacks()\n",
    "    test.test_queue_from_stacks()\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    main()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test: Dequeue on empty stack\n",
      "Test: Enqueue on empty stack\n",
      "Test: Enqueue on non-empty stack\n",
      "Test: Multiple enqueue in a row\n",
      "Test: Dequeue on non-empty stack\n",
      "Test: Dequeue after an enqueue\n",
      "Test: Multiple dequeue in a row\n",
      "Test: Enqueue after a dequeue\n",
      "Success: test_queue_from_stacks\n"
     ]
    }
   ],
   "source": [
    "%run -i test_queue_from_stacks.py"
   ]
  }
 ],
 "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}