Chapter6.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "c7ae000e",
   "metadata": {},
   "outputs": [
    {
     "ename": "IndentationError",
     "evalue": "expected an indented block (<ipython-input-1-32cd6a5a2e56>, line 71)",
     "output_type": "error",
     "traceback": [
      "\u001b[0;36m  File \u001b[0;32m\"<ipython-input-1-32cd6a5a2e56>\"\u001b[0;36m, line \u001b[0;32m71\u001b[0m\n\u001b[0;31m    class Stack:\u001b[0m\n\u001b[0m                ^\u001b[0m\n\u001b[0;31mIndentationError\u001b[0m\u001b[0;31m:\u001b[0m expected an indented block\n"
     ]
    }
   ],
   "source": [
    "import unittest\n",
    "\n",
    "\n",
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self._data = []\n",
    "        self._first_element = None # maintain explicitly where the first element is\n",
    "        self._size = 0\n",
    "        \n",
    "    def enqueue(self, element):\n",
    "        if self._size == len(self._data):\n",
    "            self._resize()\n",
    "            self._first_element = 0\n",
    "        \n",
    "        insertion_position = (self._size + self._first_element) % len(self._data)\n",
    "        self._data[insertion_position] = element\n",
    "        self._size += 1\n",
    "        \n",
    "    def first(self):\n",
    "        return self._data[self._first_element]\n",
    "    \n",
    "    @property\n",
    "    def is_empty(self):\n",
    "        return self._size == 0\n",
    "        \n",
    "    def dequeue(self):\n",
    "        if self._size == 0:\n",
    "            return \"empty queue\"\n",
    "        elem = self._data[self._first_element]\n",
    "        self._data[self._first_element] = None\n",
    "        self._size -= 1\n",
    "        self._first_element = (self._first_element + 1) % len(self._data)\n",
    "        return elem\n",
    "    \n",
    "    def _resize(self):\n",
    "        # TODO implement resize in a smaller direction\n",
    "        old_len = len(self._data) or 1\n",
    "        new_len = old_len * 2\n",
    "        arr = [None for _ in range(new_len)]\n",
    "        for x in range(len(self._data)):\n",
    "            old_queue_index = (self._first_element + x) % old_len\n",
    "            arr[x] = self._data[old_queue_index]\n",
    "        self._data = arr\n",
    "        \n",
    "    def __len__(self):\n",
    "        return self._size\n",
    "    \n",
    "class Dequeue:\n",
    "    def __init__(self):\n",
    "        self._data = []\n",
    "        self._size = 0\n",
    "        self._first_element = None\n",
    "    \n",
    "    def add_first(self):\n",
    "        ...\n",
    "    def add_last(self):\n",
    "        ...\n",
    "    def delete_first(self):\n",
    "        ...\n",
    "    def delete_last(self):\n",
    "        ...\n",
    "    def first(self):\n",
    "        ...\n",
    "    def last(self):\n",
    "        ...\n",
    "    def is_empty(self):\n",
    "        return self._size == 0\n",
    "    def __len__(self):\n",
    "        return self._size\n",
    "\n",
    "# implement stack, queue, dequeue here\n",
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self._data = []\n",
    "    def push(self, element):\n",
    "        self._data.append(element)\n",
    "        \n",
    "    def pop(self):\n",
    "        return self._data.pop()\n",
    "        \n",
    "    def __len__(self):\n",
    "        return len(self._data)\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return len(self) == 0 \n",
    "    "
   ]
  },
  {
   "cell_type": "raw",
   "id": "4fec6669",
   "metadata": {},
   "source": [
    "# 6.3 Implement a function with signature transfer(S, T) that transfers all ele-\n",
    "# ments from stack S onto stack T, so that the element that starts at the top\n",
    "# of S is the first to be inserted onto T, and the element at the bottom of S\n",
    "# ends up at the top of T\n",
    "\n",
    "def transfer(s, t):\n",
    "    for _ in range(len(s)):\n",
    "        t.push(s.pop())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "30109cb9",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 6.4 Give a recursive method for removing all the elements from a stack\n",
    "def remove_recursive(stack):\n",
    "    try:\n",
    "        stack.pop()\n",
    "        remove_recursive(stack)\n",
    "    except IndexError:\n",
    "        return \"stack is empty\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "97786be0",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 6.5 Implement a function that reverses a list of elements by pushing them onto\n",
    "# a stack in one order, and writing them back to the list in reversed order.\n",
    "def reverse_list(l):\n",
    "    stack = Stack()\n",
    "#     for x in range(len(l)):\n",
    "#         stack.push()\n",
    "    for element in l:\n",
    "        stack.push(element)\n",
    "    while not stack.is_empty():\n",
    "        l.append(stack.pop())\n",
    "    return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "78a60bfc",
   "metadata": {},
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'Queue' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-2-e619831b1e2c>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      3\u001b[0m \u001b[0;31m# Give a code fragment that uses only D and Q (and no other variables) and\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m \u001b[0;31m# results in D storing the elements in the order (1,2,3,5,4,6,7,8).\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m \u001b[0mQ\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mQueue\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0mD\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mDequeue\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m3\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m4\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m5\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m6\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m7\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m8\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mQ\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0menqueu\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mD\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mremove\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mNameError\u001b[0m: name 'Queue' is not defined"
     ]
    }
   ],
   "source": [
    "# 6.13 Suppose you have a deque D containing the numbers (1,2,3,4,5,6,7,8),\n",
    "# in this order. Suppose further that you have an initially empty queue Q.\n",
    "# Give a code fragment that uses only D and Q (and no other variables) and\n",
    "# results in D storing the elements in the order (1,2,3,5,4,6,7,8).\n",
    "Q = Queue()\n",
    "D = Dequeue([1,2,3,4,5,6,7,8])\n",
    "Q.enqueu(D.remove)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "eebb59ae",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "test_63 (__main__.TestExercises) ... ok\n",
      "test_64 (__main__.TestExercises) ... ok\n",
      "test_65 (__main__.TestExercises) ... ok\n",
      "test_queue (__main__.TestExercises) ... ok\n",
      "\n",
      "----------------------------------------------------------------------\n",
      "Ran 4 tests in 0.003s\n",
      "\n",
      "OK\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<unittest.main.TestProgram at 0x7f235649cb80>"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class TestExercises(unittest.TestCase):\n",
    "\n",
    "    def test_63(self):\n",
    "        s, t = Stack(), Stack()\n",
    "        for x in range(10):\n",
    "            s.push(x)\n",
    "        self.assertTrue(t.is_empty())\n",
    "        transfer(s, t)\n",
    "        self.assertEqual(t._data, list(range(9, -1, -1)))\n",
    "        self.assertTrue(s.is_empty())\n",
    "        \n",
    "    def test_64(self):\n",
    "        s = Stack()\n",
    "        self.assertTrue(s.is_empty())\n",
    "        for x in range(10):\n",
    "            s.push(x)\n",
    "        self.assertFalse(s.is_empty())\n",
    "        remove_recursive(s)\n",
    "        self.assertTrue(s.is_empty())\n",
    "    \n",
    "    def test_65(self):\n",
    "        original_list = list(range(10))\n",
    "        reverse_list(original_list)\n",
    "        self.assertEqual(original_list, list(range(10)) + list(range(9, -1, -1)))\n",
    "        \n",
    "    def test_queue(self):\n",
    "        q = Queue()\n",
    "        q.enqueue(5)\n",
    "        self.assertEqual(q.first(), 5)\n",
    "        q.enqueue(3)\n",
    "        self.assertEqual(q.first(), 5)\n",
    "        self.assertEqual(len(q), 2)\n",
    "        r = q.dequeue()\n",
    "        self.assertEqual(r, 5)\n",
    "        self.assertEqual(len(q), 1)\n",
    "        self.assertEqual(q.first(), 3)\n",
    "        self.assertFalse(q.is_empty)\n",
    "        \n",
    "        r = q.dequeue()\n",
    "        self.assertEqual(r, 3)\n",
    "        self.assertEqual(len(q), 0)\n",
    "        self.assertTrue(q.is_empty)\n",
    "        \n",
    "        r = q.dequeue()\n",
    "        self.assertEqual(r, \"empty queue\")\n",
    "        \n",
    "        \n",
    "        \n",
    "unittest.main(argv=[''], verbosity=2, exit=False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "62449e34",
   "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.9.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}