book_learning_3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# 《Problem Solving with Algorithms and Data Structures using Python》 的学习笔记和课后作业答案（三. Basic Data Structures）\n",
    "\n",
    "```\n",
    "对应本书第三章。\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 目录\n",
    "\n",
    "* [3. Basic Data Structures](#3.-Basic-Data-Structures)\n",
    "    + [笔记](#笔记)\n",
    "        + [栈stack](#栈stack)\n",
    "        + [队列Queue](#队列Queue)\n",
    "        + [双向队列Deque](#双向队列Deque)\n",
    "        + [无序链表Unsordered List](#无序链表Unsordered-List)\n",
    "        + [有序链表Sordered List](#有序链表Sordered-List)\n",
    "    + [作业](#作业)\n",
    "        + [q1 修改infix-to-postfix算法](#q1)\n",
    "        + [q2 实现后缀表达式求值函数中对操作符和操作数的检查](#q2)\n",
    "        + [q3/q4 计算器](#q3/q4)\n",
    "        + [q5 实现Queue，使得队尾是list的末尾](#q5)\n",
    "        + [q6 设计实验，对比两种Queue实现的优劣](#q6)\n",
    "        + [q7 实现是个enqueue和dequeue都是 O(1)O(1) 的Queue](#q7)\n",
    "        + [q8 设计一个现实生活中的使用场景，模拟队列](#q8)\n",
    "        + [q9 修改hot potato 算法](#q9)\n",
    "        + [q10 实现一个基数排序器](#q10)\n",
    "        + [q11 html匹配检测](#q11)\n",
    "        + [q12 改写回文检测的代码](#q12)\n",
    "        + [q13/q14/q15/q16/q17/q18/q19 修改UnorderedList类](#q13/q14/q15/q16/q17/q18/q19)\n",
    "        + [q20 完善OrderedList的实现](#q20)\n",
    "        + [q21 Unordered list和 Ordered list 的父类](#q21)\n",
    "        + [q22 用链表实现一个stack](#q22)\n",
    "        + [q23 用链表实现一个queue](#q23)\n",
    "        + [q24 用链表实现一个deque](#q24)\n",
    "        + [q25 设计实验对比链表和python内置list的性能](#q25)\n",
    "        + [q26 设计实验对比两种stack和queue的实现的性能](#q26)\n",
    "        + [q27 设计一个双向连接的链表](#q27)\n",
    "        + [q28 设计一个入队和出队时间复杂度都是O(1)的queue](#q28)\n",
    "\n",
    "# 3. Basic Data Structures\n",
    "\n",
    "## 笔记\n",
    "\n",
    "本章主要介绍一些抽象数据类型（ADT）：栈stack/队列Queue/双向队列Deque/无序链表Unsordered List/有序链表Sordered List。\n",
    "\n",
    "### 栈stack\n",
    "\n",
    "用内置的list实现："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "\n",
    "    def isEmpty(self):\n",
    "        return self.items == []\n",
    "\n",
    "    def push(self, item):\n",
    "        self.items.append(item)\n",
    "\n",
    "    def pop(self):\n",
    "        return self.items.pop()\n",
    "\n",
    "    def peek(self):\n",
    "        return self.items[len(self.items)-1]\n",
    "\n",
    "    def size(self):\n",
    "        return len(self.items)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "典型应用：\n",
    "\n",
    "- 括号平衡检查 Parentheses Balance Checker \n",
    "- 数字进制转换 Converting Decimal Numbers to Binary Numbers\n",
    "- 中缀，前缀，后缀表达式 Infix, Prefix and Postfix Expressions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 队列Queue\n",
    "\n",
    "用内置的list实现："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "\n",
    "    def isEmpty(self):\n",
    "        return self.items == []\n",
    "\n",
    "    def enqueue(self, item):\n",
    "        self.items.insert(0,item)\n",
    "\n",
    "    def dequeue(self):\n",
    "        return self.items.pop()\n",
    "\n",
    "    def size(self):\n",
    "        return len(self.items)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "典型应用：\n",
    "\n",
    "- 击鼓传花 Hot Potato Simulation\n",
    "- 打印机任务模拟 Printing Tasks Simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 双向队列Deque\n",
    "\n",
    "用内置的list实现："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Deque:\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "\n",
    "    def isEmpty(self):\n",
    "        return self.items == []\n",
    "\n",
    "    def addFront(self, item):\n",
    "        self.items.append(item)\n",
    "\n",
    "    def addRear(self, item):\n",
    "        self.items.insert(0,item)\n",
    "\n",
    "    def removeFront(self):\n",
    "        return self.items.pop()\n",
    "\n",
    "    def removeRear(self):\n",
    "        return self.items.pop(0)\n",
    "\n",
    "    def size(self):\n",
    "        return len(self.items)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "典型应用：\n",
    "\n",
    "- 回文检查 Palindrome-Checker"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 无序链表Unsordered List\n",
    "\n",
    "用内置的list实现："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self,initdata):\n",
    "        self.data = initdata\n",
    "        self.next = None\n",
    "\n",
    "    def __str__(self):\n",
    "        return str(self.data)\n",
    "    \n",
    "    def getData(self):\n",
    "        return self.data\n",
    "\n",
    "    def getNext(self):\n",
    "        return self.next\n",
    "\n",
    "    def setData(self,newdata):\n",
    "        self.data = newdata\n",
    "\n",
    "    def setNext(self,newnext):\n",
    "        self.next = newnext\n",
    "        \n",
    "class UnorderedList:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        \n",
    "    def isEmpty(self):\n",
    "        return self.head == None\n",
    "\n",
    "    def add(self,item):\n",
    "        temp = Node(item)\n",
    "        temp.setNext(self.head)\n",
    "        self.head = temp\n",
    "    \n",
    "    def size(self):\n",
    "        current = self.head\n",
    "        count = 0\n",
    "        while current != None:\n",
    "            count = count + 1\n",
    "            current = current.getNext()\n",
    "\n",
    "        return count\n",
    "\n",
    "    def search(self,item):\n",
    "        current = self.head\n",
    "        found = False\n",
    "        while current != None and not found:\n",
    "            if current.getData() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                current = current.getNext()\n",
    "\n",
    "        return found\n",
    "\n",
    "    def remove(self,item):\n",
    "        current = self.head\n",
    "        previous = None\n",
    "        found = False\n",
    "        while not found:\n",
    "            if current.getData() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                previous = current\n",
    "                current = current.getNext()\n",
    "\n",
    "        if previous == None:\n",
    "            self.head = current.getNext()\n",
    "        else:\n",
    "            previous.setNext(current.getNext())\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "**有序链表Sordered List**\n",
    "\n",
    "用内置的list实现："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class OrderedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "\n",
    "    def search(self,item):\n",
    "        current = self.head\n",
    "        found = False\n",
    "        stop = False\n",
    "        while current != None and not found and not stop:\n",
    "            if current.getData() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                if current.getData() > item:\n",
    "                    stop = True\n",
    "                else:\n",
    "                    current = current.getNext()\n",
    "\n",
    "        return found\n",
    "\n",
    "    def add(self,item):\n",
    "        current = self.head\n",
    "        previous = None\n",
    "        stop = False\n",
    "        while current != None and not stop:\n",
    "            if current.getData() > item:\n",
    "                stop = True\n",
    "            else:\n",
    "                previous = current\n",
    "                current = current.getNext()\n",
    "\n",
    "        temp = Node(item)\n",
    "        if previous == None:\n",
    "            temp.setNext(self.head)\n",
    "            self.head = temp\n",
    "        else:\n",
    "            temp.setNext(current)\n",
    "            previous.setNext(temp)\n",
    "\n",
    "    def isEmpty(self):\n",
    "        return self.head == None\n",
    "\n",
    "    def size(self):\n",
    "        current = self.head\n",
    "        count = 0\n",
    "        while current != None:\n",
    "            count = count + 1\n",
    "            current = current.getNext()\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 作业\n",
    "\n",
    "[题目地址](http://interactivepython.org/courselib/static/pythonds/BasicDS/ProgrammingExercises.html)\n",
    "\n",
    "### q1 \n",
    "\n",
    "修改infix-to-postfix算法使其可以处理异常情况。\n",
    "\n",
    "分析：异常情况可能是括号不平衡，也可能是缺少操作符或者缺少操作数。\n",
    "\n",
    "括号不平衡可以方便地在中缀转后缀的函数中添加，但是操作符和操作数的检查可以留到计算的步骤再去检查，这步留在q2实现。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A B * C D * +\n",
      "A B + C * D E - F G + * -\n"
     ]
    },
    {
     "ename": "Exception",
     "evalue": "parenthesis are not balance, please check!",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mException\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-6-63343863e9e7>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m     43\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0minfixToPostfix\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"A * B + C * D\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     44\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0minfixToPostfix\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"( A + B ) * C - ( D - E ) * ( F + G )\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 45\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0minfixToPostfix\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"( A + B ) * C - ( D - E ) ) * ( F + G)\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-6-63343863e9e7>\u001b[0m in \u001b[0;36minfixToPostfix\u001b[0;34m(infixexpr)\u001b[0m\n\u001b[1;32m     24\u001b[0m             \u001b[0mleft_p_remain\u001b[0m \u001b[0;34m-=\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     25\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mleft_p_remain\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 26\u001b[0;31m                 \u001b[0;32mraise\u001b[0m \u001b[0mException\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"parenthesis are not balance, please check!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     27\u001b[0m             \u001b[0mtopToken\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mopStack\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpop\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     28\u001b[0m             \u001b[0;32mwhile\u001b[0m \u001b[0mtopToken\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[0;31mException\u001b[0m: parenthesis are not balance, please check!"
     ]
    }
   ],
   "source": [
    "# q1\n",
    "def infixToPostfix(infixexpr):\n",
    "    \"\"\"将表达式从中缀形式转化成后缀形式\"\"\"\n",
    "    prec = {}\n",
    "    prec[\"*\"] = 3\n",
    "    prec[\"/\"] = 3\n",
    "    prec[\"+\"] = 2\n",
    "    prec[\"-\"] = 2\n",
    "    prec[\"(\"] = 1\n",
    "    # 存储操作符的栈\n",
    "    opStack = Stack()\n",
    "    postfixList = []\n",
    "    tokenList = infixexpr.split()\n",
    "    # 栈中剩余的左括号的个数\n",
    "    left_p_remain = 0\n",
    "    \n",
    "    for token in tokenList:\n",
    "        if token in \"ABCDEFGHIJKLMNOPQRSTUVWXYZ\" or token in \"0123456789\":\n",
    "            postfixList.append(token)\n",
    "        elif token == '(':\n",
    "            opStack.push(token)\n",
    "            left_p_remain += 1\n",
    "        elif token == ')':\n",
    "            left_p_remain -= 1\n",
    "            if left_p_remain < 0:\n",
    "                raise Exception(\"parenthesis are not balance, please check!\")\n",
    "            topToken = opStack.pop()\n",
    "            while topToken != '(':\n",
    "                postfixList.append(topToken)\n",
    "                topToken = opStack.pop()\n",
    "        else:\n",
    "            while (not opStack.isEmpty()) and \\\n",
    "                (prec[opStack.peek()] >= prec[token]):\n",
    "                    postfixList.append(opStack.pop())\n",
    "            opStack.push(token)\n",
    "    if left_p_remain != 0:\n",
    "        raise Exception(\"parenthesis are not balance, please check!\")\n",
    "            \n",
    "    while not opStack.isEmpty():\n",
    "        postfixList.append(opStack.pop())\n",
    "\n",
    "    return \" \".join(postfixList)\n",
    "\n",
    "print(infixToPostfix(\"A * B + C * D\"))\n",
    "print(infixToPostfix(\"( A + B ) * C - ( D - E ) * ( F + G )\"))\n",
    "print(infixToPostfix(\"( A + B ) * C - ( D - E ) ) * ( F + G)\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### q2 \n",
    "\n",
    "实现后缀表达式求值函数中对操作符和操作数的检查"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.0\n"
     ]
    },
    {
     "ename": "Exception",
     "evalue": "not enough operand, please check!",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mException\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-7-88e05ae7bebb>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m     30\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     31\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpostfixEval\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'7 8 + 3 2 + /'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 32\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpostfixEval\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'7 8 + 3 2 + / -'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-7-88e05ae7bebb>\u001b[0m in \u001b[0;36mpostfixEval\u001b[0;34m(postfixExpr)\u001b[0m\n\u001b[1;32m      9\u001b[0m             \u001b[0;31m# token是个操作符，需要出栈两个操作数，提前检查操作数够不够\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     10\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0moperandStack\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msize\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 11\u001b[0;31m                 \u001b[0;32mraise\u001b[0m \u001b[0mException\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"not enough operand, please check!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     12\u001b[0m             \u001b[0moperand2\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0moperandStack\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpop\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     13\u001b[0m             \u001b[0moperand1\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0moperandStack\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpop\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mException\u001b[0m: not enough operand, please check!"
     ]
    }
   ],
   "source": [
    "def postfixEval(postfixExpr):\n",
    "    operandStack = Stack()\n",
    "    tokenList = postfixExpr.split()\n",
    "\n",
    "    for token in tokenList:\n",
    "        if token in \"0123456789\":\n",
    "            operandStack.push(int(token))\n",
    "        else:\n",
    "            # token是个操作符，需要出栈两个操作数，提前检查操作数够不够\n",
    "            if operandStack.size() < 2:\n",
    "                raise Exception(\"not enough operand, please check!\")\n",
    "            operand2 = operandStack.pop()\n",
    "            operand1 = operandStack.pop()\n",
    "            result = doMath(token,operand1,operand2)\n",
    "            operandStack.push(result)\n",
    "    # 如果遍历完以后，栈中还剩操作数，则操作数过多\n",
    "    if operandStack.size() != 1:\n",
    "        raise Exception(\"too much operand, please check!\")\n",
    "    return operandStack.pop()\n",
    "\n",
    "def doMath(op, op1, op2):\n",
    "    if op == \"*\":\n",
    "        return op1 * op2\n",
    "    elif op == \"/\":\n",
    "        return op1 / op2\n",
    "    elif op == \"+\":\n",
    "        return op1 + op2\n",
    "    else:\n",
    "        return op1 - op2\n",
    "\n",
    "print(postfixEval('7 8 + 3 2 + /'))\n",
    "print(postfixEval('7 8 + 3 2 + / -'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "Exception",
     "evalue": "too much operand, please check!",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mException\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-8-23319fcf89d3>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpostfixEval\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'7 8 + 3 2 + / 1'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-7-88e05ae7bebb>\u001b[0m in \u001b[0;36mpostfixEval\u001b[0;34m(postfixExpr)\u001b[0m\n\u001b[1;32m     16\u001b[0m     \u001b[0;31m# 如果遍历完以后，栈中还剩操作数，则操作数过多\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     17\u001b[0m     \u001b[0;32mif\u001b[0m \u001b[0moperandStack\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msize\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m!=\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 18\u001b[0;31m         \u001b[0;32mraise\u001b[0m \u001b[0mException\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"too much operand, please check!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     19\u001b[0m     \u001b[0;32mreturn\u001b[0m \u001b[0moperandStack\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpop\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     20\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mException\u001b[0m: too much operand, please check!"
     ]
    }
   ],
   "source": [
    "print(postfixEval('7 8 + 3 2 + / 1'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### q3/q4\n",
    "\n",
    "将q1和q2合并，写一个直接根据中序表达式的函数，q4要求把q3改成一个计算器。个人以为q3和q4相似，直接写成一处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-0.08888888888888889\n"
     ]
    }
   ],
   "source": [
    "# q3/q4\n",
    "\n",
    "class Calculator(object):\n",
    "    \"\"\"支持0-9的加减乘除的简单计算器。\"\"\"\n",
    "    \n",
    "    def __init__(self):\n",
    "        pass\n",
    "        \n",
    "    def calc(self, infix):\n",
    "        postfix = self.infixToPostfix(infix)\n",
    "        return self.postfixEval(postfix)\n",
    "\n",
    "    def infixToPostfix(self, infixexpr):\n",
    "        \"\"\"将表达式从中缀形式转化成后缀形式\"\"\"\n",
    "        prec = {}\n",
    "        prec[\"*\"] = 3\n",
    "        prec[\"/\"] = 3\n",
    "        prec[\"+\"] = 2\n",
    "        prec[\"-\"] = 2\n",
    "        prec[\"(\"] = 1\n",
    "        # 存储操作符的栈\n",
    "        opStack = Stack()\n",
    "        postfixList = []\n",
    "        tokenList = infixexpr.split()\n",
    "        # 栈中剩余的左括号的个数\n",
    "        left_p_remain = 0\n",
    "\n",
    "        for token in tokenList:\n",
    "            if token in \"ABCDEFGHIJKLMNOPQRSTUVWXYZ\" or token in \"0123456789\":\n",
    "                postfixList.append(token)\n",
    "            elif token == '(':\n",
    "                opStack.push(token)\n",
    "                left_p_remain += 1\n",
    "            elif token == ')':\n",
    "                left_p_remain -= 1\n",
    "                if left_p_remain < 0:\n",
    "                    raise Exception(\"parenthesis are not balance, please check!\")\n",
    "                topToken = opStack.pop()\n",
    "                while topToken != '(':\n",
    "                    postfixList.append(topToken)\n",
    "                    topToken = opStack.pop()\n",
    "            else:\n",
    "                while (not opStack.isEmpty()) and \\\n",
    "                    (prec[opStack.peek()] >= prec[token]):\n",
    "                        postfixList.append(opStack.pop())\n",
    "                opStack.push(token)\n",
    "        if left_p_remain != 0:\n",
    "            raise Exception(\"parenthesis are not balance, please check!\")\n",
    "\n",
    "        while not opStack.isEmpty():\n",
    "            postfixList.append(opStack.pop())\n",
    "\n",
    "        return \" \".join(postfixList)\n",
    "\n",
    "    def postfixEval(self, postfixExpr):\n",
    "        operandStack = Stack()\n",
    "        tokenList = postfixExpr.split()\n",
    "\n",
    "        for token in tokenList:\n",
    "            if token in \"0123456789\":\n",
    "                operandStack.push(int(token))\n",
    "            else:\n",
    "                # token是个操作符，需要出栈两个操作数，提前检查操作数够不够\n",
    "                if operandStack.size() < 2:\n",
    "                    raise Exception(\"not enough operand, please check!\")\n",
    "                operand2 = operandStack.pop()\n",
    "                operand1 = operandStack.pop()\n",
    "                result = self.doMath(token,operand1,operand2)\n",
    "                operandStack.push(result)\n",
    "        # 如果遍历完以后，栈中还剩操作数，则操作数过多\n",
    "        if operandStack.size() != 1:\n",
    "            raise Exception(\"too much operand, please check!\")\n",
    "        return operandStack.pop()\n",
    "\n",
    "    def doMath(self, op, op1, op2):\n",
    "        if op == \"*\":\n",
    "            return op1 * op2\n",
    "        elif op == \"/\":\n",
    "            return op1 / op2\n",
    "        elif op == \"+\":\n",
    "            return op1 + op2\n",
    "        else:\n",
    "            return op1 - op2\n",
    "        \n",
    "cal = Calculator()\n",
    "print(cal.calc(\"( 1 + 3 ) / ( ( 3 - 8 ) * 9 ) \"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "Exception",
     "evalue": "too much operand, please check!",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mException\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-10-968961ac46e3>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcal\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcalc\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"( 1 + 3 ) / ( ( 3 - 8 ) * 9 ) 9 \"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-9-507891dfbead>\u001b[0m in \u001b[0;36mcalc\u001b[0;34m(self, infix)\u001b[0m\n\u001b[1;32m      9\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0mcalc\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0minfix\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     10\u001b[0m         \u001b[0mpostfix\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0minfixToPostfix\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0minfix\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 11\u001b[0;31m         \u001b[0;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpostfixEval\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpostfix\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     12\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     13\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0minfixToPostfix\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0minfixexpr\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-9-507891dfbead>\u001b[0m in \u001b[0;36mpostfixEval\u001b[0;34m(self, postfixExpr)\u001b[0m\n\u001b[1;32m     69\u001b[0m         \u001b[0;31m# 如果遍历完以后，栈中还剩操作数，则操作数过多\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     70\u001b[0m         \u001b[0;32mif\u001b[0m \u001b[0moperandStack\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msize\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m!=\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 71\u001b[0;31m             \u001b[0;32mraise\u001b[0m \u001b[0mException\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"too much operand, please check!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     72\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0moperandStack\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpop\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     73\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mException\u001b[0m: too much operand, please check!"
     ]
    }
   ],
   "source": [
    "print(cal.calc(\"( 1 + 3 ) / ( ( 3 - 8 ) * 9 ) 9 \"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### q5 \n",
    "\n",
    "实现Queue，使得队尾是list的末尾"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "class Queue2:\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "\n",
    "    def isEmpty(self):\n",
    "        return self.items == []\n",
    "\n",
    "    def enqueue(self, item):\n",
    "        self.items.append(item)\n",
    "\n",
    "    def dequeue(self):\n",
    "        head = self.items[0]\n",
    "        del self.items[0]\n",
    "        return head\n",
    "\n",
    "    def size(self):\n",
    "        return len(self.items)\n",
    "\n",
    "q = Queue2()\n",
    "q.enqueue(1)\n",
    "q.enqueue(2)\n",
    "print(q.items[1]) \n",
    "q.dequeue()\n",
    "print(q.items[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### q6 \n",
    "\n",
    "设计实验，对比两种Queue实现的优劣"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def queue1_en_test():\n",
    "    q = Queue()\n",
    "    for i in range(1000):\n",
    "        q.enqueue(1)\n",
    "        \n",
    "def queue2_en_test():\n",
    "    q = Queue2()\n",
    "    for i in range(1000):\n",
    "        q.enqueue(1)\n",
    "        \n",
    "def queue1_en_de_test():\n",
    "    q = Queue()\n",
    "    for i in range(1000):\n",
    "        q.enqueue(1)\n",
    "    for i in range(1000):\n",
    "        q.dequeue()\n",
    "        \n",
    "def queue2_en_de_test():\n",
    "    q = Queue2()\n",
    "    for i in range(1000):\n",
    "        q.enqueue(1)\n",
    "    for i in range(1000):\n",
    "        q.dequeue()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "queue1_en_test: 0.49930859899995994 milliseconds\n",
      "queue2_en_test: 0.20399194199990234 milliseconds\n",
      "queue1_en_de_test: 0.7333720130000074 milliseconds\n",
      "queue2_en_de_test: 0.5521609099996567 milliseconds\n"
     ]
    }
   ],
   "source": [
    "from timeit import Timer\n",
    "t1 = Timer(\"queue1_en_test()\", \"from __main__ import queue1_en_test\")\n",
    "print(\"queue1_en_test:\",t1.timeit(number=1000), \"milliseconds\")\n",
    "t2 = Timer(\"queue2_en_test()\", \"from __main__ import queue2_en_test\")\n",
    "print(\"queue2_en_test:\",t2.timeit(number=1000), \"milliseconds\")\n",
    "t3 = Timer(\"queue1_en_de_test()\", \"from __main__ import queue1_en_de_test\")\n",
    "print(\"queue1_en_de_test:\",t3.timeit(number=1000), \"milliseconds\")\n",
    "t4 = Timer(\"queue2_en_de_test()\", \"from __main__ import queue2_en_de_test\")\n",
    "print(\"queue2_en_de_test:\",t4.timeit(number=1000), \"milliseconds\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "从理论分析可以知道，如果进队操作设置在list起点，那么入队操作是$O(n)$，出队操作是$O(1)$；\n",
    "\n",
    "相反，如果进队操作设置在list末端，那么入队操作是$O(1)$，出队操作是$O(n)$。\n",
    "\n",
    "但是为什么在测试中综合第二种的性能比第一种的好呢？\n",
    "\n",
    "看一下下面的测试："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "list_append_test: 0.09044601999994484 milliseconds\n",
      "list_pop_test: 0.10493274600003133 milliseconds\n",
      "list_del_test: 0.14676751699971646 milliseconds\n",
      "list_insert_test: 0.3609275019998677 milliseconds\n"
     ]
    }
   ],
   "source": [
    "def list_append_test():\n",
    "    l = list(range(1000))\n",
    "    for i in range(1000):\n",
    "        l.append(i)\n",
    "\n",
    "def list_pop_test():\n",
    "    l = list(range(1000))\n",
    "    for i in range(1000):\n",
    "        l.pop()\n",
    "        \n",
    "def list_del_test():\n",
    "    l = list(range(1000))\n",
    "    for i in range(1000):\n",
    "        del l[0]\n",
    "        \n",
    "def list_insert_test():\n",
    "    l = []\n",
    "    for i in range(1000):\n",
    "        l.insert(0, i)\n",
    "        \n",
    "t5 = Timer(\"list_append_test()\", \"from __main__ import list_append_test\")\n",
    "print(\"list_append_test:\",t5.timeit(number=1000), \"milliseconds\")\n",
    "t6 = Timer(\"list_pop_test()\", \"from __main__ import list_pop_test\")\n",
    "print(\"list_pop_test:\",t6.timeit(number=1000), \"milliseconds\")\n",
    "t7 = Timer(\"list_del_test()\", \"from __main__ import list_del_test\")\n",
    "print(\"list_del_test:\",t7.timeit(number=1000), \"milliseconds\")\n",
    "t8 = Timer(\"list_insert_test()\", \"from __main__ import list_insert_test\")\n",
    "print(\"list_insert_test:\",t8.timeit(number=1000), \"milliseconds\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "也就是说list的append比pop快，虽然都是$O(1)$;而且，del也比insert快，虽然都是$O(n)$。\n",
    "\n",
    "因此第二种实现更好。\n",
    "\n",
    "### q7 \n",
    "\n",
    "实现是个enqueue和dequeue都是$O(1)$的Queue。\n",
    "\n",
    "这道题我没有想出来，于是在[stackoverflow](http://stackoverflow.com/questions/69192/how-to-implement-a-queue-using-two-stacks)上找到了一个双栈的实现方法。只有在outbox空的时候，把所有inbox出栈，再入outbox栈，这里的时间复杂度是$O(n)$。正好符合作者的要求。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "# q7\n",
    "class Queue3:\n",
    "    \"\"\"\n",
    "    Keep 2 stacks, let's call them inbox and outbox.\n",
    "\n",
    "    Enqueue:\n",
    "\n",
    "    Push the new element onto inbox\n",
    "    Dequeue:\n",
    "\n",
    "    If outbox is empty, refill it by popping each element from inbox and pushing it onto outbox\n",
    "    Pop and return the top element from outbox\n",
    "    \"\"\"\n",
    "    def __init__(self):\n",
    "        self.inbox = Stack()\n",
    "        self.outbox = Stack()\n",
    "\n",
    "    def enqueue(self, item):\n",
    "        self.inbox.push(item)\n",
    "\n",
    "    def dequeue(self):\n",
    "        if self.outbox.isEmpty():\n",
    "            while not self.inbox.isEmpty():\n",
    "                self.outbox.push(self.inbox.pop());\n",
    "        return self.outbox.pop();\n",
    "\n",
    "q3 = Queue3()\n",
    "q3.enqueue(1)\n",
    "q3.enqueue(2)\n",
    "q3.enqueue(3)\n",
    "print(q3.dequeue())\n",
    "print(q3.dequeue())\n",
    "print(q3.dequeue())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### q8 \n",
    "\n",
    "设计一个现实生活中的使用场景，模拟队列。\n",
    "\n",
    "这里设计一个理发师和顾客的场景。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Barber():\n",
    "    \n",
    "    def __init__(self, wait_seat_num):\n",
    "        self.wait_seat_num = wait_seat_num\n",
    "        self.isWorking = False\n",
    "        self.wait_queue = Queue()\n",
    "        \n",
    "    def costomer_come(self, cid):\n",
    "        if self.isWorking:\n",
    "            if self.wait_queue.size() < self.wait_seat_num:\n",
    "                self.wait_queue.enqueue(cid)\n",
    "            else:\n",
    "                print(\"Sorry, the baber shop is full! Come again later!\")\n",
    "        else:\n",
    "            self.isWorking = True\n",
    "            self.work(cid)\n",
    "            \n",
    "    def work(self, cid):\n",
    "        # ... ...\n",
    "        self.work_done(cid)\n",
    "    \n",
    "    def work_done(self, cid):\n",
    "        if self.wait_queue.size() > 0:\n",
    "            new_cid = self.wait_queue.deque()\n",
    "            self.work(new_cid)\n",
    "        else:\n",
    "            self.isWorking = False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### q9 \n",
    "\n",
    "修改hot potato 算法，使每次传递的个数为一个随机数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Susan\n",
      "Brad\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "def hotPotato(namelist):\n",
    "    simqueue = Queue()\n",
    "    for name in namelist:\n",
    "        simqueue.enqueue(name)\n",
    "\n",
    "    while simqueue.size() > 1:\n",
    "        num = random.randrange(1,5)\n",
    "        for i in range(num):\n",
    "            simqueue.enqueue(simqueue.dequeue())\n",
    "\n",
    "        simqueue.dequeue()\n",
    "\n",
    "    return simqueue.dequeue()\n",
    "\n",
    "print(hotPotato([\"Bill\",\"David\",\"Susan\",\"Jane\",\"Kent\",\"Brad\"]))\n",
    "print(hotPotato([\"Bill\",\"David\",\"Susan\",\"Jane\",\"Kent\",\"Brad\"]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### q10 \n",
    "\n",
    "实现一个基数排序器，参考wikipedia的[Radix_sort](https://en.wikipedia.org/wiki/Radix_sort)。\n",
    "\n",
    "wikipedia的example：\n",
    "\n",
    "```\n",
    "An example[edit]\n",
    "Original, unsorted list:\n",
    "170, 45, 75, 90, 802, 2, 24, 66\n",
    "Sorting by least significant digit (1s place) gives:\n",
    "170, 90, 802, 2, 24, 45, 75, 66\n",
    "Notice that we keep 802 before 2, because 802 occurred before 2 in the original list, and similarly for pairs 170 & 90 and 45 & 75.\n",
    "Sorting by next digit (10s place) gives:\n",
    "802, 2, 24, 45, 66, 170, 75, 90\n",
    "Notice that 802 again comes before 2 as 802 comes before 2 in the previous list.\n",
    "Sorting by most significant digit (100s place) gives:\n",
    "2, 24, 45, 66, 75, 90, 170, 802\n",
    "```\n",
    "\n",
    "简单的说，就是每比一位排一次序。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "7\n",
      "0\n",
      "[10, 20, 300]\n",
      "[1, 3, 20, 25, 98, 677]\n"
     ]
    }
   ],
   "source": [
    "# q10\n",
    "def get_max_num_len(nums):\n",
    "    \"\"\"获取数组中位数最大的个数的位数\"\"\"\n",
    "    max_len = 0\n",
    "    for num in nums:\n",
    "        cur_len = 1 \n",
    "        while num // 10 != 0:\n",
    "            num = num // 10\n",
    "            cur_len += 1\n",
    "        if cur_len > max_len:\n",
    "            max_len = cur_len\n",
    "    return max_len\n",
    "\n",
    "def get_num_by_order(num, order):\n",
    "    \"\"\"例如输入876和2，返回第二位的7；若输入4，则返回0\"\"\"\n",
    "    left = num // (10**(order-1))\n",
    "    return left % 10\n",
    "\n",
    "\n",
    "def radix_sorting_machine(nums):\n",
    "    bins = []\n",
    "    for i in range(10):\n",
    "        bins.append(Queue())\n",
    "    for i in range(get_max_num_len(nums)):\n",
    "        for num in nums:\n",
    "            bins[get_num_by_order(num, i+1)].enqueue(num)\n",
    "        j = 0\n",
    "        for one_bin in bins:\n",
    "            while not one_bin.isEmpty():\n",
    "                nums[j] = one_bin.dequeue()\n",
    "                j += 1\n",
    "    return nums\n",
    "\n",
    "print(get_max_num_len([10, 20, 300]))\n",
    "print(get_num_by_order(876, 2))\n",
    "print(get_num_by_order(876, 4))\n",
    "print(radix_sorting_machine([10, 20, 300]))\n",
    "print(radix_sorting_machine([20, 1, 3, 677, 98, 25]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### q11 \n",
    "\n",
    "html匹配检测"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "html is balance !\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import re\n",
    "\n",
    "def html_checker(html_str):\n",
    "    pattern = \"<(.+?)>\"\n",
    "    tag_stack = Stack()\n",
    "    html_pat = re.compile(pattern)\n",
    "    tags = html_pat.findall(html_str)\n",
    "    if tags:\n",
    "        for one in tags:\n",
    "            one = one.strip()\n",
    "            if not one.startswith('/'):\n",
    "                tag_stack.push(one)\n",
    "            else:\n",
    "                one = one.replace('/', '')\n",
    "                if tag_stack.isEmpty():\n",
    "                    print(\"html is not balace, check : \", one)\n",
    "                    return False\n",
    "                stack_top = tag_stack.pop()\n",
    "                if stack_top != one:\n",
    "                    print(\"html is not balace, check : \", one)\n",
    "                    return False\n",
    "        if not tag_stack.isEmpty():\n",
    "            print(\"html is not closed, please check !\")\n",
    "            return False\n",
    "    print(\"html is balance !\")\n",
    "    return True\n",
    "            \n",
    "        \n",
    "html_str = \"\"\"\n",
    "<html>\n",
    "   <head>\n",
    "      <title>\n",
    "         Example\n",
    "      </title>\n",
    "   </head>\n",
    "\n",
    "   <body>\n",
    "      <h1>Hello, world</h1>\n",
    "   </body>\n",
    "</html>\n",
    "\"\"\"\n",
    "html_checker(html_str)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "html is not closed, please check !\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "html_str += \"<a>\"\n",
    "html_checker(html_str)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "html is not balace, check :  b\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "html_str = \"<a></b>\"\n",
    "html_checker(html_str)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### q12\n",
    "\n",
    "改写回文检测的代码，使得有空格也可以检测（忽略空格）。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "True\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "# q12\n",
    "def palchecker(aString):\n",
    "    chardeque = Deque()\n",
    "\n",
    "    for ch in aString:\n",
    "        if ch != \" \":\n",
    "            chardeque.addRear(ch)\n",
    "\n",
    "    stillEqual = True\n",
    "\n",
    "    while chardeque.size() > 1 and stillEqual:\n",
    "        first = chardeque.removeFront()\n",
    "        last = chardeque.removeRear()\n",
    "        if first != last:\n",
    "            stillEqual = False\n",
    "\n",
    "    return stillEqual\n",
    "\n",
    "print(palchecker(\"lsdkjfskf\"))\n",
    "print(palchecker(\"radar\"))\n",
    "print(palchecker(\"I PREFER PI\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### q13/q14/q15/q16/q17/q18/q19\n",
    "\n",
    "- q13 修改UnorderedList类，增加一个变量保存链表的长度，获取长度的时候不用再遍历。\n",
    "- q14 修改remove方法，使得元素不存在时的情况也能处理。\n",
    "- q15 允许UnorderedList中存在重复的元素。代码无修改，会影响后面的index方法。\n",
    "- q16/q17 实现__str__方法。\n",
    "- q18 实现UnorderedList的append, index, pop, insert方法。\n",
    "- q19 实现UnorderedList的切片。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# q13/q14/q15/q16/q17/q18\n",
    "\n",
    "class UnorderedList:\n",
    "\n",
    "    def __init__(self):\n",
    "        # 保存第一个结点\n",
    "        self.head = None\n",
    "        self.length = 0\n",
    "        # 保存最后一个结点\n",
    "        self.rear = None\n",
    "    \n",
    "    # q16/q17    \n",
    "    def __str__(self):\n",
    "        datas = []\n",
    "        current = self.head\n",
    "        while current:\n",
    "            datas.append(current.getData())\n",
    "            current = current.getNext()\n",
    "        datas = [str(data) for data in datas]\n",
    "        return \"[\" + \",\".join(datas) + \"]\"\n",
    "    \n",
    "    # q19\n",
    "    def __getitem__(self, key) :\n",
    "        if isinstance(key, slice) :\n",
    "            #Get the start, stop, and step from the slice\n",
    "            indices = list(range(self.size()))[key.start:key.stop:key.step]\n",
    "            items = []\n",
    "            for ind in indices:\n",
    "                items.append(self.__getitem__(ind))\n",
    "            return items\n",
    "        elif isinstance(key, int) :\n",
    "            if key < 0 : #Handle negative indices\n",
    "                key += self.size()\n",
    "            if key < 0 or key >= self.size() :\n",
    "                raise IndexError(\"The index (%d) is out of range.\"%key)\n",
    "\n",
    "            current = self.head\n",
    "            cur_ind = 0\n",
    "            while cur_ind < key:\n",
    "                current = current.getNext()\n",
    "                cur_ind += 1\n",
    "            return current\n",
    "        else:\n",
    "            raise TypeError(\"Invalid argument type.\")\n",
    "        \n",
    "    def isEmpty(self):\n",
    "        return self.head == None\n",
    "\n",
    "    def add(self,item):\n",
    "        \"\"\"添加元素到头部\"\"\"\n",
    "        temp = Node(item)\n",
    "        temp.setNext(self.head)\n",
    "        if self.head == None:\n",
    "            self.rear = temp\n",
    "        self.head = temp\n",
    "        # q13\n",
    "        self.length += 1\n",
    "    \n",
    "    # q13\n",
    "    def size(self):\n",
    "        return self.length\n",
    "\n",
    "    def search(self,item):\n",
    "        current = self.head\n",
    "        found = False\n",
    "        while current != None and not found:\n",
    "            if current.getData() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                current = current.getNext()\n",
    "        return found\n",
    "\n",
    "    def remove(self,item):\n",
    "        current = self.head\n",
    "        previous = None\n",
    "        found = False\n",
    "        while not found and current:\n",
    "            if current.getData() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                previous = current\n",
    "                current = current.getNext()\n",
    "        # q14\n",
    "        if found:\n",
    "            if previous == None:\n",
    "                self.head = current.getNext()\n",
    "            else:\n",
    "                previous.setNext(current.getNext())\n",
    "            # q13\n",
    "            self.length -= 1\n",
    "        else:\n",
    "            print(\"item not found in the list!\")\n",
    "    \n",
    "    # q18        \n",
    "    def append(self, item):\n",
    "        \"\"\"添加元素到尾部\"\"\"\n",
    "        temp = Node(item)\n",
    "        if self.rear == None:\n",
    "            self.rear = temp\n",
    "        else:\n",
    "            self.rear.setNext(temp)\n",
    "            self.rear = temp\n",
    "        if self.head == None:\n",
    "            self.head = temp\n",
    "        self.length += 1\n",
    "        \n",
    "    def index(self, item):\n",
    "        ind_list = []\n",
    "        current = self.head\n",
    "        cur_ind = 0\n",
    "        while current:\n",
    "            if current.getData() == item:\n",
    "                ind_list.append(cur_ind)\n",
    "            current = current.getNext()\n",
    "            cur_ind += 1\n",
    "        return ind_list\n",
    "        \n",
    "    def pop(self, pos=0):\n",
    "        if pos > self.size()-1:\n",
    "            print(\"pos is bigger than list size!\")\n",
    "            return    \n",
    "        cur_ind = 1\n",
    "        pre = self.head\n",
    "        current = pre.getNext()\n",
    "        if pos == 0:\n",
    "            self.head = current\n",
    "            self.length -= 1\n",
    "            return pre.getData()\n",
    "        while cur_ind < pos:\n",
    "            pre = current\n",
    "            current = pre.getNext()\n",
    "            cur_ind += 1\n",
    "#         print(pre.getData())\n",
    "        pre.setNext(current.getNext())\n",
    "        self.length -= 1\n",
    "        return current.getData()\n",
    "        \n",
    "    def insert(self, pos, item):\n",
    "        if pos > self.size():\n",
    "            print(\"pos is bigger than list size!\")\n",
    "            return   \n",
    "        if pos == 0:\n",
    "            self.add(item)\n",
    "        elif pos == self.size():\n",
    "            self.append(item)\n",
    "        else:\n",
    "            pre = self.head\n",
    "            current = pre.getNext()\n",
    "            cur_ind = 1\n",
    "            while cur_ind < pos:\n",
    "                pre = current\n",
    "                current = pre.getNext()\n",
    "                cur_ind += 1\n",
    "            temp = Node(item)\n",
    "            temp.setNext(current)\n",
    "            pre.setNext(temp)\n",
    "            self.length += 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "ul = UnorderedList()\n",
    "ul.add(1)\n",
    "ul.add(2)\n",
    "# q13\n",
    "print(ul.size())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "item not found in the list!\n"
     ]
    }
   ],
   "source": [
    "# q14\n",
    "ul.remove(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "True\n",
      "[3,2,1]\n"
     ]
    }
   ],
   "source": [
    "# q16/q17\n",
    "ul.add(3)\n",
    "print(ul.size())\n",
    "print(ul.search(2))\n",
    "print(ul)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3,2,1,3,5,4]\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "# q18\n",
    "ul.append(3)\n",
    "ul.append(5)\n",
    "ul.append(4)\n",
    "print(ul)\n",
    "print(ul.size())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 3]\n"
     ]
    }
   ],
   "source": [
    "# q18\n",
    "print(ul.index(3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3,2,1,3,5,4]\n",
      "5\n",
      "[3,2,3,5,4]\n",
      "4\n",
      "4\n",
      "[3,2,3,5]\n"
     ]
    }
   ],
   "source": [
    "# q18\n",
    "print(ul)\n",
    "print(ul.size()-1)\n",
    "ul.pop(2)\n",
    "print(ul)\n",
    "print(ul.size()-1)\n",
    "print(ul.pop(ul.size()-1))\n",
    "print(ul)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3,3,2,3,5]\n",
      "[3,3,2,3,3,5]\n",
      "[3,3,2,3,3,3,5]\n",
      "pos is bigger than list size!\n"
     ]
    }
   ],
   "source": [
    "ul.insert(0, 3)\n",
    "print(ul)\n",
    "ul.insert(3, 3)\n",
    "print(ul)\n",
    "ul.insert(5, 3)\n",
    "print(ul)\n",
    "ul.insert(8, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7\n"
     ]
    }
   ],
   "source": [
    "print(ul.size())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "3\n",
      "2\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "for node in ul[0:3]:\n",
    "    print(node)\n",
    "print(ul[2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### q20\n",
    "\n",
    "完善OrderedList的实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class OrderedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "\n",
    "    def search(self,item):\n",
    "        current = self.head\n",
    "        found = False\n",
    "        stop = False\n",
    "        while current != None and not found and not stop:\n",
    "            if current.getData() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                if current.getData() > item:\n",
    "                    stop = True\n",
    "                else:\n",
    "                    current = current.getNext()\n",
    "\n",
    "        return found\n",
    "\n",
    "    def add(self,item):\n",
    "        current = self.head\n",
    "        previous = None\n",
    "        stop = False\n",
    "        while current != None and not stop:\n",
    "            if current.getData() > item:\n",
    "                stop = True\n",
    "            else:\n",
    "                previous = current\n",
    "                current = current.getNext()\n",
    "\n",
    "        temp = Node(item)\n",
    "        if previous == None:\n",
    "            temp.setNext(self.head)\n",
    "            self.head = temp\n",
    "        else:\n",
    "            temp.setNext(current)\n",
    "            previous.setNext(temp)\n",
    "\n",
    "    def isEmpty(self):\n",
    "        return self.head == None\n",
    "\n",
    "    def size(self):\n",
    "        current = self.head\n",
    "        count = 0\n",
    "        while current != None:\n",
    "            count = count + 1\n",
    "            current = current.getNext()\n",
    "\n",
    "        return count  \n",
    "    \n",
    "    def remove(item):\n",
    "        pre = self.head\n",
    "        current = pre.getNext()\n",
    "        if item == pre.getData():\n",
    "            self.head = current\n",
    "        found = False\n",
    "        stop = False\n",
    "        while current and not found and not stop:\n",
    "            if current.getData() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                if current.getData() > item:\n",
    "                    stop = True\n",
    "                else:\n",
    "                    pre = current\n",
    "                    current = current.getNext()\n",
    "        if found:\n",
    "            pre.setNext(current.getNext())\n",
    "    \n",
    "    def pop(self, pos=0):\n",
    "        if pos > self.size()-1:\n",
    "            print(\"pos is bigger than list size!\")\n",
    "            return    \n",
    "        cur_ind = 1\n",
    "        pre = self.head\n",
    "        current = pre.getNext()\n",
    "        if pos == 0:\n",
    "            self.head = current\n",
    "            return pre.getData()\n",
    "        while cur_ind < pos:\n",
    "            pre = current\n",
    "            current = pre.getNext()\n",
    "            cur_ind += 1\n",
    "        pre.setNext(current.getNext())\n",
    "        self.length -= 1\n",
    "        return current.getData()\n",
    "    \n",
    "    def index(self, item):\n",
    "        current = self.head\n",
    "        cur_ind = 0\n",
    "        found = False\n",
    "        stop = False\n",
    "        while current != None and not found and not stop:\n",
    "            if current.getData() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                if current.getData() > item:\n",
    "                    stop = True\n",
    "                else:\n",
    "                    current = current.getNext()\n",
    "                    cur_ind += 1\n",
    "        if found:\n",
    "            return cur_ind\n",
    "        else:\n",
    "            return -1\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### q21 \n",
    "\n",
    "考虑写一个Unordered list和 Ordered list 的父类，使得二者相同的操作可以在父类中实现。\n",
    "\n",
    "相同的操作有：\n",
    "\n",
    "pop size isEmpty\n",
    "\n",
    "此题代码省略。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### q22\n",
    "\n",
    "用链表实现一个stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Stack2:\n",
    "    def __init__(self):\n",
    "        self.items = UnorderedList()\n",
    "\n",
    "    def isEmpty(self):\n",
    "        return self.items.size() == 0\n",
    "\n",
    "    def push(self, item):\n",
    "        self.items.append(item)\n",
    "\n",
    "    def pop(self):\n",
    "        return self.items.pop(self.items.size()-1)\n",
    "\n",
    "    def peek(self):\n",
    "        return self.items[-1]\n",
    "\n",
    "    def size(self):\n",
    "        return self.items.size()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### q23\n",
    "\n",
    "用链表实现一个queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Queue2:\n",
    "    def __init__(self):\n",
    "        self.items = UnorderedList()\n",
    "\n",
    "    def isEmpty(self):\n",
    "        return self.items.size() == 0\n",
    "\n",
    "    def enqueue(self, item):\n",
    "        self.items.append(item)\n",
    "\n",
    "    def dequeue(self):\n",
    "        return self.items.pop(self.items.size()-1)\n",
    "\n",
    "    def size(self):\n",
    "        return self.items.size()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### q24\n",
    "\n",
    "用链表实现一个deque"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Deque2:\n",
    "    def __init__(self):\n",
    "        self.items = UnorderedList()\n",
    "\n",
    "    def isEmpty(self):\n",
    "        return self.items.size() == 0\n",
    "\n",
    "    def addFront(self, item):\n",
    "        self.items.add(item)\n",
    "\n",
    "    def addRear(self, item):\n",
    "        self.items.append(item)\n",
    "\n",
    "    def removeFront(self):\n",
    "        return self.items.pop()\n",
    "\n",
    "    def removeRear(self):\n",
    "        return self.items.pop(self.items.size()-1)\n",
    "\n",
    "    def size(self):\n",
    "        return self.items.size()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### q25\n",
    "\n",
    "设计实验对比链表和python内置list的性能。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def list_test():\n",
    "    l = []\n",
    "    for i in range(1000):\n",
    "        l.append(i)\n",
    "    for i in range(1000):\n",
    "        l.pop()\n",
    "    \n",
    "def unorded_list_test():\n",
    "    ul = UnorderedList()\n",
    "    for i in range(1000):\n",
    "        ul.add(i)\n",
    "    for i in range(1000):\n",
    "        ul.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "list : 0.020239962999767158 milliseconds\n",
      "unorded list : 0.18505007000021578 milliseconds\n"
     ]
    }
   ],
   "source": [
    "from timeit import Timer\n",
    "t9 = Timer(\"list_test()\", \"from __main__ import list_test\")\n",
    "print(\"list :\",t9.timeit(number=100), \"milliseconds\")\n",
    "t10 = Timer(\"unorded_list_test()\", \"from __main__ import unorded_list_test\")\n",
    "print(\"unorded list :\",t10.timeit(number=100), \"milliseconds\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### q26\n",
    "\n",
    "设计实验对比两种stack和queue的实现的性能。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def stack_1_test():\n",
    "    s = Stack()\n",
    "    for i in range(1000):\n",
    "        s.push(i)\n",
    "    for i in range(1000):\n",
    "        s.pop()\n",
    "    \n",
    "def stack_2_test():\n",
    "    s = Stack2()\n",
    "    for i in range(1000):\n",
    "        s.push(i)\n",
    "    for i in range(1000):\n",
    "        s.pop()\n",
    "    \n",
    "def queue_1_test():\n",
    "    q = Queue()\n",
    "    for i in range(1000):\n",
    "        q.enqueue(i)\n",
    "    for i in range(1000):\n",
    "        q.dequeue()\n",
    "    \n",
    "def queue_2_test():\n",
    "    q = Queue2()\n",
    "    for i in range(1000):\n",
    "        q.enqueue(i)\n",
    "    for i in range(1000):\n",
    "        q.dequeue()\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "stack 1: 0.005089294999834237 milliseconds\n",
      "stack 2: 0.9783772470000258 milliseconds\n",
      "queue 1: 0.007056649999867659 milliseconds\n",
      "queue 2: 0.9649373209999794 milliseconds\n"
     ]
    }
   ],
   "source": [
    "t11 = Timer(\"stack_1_test()\", \"from __main__ import stack_1_test\")\n",
    "print(\"stack 1:\",t11.timeit(number=10), \"milliseconds\")\n",
    "t12 = Timer(\"stack_2_test()\", \"from __main__ import stack_2_test\")\n",
    "print(\"stack 2:\",t12.timeit(number=10), \"milliseconds\")\n",
    "t13 = Timer(\"queue_1_test()\", \"from __main__ import queue_1_test\")\n",
    "print(\"queue 1:\",t13.timeit(number=10), \"milliseconds\")\n",
    "t14 = Timer(\"queue_2_test()\", \"from __main__ import queue_2_test\")\n",
    "print(\"queue 2:\",t14.timeit(number=10), \"milliseconds\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### q27\n",
    "\n",
    "设计一个双向连接的链表。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Node2:\n",
    "    def __init__(self,initdata):\n",
    "        self.data = initdata\n",
    "        self.next = None\n",
    "        self.pre = None\n",
    "\n",
    "    def __str__(self):\n",
    "        return str(self.data)\n",
    "    \n",
    "    def getData(self):\n",
    "        return self.data\n",
    "\n",
    "    def getNext(self):\n",
    "        return self.next\n",
    "\n",
    "    def getPre(self):\n",
    "        return self.pre\n",
    "    \n",
    "    def setData(self,newdata):\n",
    "        self.data = newdata\n",
    "\n",
    "    def setNext(self,newnext):\n",
    "        self.next = newnext\n",
    "        \n",
    "    def setPre(self,newpre):\n",
    "        self.pre = newpre"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### q28\n",
    "\n",
    "设计一个入队和出队时间复杂度都是O(1)的queue。\n",
    "\n",
    "参考[q7](#q7)"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda env:py35]",
   "language": "python",
   "name": "conda-env-py35-py"
  },
  "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}