面试题31：栈的压入、弹出序列.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 书上的思路：\n",
    "构造两个栈，按照第二个栈的出栈顺序来判断。\n",
    "\n",
    "1. 判断下一个弹出的数据，因为它要被弹出，所以应该是最后一个被弹出的。在它之前的数据应该都直接压入。\n",
    "2. 弹出该元素后，要判断下一个被弹出的数字是不是栈顶，如果是栈顶直接弹出，如果不是的话，则应该压入后面的元素。如果所有的元素都被压完了，还没有找到相同的数字，那么说明这个弹出序列不是原来序列的一部分。就可以返回False了。\n",
    "\n",
    "伪代码可以这样写：\n",
    "```python\n",
    "i = 0\n",
    "for 元素 in popV:\n",
    "    ### 当栈顶元素和弹出的首元素不相等时，执行压栈操作\n",
    "    while stack.peek() != 当前弹出元素:\n",
    "        if i >= len(pushV): # 说明所有元素都已经入栈,但栈顶元素却不等\n",
    "            return False\n",
    "        stack.push(pushV[i])\n",
    "        i+=1\n",
    "    ### 栈顶元素相同了，就弹出，进行下一个元素  \n",
    "    stack.pop()\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "# -*- coding:utf-8 -*-\n",
    "class Solution:\n",
    "    def IsPopOrder(self, pushV, popV):\n",
    "        # write code here\n",
    "        stack = []\n",
    "        i = 0\n",
    "        for curr in popV:\n",
    "            while stack == [] or stack[-1] != curr :\n",
    "                if i >= len(pushV):\n",
    "                    return False\n",
    "                stack.append(pushV[i])\n",
    "                i+=1    \n",
    "            stack.pop()\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = Solution()\n",
    "a.IsPopOrder([1,2,3,4,5],[4,5,3,2,1])"
   ]
  }
 ],
 "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}