定义
栈是一种“操作受限”的线性表,后进者先出,先进者后出。
比较典型的例子就是我们在叠盘子的时候,叠的时候从下到上一个一个磊起来,取的时候,再从上到下一个一个的拿出来。
说到先入后出这种特性,在 Go 中你第一时间想到了什么?不知道是否和我的答案一样, defer
![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAO0AAAF5CAYAAABzza1uAAAgAElEQVR4nO2deZRcR33vv3Xv7W000kijkUaSrdWWbJaHZHBekIkXDM45GAIcOw+w2U5yrGMDDj55vEAsY4KxETYvhjwTgon9CIsxNn7PIQdvOeCFhBw9YscbMbZk7btm1Wzdt/su9f74VfWt7lml6emrrqrPOWNrerrv/XV3fe/vV7/61e8yzjmHxWJpGZy0DbBYLCeHFa3F0mJY0VosLYYVrcXSYljRWiwthhWtxdJiWNFaLC2GFa3F0mJ4jT6grdWwWKaGMTar189atFakFsvJUa+ZkxXxKYvWitViaQxSSzMV70mL9mTFasVtMZ2ZinGm4mUz3TAwk6fVP8cK1mIh6oU4EyFP9pxpRTud8DjnEz7HCtZiqWUiETLGpves9YKfSrRTCS+O4xk/dyZ/t1h042TF6DiTr8Cqz51UtJN5z+lC4HoxT3dMi0VHphJsvTgnCp0n88rAJKKdSFyTedbphKw+z2IxiarIVC85hUBn4nkZY+NFO51gJxOrfM5EIrWCtZjKRIKV/1dFOZl4JxLutEs+9YKtF638XRXtyQrWitrSqpxsFnii0HeqUDiO43HCrRHtdGHudD/yJPWvmejYFovuqJ5zIu/JOa/+Tf2pf718nmRSTzuZV5U/cRyDc45sNotMJtPAtzp7du/ejf/4j//A7t27MTAwAABYsmQJ3vjGN+KSSy5Be3t7yhZamoE6Dvr7+8EYO+3GQRAEqFQqYIxNOoetL7qoPmsir6r+WxWrFGwmkzltBPvb3/4WW7duxZve9CZcdNFFeOCBBzA0NITu7m50d3ejt7cXd911F+bPn48Pf/jDeOKJJ9I22TIHTDYOli1bdlqOA6mhem3VR7A1004uiOO4+hNFEQ/DkIdhyCuVCq9UKtz3fV4sFvnY2BgfHR3lw8PD/HTgl7/8Jf/ABz7Au7u7+ec//3n+7LPPTvn84eFh/p3vfIdv2rSJX3LJJfzxxx9vkqWWuaTVx8Hw8DAfHR3lY2NjvFgsct/3q9qTWoyiiMdxzMF5rWDjOK4+KQgCXqlUeLlc5qVSqUawg4ODqb7JF154gV955ZV8/fr1/O677z6lY/zoRz/i69ev55/85Cf5sWPHGmyhpRnoMg4GBwdrhFsqlXi5XOaVSoUHQVDVZBzHfFwQzadJPsVxjCiKpiyimGtuvvlmXHDBBdi8eTN27tyJa6+99pSO87GPfQw7d+7E8uXLsXHjRjz00EMNttQyl+g0DlRdTaQ7Cecc7l/91V99WX0x53zc/2Wsrf5EUYR58+Y18W0B//Iv/4Irr7wSnufh0UcfxR/+4R825Ljvfve7sXHjRtxwww3o6+vDpZde2pDjWuYGHcfB6OjopMtB49ZvJwuNZVgs57Kjo6N8aGiIDw4O8t7e3qaHEXfccQdvb2/nP/jBD+bsHP39/fzyyy/nV1999ZydwzI7dB0Hx44d4729vXxwcJAPDQ3x0dHR6txWhslSmzXhMZ+kmqney8rHmsHo6Ciuvvpq/PM//zNefvllfOITn5izc3V2duLRRx9Fe3s7LrvsMgwNDc3ZuSwnh+7jQNVVvdYk8t8Tilb9vf4x9YBzzUsvvYSLLroI3d3dePLJJ7F27do5PycAfPe738Xb3vY2XH755ejr62vKOS2TY8I4mExXE2lw0r1AvG59qN7LzrVoH3nkEVxyySW45ppr8M1vfnNOzzURt99+Oy699FJ84AMfwIkTJ5p+fgthyjiYSF+qYFXhTija+idyPr4Sai5F+73vfQ8f+chHcN999+HTn/70nJ1nOm699VZceOGF+OM//mNEUZSaHaZi0jhQdaXqDRivx3EVUfWuWEX+rT7WbiR33nknvvKVr+BXv/oV3vve987JOU6G22+/HRs2bMBVV12VtilGYdo4UB3hdBqcsln5RGqvd9uN5JZbbsEPf/hDPP3003jb297W8OOfKn/3d3+HOI5xww03pG2KEZg4DtRIVv6uPq4yYe1x/e8THbDRor3pppvw+OOPNzXRcDI8+OCD2L59O/7mb/4mbVO0xtRxoGpqIseo/nva/bT1L56JCz9ZbrzxRvz617/GL37xC8yfP79hx20kruvivvvuw9vf/nZs2LABl19+edomaYfJ40AVrOu61ccm0tm04fF0/54tN910E37961/jiSeeOG2/KMmGDRvw/e9/H1u2bMHBgwfTNkcr7DiYud6mzB5PdfBGZI9vueUWPPnkk3jssceaXhJ5qrz//e/Hddddh+uuuy5tU7TBjoOZJXcnLK6Y6AnTPXaqfP3rX8c//uM/4pFHHjntr6z13HzzzfA8D7fcckvaprQ8dhyMZzrtNfyueTPh7rvvxt///d/jqaeeQldXVxomzJq7774bb3nLW3DBBRfgsssuS9uclsSOg1PjpO9PO1tv+8ADD+Dmm2/Gz372M6xatWpWx0qT5cuX49vf/jZuuOEGlMvltM1pOew4mJiZ6OuUbip9qsL95S9/iY9+9KN4+OGH8eY3v/mUjnE68aEPfQgXX3wxPve5z6VtSkthx8HEzFRXTbsT/Msvv4yrrroKDz30EC688MJmnXbOueuuu/DEE0/gn/7pn9I2pSWw42D2zEi0sw2Je3t78dGPfhRf+cpXcMUVV8zqWKcbmUwG3/jGN/D5z38elUolbXNOa+w4ODkm090pe9qTEfLHP/5xfPCDH8SnPvWpUz3dac373/9+XHzxxbjxxhvTNuW0xo6DyTkZPbE4jjlQW+lUvxE3DENEUYQwDBEEQfVnw4YN055gy5YtCIIA3//+90/6jbQSQ0ND2LBhAx566CFcdNFFaZtz2mHHwdTs3Lmz2k41k8nA8zy4rgvP8+A4Tu3PHNqP2267Dbt27dL+iwKAjo4O3H777bjpppvSNuW0w46DxjJnor3//vtx77334v7775+rU5x2/Mmf/Ana29tx1113pW3KaYMdB41nTsLj3/zmN7jwwgvx1FNP4Q/+4A/mxPDTlRdeeAHvfOc7sWPHDnR3d6dtTqrYcTDzcZBqeDw4OIg//dM/xd13323cFwUA5513Hq655hrjSxztOJi7cdBwT3vFFVdg/fr1uOOOOxpubKtQKpWwdu1aPPzww7jgggvSNicV7Dg4uXGQmqe96aabEIah0V8UABQKBXz5y1/GrbfemrYpqWDHATFX46Bhor3//vvxwAMP4Ac/+EGjDtnSXHfddejv78eDDz6YtilNxY6DWuZiHDREtC+//DK2bNmCf/iHf8CiRYsacUgt+NKXvoRt27albUbTsONgYho9Dhoi2muvvRZ33HGHLSqo433vex9Wr16Nb33rW2mb0hTsOJiYRo+DWSeirrvuOoRhiHvvvbchBunGb37zG1xxxRXYs2cPcrlc2ubMGXYcTM1046Bpiajvfve7ePbZZ+0XNQW///u/j8suuwxf//rX0zZlzrDjYHoaOQ5m5WnPOeccPP/88zjvvPNmbYjO7NixA+effz727t3bsh0apoIxZsfBDJhqHDTN03LO7Rc1A8455xx88pOfxJ133ll97IorrsAPf/jDFK1qHHYczIxGjYNUekSZyBe+8AWsXbsW119/PZ5//nn8/Oc/x7p169I2y9JkJhsHb3/722d8DCvaJrFy5Up89rOfxa233ooHH3wQYRi2XPdBy+xpxDiwop1j7rnnHnzjG99AZ2cnKpUKnnvuOeTz+bTNsjSZRo4DK9o5pqenBwcPHsTu3bsRBAEAwPf9lK2yNJtGjoOmNXYzlZtuugmvv/46LrjgAixYsCBtcywp0chxYEXbBJYvX45nnnkGn/70p1EoFNI2x5ISjRoHVrRN5Gtf+xp++tOfYuHChdU7o1nMY7bjwIq2ybzvfe/DK6+8gjPPPBMjIyNpm2NJidmMgznvxmixWKbntOnGaLFYGo8VrcXSYljRWiwthhWtxdJiWNFaLC2GFa3F0mJY0VosLYYVrcXSYljRWiwthhWtxdJiWNFaLC2GFa3F0mJY0VosLYYVrcXSYljRWiwthhWtxdJiWNFOBefgcYiwPAQeVcB5lLZFFottoSqJgiJ2P/MZcB6B81gIlIMxF5n8YgTlQSCOwHkExlzAccEY/bi5DsTBGJiTBROPg7nVf/OoAifbDsY8MEf5meD3sHwC2XnLJ/37ZK8NSn3ItZ+hnNcj+xwXYF5iVyvCQ4DZoSox/pOIwxJ2/eqzmL/0bWjvPh+cxwCPAV4BhwsIAWfnLa/+jfMIPI4AKfBwFK6bAWcegBhxXAE4F8+NweMAKA8C4PQ4OB0LHKBmP/Q/8RowRsZxLqzkyn9R81j1QTbuCRM9oMCU/zHxm3yMicc4IIXOXDDGADgAc8CYQ892PHGRcpKLhbhQOMoFJo4r8LIdYI4HOOJvjNGP2w7HyYDFw2C5ZWBuBg7LAswBGAfKR4DsUjAnX7UNYMIeptgr/h2XAbdQ/b1v18NYsHwzOs64eIrPo3UwXrSl3n9HHIwiv/Bs4TkdACFY5RhYpgvIdCaDMh4FeAiW7a4OXJQPgcU+MO8N9DtzksEd9IA5BSCzCAiHaWxlOkEDzQGLK0BpJ+DOAwpnJ4MQDCgfAvIrhZUMLOyjwSueCwCIK0Dxd4DTBngLgOwyABzwD9AFJS4BmS76CUcAfw944Y3gPASPK+BjO8Dza8HjkH54CB4F4MEgykOvwZu/AQiHwaMxxKwNnLvgPKDnhkXwSh+4207XGh6CRyE4DxBHJSAsgnOGOPDB4whxWERQ6gXiAJw5FLXEFQDUl4xzeRFMLnZgJETGHMAR3wHc6ucMcLqwODnxGImUxQGYkwV3PDA4KI8eRNviNzV3YM0hxosWjIEDWLTy3fR7XAaKrwJsBTDvDcnzwiHA3wu0bSCRAPS7uwBovyjxSABQ2gPwCpDNAYWz6JjhQaCwAXDbk+eN/SeQbQfa3iwGoaB8CGAxDdTyUcAtAEEP4OaAtrMBlhHP208idtsTgZePAIgBxsFy3UB2OYk7OELHYT6QXUK2z19Hr/X3AQs2ifc5CJRCtC98N+AtBCpH6Rjlg0DbOYBTEJ/RDiC3HMgsqf08g346XuEser0kGgNKrwP5NfR4aRcdy20DWJYuXoUN9H78/UB+NXhpP+JgCLG3GHFxL7i3BHEcIQ59xJU+xKXDiFkOMXKIwxLiSj/iYARRLJoThkXEYRE8DpWopfWxos0sSv4djdBgYplawfr7gGCABqIUbOUIPda2vlaw/gEa1IhJ4IwBpd0i1FM+7uJOmqvNe1OtYCtHgWiUvKm0pdxPYXNBEWzlKBCXAGcekF9FjwW9QHgCcDzAaSexASRQ5pDAMkvoeXEFyC0Giq+TnQBdmEp7SEzZbhJmfjVQPgDk19Hj4OJiNR+oHAO8DhIdAERFElxmca1gY5/O42Tpcf8AfWbeInGBzAK5VSTY8iH6XIJ+sHgEbvs5cEt7gAUbgOxScbwxYAxA13ogv1bYPgiU9lEkk1+dnDvow2tPfhY81KddrfHZYzmbQzRMAwsO0HZu8oRwmLxHdgkNUIB+Lx8FcmeQp5VUjtLAR0gCZxlgbAfAI6CwHnDEDZf8fSTMtnMSEQJA5TgQDNJALO2iwRwNA2DkoaSXDodJMCwDFJRBWz5Cj7E8kDtTnGs/eX1vEYXPUZFEk11CAi2cRQKMRgF/D4k7v5JszK0km3Irk/fu7yO7QmGnFCyPRag/n2yV8IDE73jAvHPFxcYnkfp7yNNmFpHQK8fJjuxSOk9+LV0wvAWJYHlI35M3PxFsVARKe0n0qmCjEr1XcHAnd3ID4zTGeNFWkz6l3fTv3BmJR+SVZGDlRPgZDdNA8DrFHFIQ9AGVXgAxkD2DBOrvB+IikD+TBhRAYgv6aXA5yq0hgl4KgQtr6JxOnoTBcuT1Mp3CppA8HVygsA4Ao4EuBy3zEs9bOU6e152fiLh8gMJa/7AQ40KysbSbjpVfKzxoJ70200lzYgAoH6bzx0Wyvz7UZ1mKPCQ8Aoqv0XHbzqULUtBPF5rSHno+88i2cEBcIFaJ8HgNfSYsQ99J9Ty/o9cV1ifnKAkv3qb24Y6B0g7AbRe5vnBm46EFMF60nCvpV7cjGaBxGRh7jQZVmwiVozEhjrbEwwFivntQeNSzaKBXjiTilMcMh2jgZ5eRZ5EEA/R4fi0NWKeNBrg7n4ShXhxKu8R5zqbBG5fJJk94/KrnPUE2OIXE8/kHAScHBCfEhWBx8nrm0nnCYXrPvEzPlSF20Ev2c06vU+0f+x19fvPeWPvhFl8jDzzvXBK6v194zyOUFY7LJFJ50SmsI5u9Tgr9eVjrtSc6T3EHAE7zYZWx35Hg2zbQertGa+zGixZy6SK/WnguiLmdmHMWzqLH4pIIHzMU1kqiInkNcBFqttPALx+lELR6ESiRN/MW1nqO8AR5zvxaEpU7jx7zFohQdVXyXH8/na9wFl04eCzml3kh5HXKuYQnk5nmoJ/m7HGZwtHsUgpdZUjszgfA6LUsS8eToWY4THNNJ0ceTQoZIC/HK0B7XXZ27FU6ftu5InTeSxeUaJjC46iYvLfSHnr/4SBoScklW/PrkuMVd44/T2k32VtYT3ZVnyumJPPeVE1A8Uo/vQcNMF60TP7DEwmp2KcQksd0lXcKlLQp7aFlTzVBVR30IBF4C0T4KsW5MnlecSeJS14EABqY/l4KicuHaZ4WDtP8MS7Xepmgl4SXO0OZX+4B4ABxIATrgMLCXTTwC+tJkLEvkj+O8NzLEyHBpR+vg8JTV9gg54uxTzZ6i8Z7Pn8fLSUV1qNmKBV30OvknN3fm5wzGCAbs8vp/fp7yesjIo/rLQAqPSRYmaAr7RE5gHOT85QP08W1sDaZesjPJCqSdwdEMQwDj4riPK2P8aJVZCtCxV0APBrcch7p7yHhzXtD7fNLe0gwuVXJnHHsdzQfrYozJsECQKHeQ+8FsmcC5eNAZiGJ2J1Pnja/Jplby+RRZnEy8Pz9Yn5ZJsHKhFbxdSFixfv4+8kmp6AkqERGOS4DuW76PdNFF4fCWpERF57c6yBx5pUpQfloEv6rointomlE2wY6n7+H3pOTp4uhk6fwP9stphrt9LzyITq/f4Dej0wclQ+RBy6sSxJ5wSBdYLLLKJSu2nQkSeSxXPLewcCdttqkXwtjRSs1yAORjMrQYJeiK+6kLGTbG2qXbEp7KDTLn5nM78ZeoQO2Kd64uIu8TuHsZGkoLpOXyi4lkWQ6aaA7bSIru4bCX0AkWmRWVoSr5SP0/NivHcwyK104O3l9+RC9NyeXvN7fB4ALj7qKklKZJZSAKqxNjlfaS5noYICiAXkRCAZo7pldXju3Le0l79d2tlhvFUs7mS4Sr9cpvPVKkdVlQEZkirMryHsW1iUXgaBHJKfOTJaQ4pK4kCwEciuSc4eDlJnOraALIABUjoNXegDmgHPlYtviWNFK1ZaE52FO4lH8/eT9CmcnV34gCc2ySnFBdd1VWS7y99GaYn5NMhB5SI97C8hTZTrposAyJMTcGbVrnEUloQKIhFC/mMspA7xylMSUW50kpYIBOgfLJvPd8kESceyTYIO+ZB6dX50sYZUPAeDC/tVizguxjLKPxKqKxj9AGeD8GjpG5RjZmFtFF8PMYnGOVRT+SvvlsYK+WnEGA4B/iEQtowse0efstCXvB6D3UtpLn6Wcb0dDQPkQeGYxGHMQ2+yxTsg630Asl4i5VDhIA6mwnuZekqBfhGZLlFB1jxC3EqZWjoolk27FG3EapE6eRJ/povMiJjF7HbUVRtXsq8iWhoPJskthXSKw8ES1PhdZmfjyxZqql0QN5SMUanOIDK2fPDfTldhZ6aH3g5ieV7U/WUapmdtWDieiyyymzyjoE0s7uykrHwyQYKNi8jd/P10Mo9HapSVeEdVeSqWX/Dzg1F4YAZpDu/OUeXgJKO4Wn+dy8rRxMNUgaCmMFy0L+8HBxdX7LArn4pJYRlmUeC2APKG/j7Kv1XXPw0AwRANSeqOgL0nq1Hij/QAcMUi7AMQ0iJlH51WzyqXd5NXmnQtaix0TJYpMrK/KxJlIknkLE5uAumSUm6zZOjnAydBPOEwXAKeQLCuFJ+iCw/KiUkmxf1SuxSrLK5XjNCfPLaOLWDSSLO34h+gCFY+JC5yb/C0YoIsFj8T5lYz02Kv0mHqeoshSz1PyAoBYH3aTjL4s5nALQOFscB6DSdHyUHyGrY3xokU0CoCJ9U1RqFDcKea1SgjGQ1recJVKnKCP5l3ZJYmHDIfEXE6pVgIoLI0rdEHIdNFAC/rJQ9RnisuHSFCFdZRQiUWRB4/FGm9X8tziq2LdWMlKF1+n17SJZFTQR97TW0CPe510DrdQW4wRF5PEE69MsEaK2jXSYICOk11Cc1IZphaEKOmDowuFt1BkyteRsCo9yRxZXdaqilDxpuUDtFRUWJ9UYAHK0s6bax9TX88j8rSRLwpIWh8rWndh7e/lI2KNck3t42N1c8vwBIlTrTaSSRLGlCUYiFB5hISQWSKqpQ6KqqMhSvLIML0iky8rxNIOF0s7qM0eA0riSx3gh2iAt52dJLbKBylsDofouP4+UQlVTi5MPBTRRWftkg+geDlFsNGwyDh3kueXa8bZZSTeuEQXk9inz6e0h7ypk0vm9HGl9sI4kQgrPVRpll9ZW4FV2iuy1IrnLb5GF4TCOdXPkzwtAw9HRTSjRA4tihVtRlky8A8AiOgxdYAUX6X/zxML+9GYKKzPJ8ULPBLlhZwGvCxRDHqBSh+AmJIq3nxR19sNBMfF0o7wHuEJITAl+VLaSwPRW1Q74Io76PH2tySPyfl27kya70YjYllpOT2eXyM8bDu9h7wogwREkUZ7UmaoLhdFYi1WZs/jImXFvQ4laSc2ETBGyy7ZxWK9dZUQaYfYXSQEG43VCra0hx5T56vRKH0emSX02UkqRyjpVZPp3i2OWVdoERdFRVScfFctjvGirS4EBL0094qDWm9W2kNzy3bhZeRaLnNqQ1J/P9W3ZlckGdBwUMzrXBp0mcViTtwlBrRSGCB3yHiLkqKM8kGyiWXr5qvSyygDPPaTHTbZ7qRSK3cGZXLzayiUZx553LwqzAMAXBKJOjcvH6XQOr9KsbMk5oztiQjEWijt0jkK5M+gSCK/mt4n88iO0j6KVqqhv9xieIguWHI6ACTTEW9BbfgcDIjNGsuTeX35UPKe1Istr4AX99CcFi3atWMCjBdtdcOAf4gGgduWeMnyYbGwfxYALylOB8Q2PaUAIBoV5YFC8NGIyBS7gNeV7Fxx22mAqks7ci3WKSTep3KMPJZTqA0By4fF0oriZXikZFDXiHVgEaoGfXSucIQEF43WLRWJpRlE9P6rddKDylpsl2LnjtpkVOUYXSCyXcl8tnyELl5BXzJfLx+hEDscVrb5QUQicjqgTFXGXiUBF5QNCNXlpk46fvX1vWKur0RNPBZhfQjm5mhPrSZY0Uryq2nwVdcJ+2hAZOXcEqK8MaIBVs0Ui/JCdSeQXG6BS0s+2aWJ2KOSEIeytDP2Cg3Q6lpsP4nBydTW3wZ99Hh2Re0+4OKroC2F54gwXax9hkNJp4xoCEAs1kLlFsMBsZPGodfL8FtmzzOdtSH52O/Ia8ppQtBPr8+toPC0sI6mAm57Uj6ZX0XPC/sTAcuMfDRKHjmzpHZTRPE1srVmAwJXlpuU7Yj+QSqmqJ+rll4H4jJ4lnZt2XVajaj2M8h00qDLdCXLFt5CCsOApNooo2SKoxEaNMyrTdz4+6hQPdtNP0Efhd1g5J1rhPCfNMBlTbM8N3Nq62/l45nFiU2AqPMNEm/siy16UZE8sduehL+ZxYnXjEbFczvEBnsR6vOQjum1176nsVfo06rO64U92W46fm4lnRMRHbN8kF4vLyJw6rYYBiL8nV8b/srpiFrjLc+vJgKjUXqu21ZrpzxGXALyK8HdtmTJRxOMF201PJbEFVEQMC/JIJcPU3jptieC45GoohKZYlmiWNpNHkUmk6IRGtSy64O6Sbv4WrIbBRBLJmJZIq+E3zLxU7/B3N+bJHScbFJMAWoel9T3ttH7kWuhcUV40iViKUUVp9yvqq6RiqzsvDeCdgKJ7Xz5VeRZs930eDgopgF7kjmzv4/eu7ewLvP9Kr0/NfytTkeUzfWTfk67xLJc3Za88kH6zDNLRWlmjxWtbrD6mtTSLtAGczGYZPjr1HnT0m5RR6vMz+SAyS6lcI8HIlu6iPanqoIrvS48ihSCuFiA184540rSqkUtNigfEUs4YtePbNPi5ISQ15ConRx5qJotfmL/bdBX232iuhareLnSrrra65hEme2mz8VbSBcufz95W/9QMl/399Ex3LbxG9kBoK1uzbdybPzctlpkImzikegwwpNdTOpnEgzS55FbAVR6wIMTAA+saLWC1e/a8UXzNJeSJv5BkIdU5pblQ6ImV2nDUjlOIsgsSTxaaR+tlcZjQhzCG8stbW0bkgyqv0/0bVpZl6DaQf+uqULqoYuJ10HiqRyji4XXkfSyKomMLlC3tLKXLgD129rkvti2c5PX+fvoM2hTaq9LYmknGiExZruA8jG6SAQ9SSlm+RB5ZCdTe7Eqvk4XMPXCIHMAmcW1lVHlw0pWOavYGYhIJD/+M3HyIlPeR0tqYGBuDoWFikdvcaxoJZVescNmXdJx0N9LfyusTQZteIKem+lK5ray84TXmXgU/wB1Z4jEljY10xz0124i8PeL4vq6aqeSqGxSG7rJHTZORpQDioRZZil5msI6UZDvi8EtKr3kuRHR37LLkiWT6r7Ys5NloPJhZeudSLr5B+lYsnl4biVdmLJL6PWyFDPoJY8HRuKS+PuVyiZlm5ya+ZbIpFvN/uHdSXJLLS8N+ukzYaIFTzgoOlrmwVkWzMmhOLhD9JpufaxoZZfvyiGRqBFezt9Lf8uvSgrz5VzQbVd6Ro0mW8XkfFU2KAtHa9di/QNieSAgHpQAAB1ZSURBVOOMJCEjw1xvUa2XKe4SO2GU14fDyba6/DpRlXWQssn+ftEZYlTU9ZZr12IrPSQsgEQoG6WpbXHkGmelJxFMdRPBMZpbO5mkYkwW/IMn54uGaZqASNmXC6U31qoJeku5tctawYDYP9yVZJXLh+jzzHbXXtjCIbFOLKYV1SZv88W2wCWo9qi2otUEGR5nlym9lA5QRtZtr/N8O2nQyuZlXMw3vQW1rWoqx8R8d/X45RVvYTIQg176cefVzTkPAPGo6O4gxB0VydPIrYMyK5tfKfpLraGMdfkQqBukMi+WmwCcPGhpRxRqVLtKKvtia6qypJ3CdqeN5peFdULE5doqKnlR46hbi+0T7XeW1u1i2iG2MyplizwWm+WV/b9S8F5H7YUtGk0a8uXXiVJK0TVEtN+RGwYYc7TpE2W8aJlc9Kk2MOuj8Mprr5sL7qIBpm5wH3uVRCyTVlFRZHDdpHEaUFunK5dWpJdUt84ByTxO7fYoNwywDD3mFETxBCVbkF1Gxf+yS6Pa8jSq2wQgM8XRqDKPXJE8t7SntipLtsRxFybbD8NBsYbdlezakW1lAHGxWqCcX7RBVau6/H3jq7oAoPgKvYfqWrAIk+VcVRL7og9Who7rZBPbZXMAgIQs90nbHlG6oCSiZCkhy9a1VhEhrNy6BwCjvxWFBoqXKIv1Va8zWd6IS2K5RtnvKWuXWaZWsJXjolCjkHheLrK1zKOQL7MkKYUMh8irZBaL5SevtpmcbLfqdSZzazAKk4uvU9gvhcDDpHih2iBOLO1kuoDoBKp3SyiJThP+wSR89/eLubJyseKBiE7qdiFVW9WsqU0mjb1K0UL7f6HfwyHyuvUXtmqXEVfUiXcIwS5QSiRll5EY4BFNgmy7GU1Qs8f+3vEDJBxJbo0hEzJj/4maQgOAvAkPaQBVK4vE7TPcNmWrWCUJ6drOVvoeCY/C3NpMtb8HkPf3ya8mcbhtdDFwssmuHXASoRo+ykKLoD+Z3/JIXATc2h7FY6+QLdUsNU+WhsJBSigxNwnJgx4Rvi9K9urKhujy9cXX6DXqJgDZ2jW7vLbssCSSTLIKKhqjUJeL0LcqQi4ueI5Ye15Gz3PbReZ8Xc2FgEejdK8l5gKuUkXWwljRypIof68Iq85KkjfVzooLEiGOvSrCZGUgBiLz7LYrHjIQgzajPJeT1+WhWLIQcz45j5TJFHVpiMdK/e5Bxe6YRFw+SAkidV8sIJIzYtmqoBTSy+bhaoRQTQap67OiBWvQL+bHbcmaczicJLOq4Wtb7fnlNju1mZ2c89bvWKpuGDiL3kdcoc9d7nOW/a6AZC0bLn0mpd1iC6JYGlKTXNEY4B8GnCyY49nssS4wxmgMBIPUX6lmS94O1BRaFHeSQNTtX9GoqHjKJeFvfWd9SWk3DciaOd+IKNRA7Za+8mESq+wxFQ7SIHQLovfxOuHhhmrL+wAK5+MyefVsd7K0I7fztZ2TFCUUXxUtbRQR+/uVi8Va8uDlgyRsHtH7yp1Jn4UMX9uU6KS6TU5ZQpLncuv6O8kuH7kzRQtakUziqO0ZBYiLWFhNMpFgs/Qd1BdlxEWguJOWfLz5iu2tj/Girc5pc8uT/kpAUmghQ+XS7qRIotqkLUoGTrUcjydld23nKF7zgBhcSqa22lQ8M75QIxwWmxPOFJ0eekl80vPJjDCXhR/ifchEGmNijiv35e5R9puKNWPZn1htAF45RnZycXe9TKdYwhoT69dF8n48oj5McMQWPdmPWGyTq/d6Y6+MX9qptobtqu23xSOx/KZkmssHk831+bViHVa0gM101j439pPuI9nl1SUf62m1QS75KHPByjHK+ObOTMLCaGz89q+SLKfbkIizuEN0hFDEUTlG2+nUzhPVua2H6j1kAVEoIPagegto94+/D8h0kEgL62g5qrRXFPqvS7xZKNZI3TZQhCD2u8qMdE1Bh9r5QdgeDNC5AdGQrktcHET4K/cAgyUVVGqnSnWbnKfMH0s7Re2y4s2h3rBLtnbdL5aR5tWWPco7CcY+nT/sFx43FlVZyncXV0SERLueeFwCC4foe7Ki1YMo9sEc5WMIB8UgnSd2sIjdPfVrhFLINZ5rJ5Lbdsjevf006NwFyh0HYuFhXTFAxfwuHBa7i8TWtoxYUsmtoONkl9E8UyanamqUZT/gReKiIUL1ityvqiR+yodE0mYtqrfulEUiMiObXSqOuU/UGYuWL3ITgFyvrd7Jb2jibXL+fiqKaKtvyCZ37YgIpXyYpgr1O6aCXrKVxyTkqCia4WXoM8op3Rp5IMo+Y3FcTplq5oKxjPW0uhCHfnITLjlIeSzapOwnYbJs7e6cSs/47vpyHqcWVITDNBjVze2ASLJADFCx5BIXRSF+FxDJW0GKzo+VHjpudlkSPubra5TlnQCGE28YjdCcU63prRxX5pCyo2NZbHMrKBenUCztdCce1lskooZBMYcUr4/GxDQhXyu4yjGxKaHuDoHF1yisl9n3ynGKRMY1wzuS3L7TW0jfS3hCZM8rteeSGwlk2adTAIqv021BvAUiErJzWi3wsh00gOS9beT8snJcZGVd1PTejUviFhbKeqjso5RbUTdflXM+ZWnFF2Etj5TElQh3vcVJN/+y2NImm7F5neI8vqgs6qo9pltI5rtOTqwPy3Yt8kZaoiZX7vOlkydLXU57UgBR2i82TQwl+2Blf2V1HZpXkm1y6iaAye4QKPe6yufK3T1xQOeu3qB6OCmqcLL0f7khIRytvQiCVze9U7Z5vvi9JBrpZeycVktkJZNToLlTNEohYO6MOi+xU2wQF8sb5YOiKbnSvFz23pVrsdX57k6RES7VFgCU9oibb4n11GAAtF3PT5IslWNiLXRhXZgudvNU65zbxUZ22b5GXDDiMaUbRV2/KR7VFnTIW3YwT6yFdidJM7ddiTq4uE+R2CYn8wPVXsyLauem8r48edEfSq2lVmus5bkyi+iY3kL6nL2u5MIkP1OALhpxWWwu6EySfvk1lBOwiSi9YPKL5GEyV4qKoKJ8pckZkGRA5cbr8mFl/6baaFzcQzZ3RrLQL1uzxqXaulzZ1TEcI4/KK+SlwJON69IbuXVroZWjYmknSDK9gNKJX84jo/F3TweSNV51uUr2jHIyZENuZRJ61u/plReh+tumFF8VzcInW9rpQPXWoU5WtPQRoTYPhOA7RPJP3LE+uyxJxKnnkp47I/pwBT108cuQh+fgYGB03Lgy5VhoFYwXLWeyuoLToI6LohRxYd1mgV1iv6kI6ypHk95QNZvbd1EIW1inbN3rpTkbQlEXLO+XI4oleEDnZnlxH9hsUlNbTRApNwUDxJa8/trKIEDMF0OR+BFf7+gr47tEVI7TBUc9ruz55M6vbXEqvamaTPL30sWtvgNidWlHbYVat7QjhcmyoopKtkflyUUsKopSyQNiQ/ux8ctI/j76vlxx0QyHUG3QJ1vy8BiIx8AcF1yT4a7Hu5gNUrPeQuVK7E4Q1im1x5XjlJV16oRUXYs9I/Ec4aBIpri182DZxVDeEiTThWrvYEDs2lGWhdS1ULk5350HyNuEACIZVqRIQC4DyR5UarVTMCB2/XhCmEzpQdWVdLQAQ82Nm6sb9vckc211Caz46gRLO5yWdjy5tKOWIRbqIhQhZNn9o3Ik6bE1rtBCfNZOno4rcwh19xniwQBtCmEZbYorvOmfojscB75XxoHvXZe2IZY55Nz//kZt5rTGi5YHJwAAl2z9YsqWWOaKZ7bdJjZL6CFas8PjSOzgsWgPY9DG05otWnd+sgHcojdxWbmTX2tjtmgBcLk2aNEa5uTA1eW7FsZ40VoMwS0AcUTLWi2OFW1yYxCLxjDGEJcPipuNtTZWtJokJyzTEPtJwUqLY7xorZ81A8bcpB1ti2O8aBm3sjUB5mTAw+G0zWgIxosWVrRmEPtKR8fWxnjRWsmaAXM8cE0KAI0XLWATUUbgLdJmw4AVrfW1RmD7HuuEvJOcRW+YI5rPH0jbklljvGi5uqlac3bu24//+pGrkX/r+fijz/wZBoaG0japabBoBLzSi5o7x7corf8OZosh2eOBoSF87n/+Nf7XX34B/vPP4er3Xo67f/pQ2mY1D9lTSoPiCj3SabNCj3nOdOzYuw+bN23E5k0bAQBXXf6elC1qLgwc3LM34NICboin3XfkCNrb2vBHn/kzI8NjZGz2WCPMEC0A3PfzR3DnX/wP+M8/h82bNhoVHts7DOhE5XjaFjSND77rUmxYQz2L3/l7v4ftL75kjrdljjabQ6xoNbk7+HSsWbECR3p6UCqX0zYlFWyzco3gmjSwno5z1q7B8OgoDh49hlK5jB8/+ig2b9qIzo6OtE1rEpH1tNqg3mdGYzo7OvDFa6/Fx/7yRiza/A4AwJ9/4uMpW9U8WDgEHodpm9EQ7JKPIdljANiwZjX+/YH70zYjHbJdQGU0bSsagvGelhuUPTYZ5uTsnFYbNPkiLVPDohErWn2wntYIMovsXfN0wZSKKNNh4QnwaCxtMxqC8aK1ntYUIsBpS9uIhmBFq8k8xzI1LNtt57TaUGn9jvOW6Yl5BB7ZOa0WcK7Hgrtlahy3AOa4aZvREIwXbfXO7BZLi2BFaxNRZqDJfBawotUmOWGZBg16Q0n0eSenjPW0JsCgzzdtRWuLKywthvGitRsGLK2G8aK1ntYU9AmQ7X5a0UL1mW23pWyHxTIzrGiFp71k6xdTNsQyV+h2QTY+PLZzWkurYbxo7ZzW0mpY0cbFtC2wWE4K40VrSgtV49EneWxFC4NudWk04QgAey8fPbBzWjMI+4FIjxuIW9HqEjNZpsEB3AVpG9EQjBetbexmCNll0GW46/EuZoPtXGEGTjZtCxqG2aLlMRAMpG2FpRnEFegyFTJbtP5ecENudWk8Ti5tCxqG2aItnIXSyLG0rbA0A39/2hY0DLNFC6DQsS5tEyzNILs0bQsahvGiNWnDwLZ77kX+redXf37y2ONpm9Q8nELaFjQMuzUvHErbgqZQKpdxpKcHT3/vf2Pzpo1pm2OZBcZ7WlMo+T6GR0exeOHCtE2xzBLjRcudeWmb0BT6Bk/gtb378JYrrkT+refj+q9uQ6lcTtus5qLJ5hDjRatTE+up6D9xAt2LF+PI009icPu/AQC++cMfpWxVEwn6gLikhXCtaA1JRG3etBE///a30NnRgUIuh4++973Y/uJLGBgyY06POADcghaVUcaL1uQ7DKxesRyFfD5tM5pDZhHAWl+wgBWtMVvzfvLY49h2z70AKJP840cfxTvOOw+FnD6VQlPi6HNxsqKFGZ72qsvfAwDIv/V8LNr8DqxYurT6mAn4Q3sR+nrUmRu/TmvS1rytW67B1i3XpG1GKuQXrETg96ZtRkOwntYQT2s8Gm0MsaI1yNNa9MB40ZoUHlv0wHjR2vDY0mpY0VpPa2kxjBetycUVltbEeNGaUsZo0QfjRWs9rSEEPUA0lrYVDcF40VpPawg8Blw9tmFa0ca277ER2B5RmsADcE1CJss0MH2Guj7v5FSIywAzvvzaDOKKNjMhs0XrtmtVk2qZgkoPwPVor2O2aAHEkR5fpGUavHaA6bF32HjRMseGx0bgLYIu8bEdsaKM8Zltt6VsiMUyM4wXrSyuuGTrF1O2xDJX6HZBNj48Bg/StsDSLDT5rq1o4aZtgKUZxCUgGgXC4bQtmTXGi5bb/bRmUDlGS3zegrQtmTXGi9bupzUEr0ubNXkrWrvLxwy8+Wlb0DCMF61J96e16IHxogW3u3yMIRqjG3G1OFa0YGkbYGkG5cMAOJDpStuSWWO8aG0LVUPgFbsJXhtsIsoMssuhS1RlvGhtIsoQnLw237TxorWe1gz08LGEFa0211+LKRgvWhNbqO7ctx/v+8z12Llvf9qmNI1S37OIKq1fdwxY0RpXxlgql3HXj3+Mnn49brA8U/Kdm+BlO9I2oyFY0RoWHv/syaewoL0dSxd3pm1Kc2EuwPSY2RovWpPC45379uPxf/1X/NHFF6dtSgpw6JKOMl60JoXH/+cXv8CnPvxhLF64MG1Tmg7nHMx6Wl0ww9Nuf/ElAMDmTRtTtiQtrKfVBlPKGJ9+9ll85Tt3I//W8/GWK67EL7f/P3zsL280J4PMuZ3T6oMZnnbrlmvgP/8c/Oefw8sP/1+8e/Pbcd/tX8OGNavTNq05RKPQZbjr8S5mgyGe1nR4HGgzp7UtVA3KHks2rFmNR779t2mb0Vy8+QCOpW1FQzDe0xY6zkrbBEszsHNafSideD1tEyxNgEdjYDZ7rAd2a54hBH3atBYyfk5rE1GGwLKAo8d3bbin5TCt9thY3AXa3A1ej3dxqmiUnLBMDXcydk6rAxxcmy/SMg0aXaCNFi3NZ/X4Ii3Toc93bbZooc/V1zIN1tPqgj5XX8vU8HAYLC6lbUZDMFq0Ou2xtExDNASwXNpWNATD12k5DL9umYO3CIj0WN4ze8RqNM+xTA1nOW2iKrNFa+e0BqHPd220aGlOm7YVlqYQjWoTVdk5rbhuPbPttnRNscwt4QjgZdK2oiGYLVplTnvJ1i+mbIxlrnhm223g3kIwRw/RGh0e6zTPsUwDy0CX79po0XLONfkaLdPCY7vLRwt4AFO6MZqOTptDzBatv1+bq69lGjRakzd7xObXAszsXJwxRGOwc1oN0ClkskxDNApAjx5RRos2LPWDOdbTmgB3F4CxbNpmNASjRevlFxnZrNxIWMbOafVAn+SEZTpi6DLc9XgXpwit01rRGoHNHuuCrYgyBR772lygzRatRldfyzTEJW2+a7NFaz2tOTjt0OW7Nlu0hu2n3XbPvci/9Xzk33o+fvLY42mb01Q4mO1coQMm3Xxr+4svAQD855/DkaefxP2PPlZ9zAz0iaoMrywwp7Hb5k0bsXnTRgBAZ0cHNm/aiH1HjlQf055wWJs6cz3exanCoU1y4mQYGBrC9hdfwpoVK9I2pWlElREExd60zWgIZotWo5Bppvzkscex4p3vwuoVy7HpDeembU7TcPJLkc16QKUnbVNmjdGiNbFZ+VWXvwf+88/hHeedh7/46ztRKpfTNqk5REW6qXR2adqWzBqjRQtwgJslWsmaFSuw/8hRlHw/bVOaQ1wBst1pW9EQrGh5kLYRTeEnjz2ObffcW/396WefxeZNG9HZ0ZGiVc2Du/MA5qZtRkMwW7ScA44e27Wm46rL3wMA1XXaIz09+PNPfDxlq5qJo81UyOglH9oEbw5bt1yDrVuuSduMdIjGoIuP0uNdnCqcAwYVWBiNk9dmec9s0YJrM8+xTI1OrYWsaG0LVTPQaEeX2aKNxsBjQ9YpjUefQhqjRcudApiTT9sMSzOwnlYPgrHjiG1jNyPgiO2cVgcybUvhuGas0xoP53aXjxYwJpZ9LPpj57RawOCA2+yxEei0OcRo0VpPaxLW02qCFa0x2OyxHjDGbHhsDNbT6gFz6A7hFu3hUQnMZo91QI8rr2UmcMDfm7YRDcFs0dpElDnwCMivTtuKhmD0floGVu19/My221K2xjKXcCcPxjJpm9EQjBat6mkv2frFlI2xzBXPbLuNvudoKG1TGoLZ4TEc2K15hhCXgKCP/t/iGC1axhi4ndOaAQ+B3HLAKaRtyawxWrSUPbaiNQHOMmCuHp0nzRatzR4bhGsronSAwQHnUdpmWJqCrYjSA8agyxdpmRq7y0cb7JzWHKyn1QM7pzWHuAKUD6VtRUMwWrRReQiONy9tMyzNgEdAbmXaVjQEo0Xr5TsRBcNpm2FpApx5YI4ejemNFq2d05qGndO2PMzOac3Bdq7QBetpjYEHQDSSthUNwWzRGuRpS+Uyrv/qtur9aa//6jaUyubcEoXzCMydn7YZDcFs0cIxRrQ/e/IpvOO88+A//xwGt/9b9TFjYC7A9NiJqse7OEWosZsZopV3ggeAQi6Hd5x3Hv7thRfwwXddikIul6JlTYLDzmm1gJk7p917+DBWLF1qhmBh70+rEWaKdvuLL2H7iy/hug/9t7RNaR4aZY9teGxYC9XtL76EG26/A/fd/jV0duixv3RmxNBlndZo0VKgYY6n/cljj+P+Rx/DE9/9jmGCBTLZBYiCUXi5hWmbMmvMDo8NWvLZ/uJLuP/Rx/CDbbcZJ1gAqJRPwMvq8b7NFq0m4dJMePrZZ/GL7dux4p3vMnOtlkfa3J/W6PDYpMZuW7dcg61brknbjNSgPJQeF2k9Lj2njJnZYyPRyNPq8S5mgyZXX8s08BiIimlb0RCMF60uC+6WqeHgYJ6tPdYD62nNgHMbHutCdt6KtE2wNAEqY9RjuOvxLmZBUOxN2wRLM+CxNlGV8aJljtGrXuagSWgMWNFa0RqCTglHK1pNQibLNFhPqw/MMWM/qekwAIj9tM1oCFa0rg2PjcBxACefthUNwYqWZdI2wdIU9Bnq+ryTU0SXrvOWqWFw7L18dIE51tOaAQcqPbRxoMWxotWkraZlOjhQOItaqbY4dsSK8PiZbbelbIhlTnFcwNOjc4XxonVEccUlW7+YsiWWueKZbbdpFVHZ8FijL9NiBsaLFraM0RD0Ger6vJNTxIFZfY9NRadyVeNFq9F3aZkKjb5n40ULTVqQWKZBo/59xos2DobTNsHSDDRYn5WYLdrYh+fq82VapsCGx5rg5MEyi9K2wtIE7CZ4jXA8PbZrWczBeNHaTfCGwEMg1uO+RVa0trjCDJgLaHKBtqK1W/PMQKNyVStaK1oj0CcNZUVrZLuZbffci5889njaZjQVrlHpmxUtH03bhKay7Z578ZXv3J22GU3HLvlohJPRY2P0dJTKZVz/1W0AgC996rqUrbHMBuNFy9z2tE1oCoVcDn9701Zz7wbPK0AwkLYVDcF40VoMQpPqNytaixk4WeiSQ7aitRiCHoIFrGgtxmBFa7G0FlyftkL61HadIho1NJgxRmaQeQWoHAWyy9O2ZNZYT2sxA5YBojEt7udzyqLVqbudxQB4SMLNnZm2JRNyMnqakWi1FiivpG2BpSkwIL86bSNOisl0Z3Z4zGOa51j0h7nA6MtpW9EQTkm02nhe5gCGlDEaT1wGskvTtmJKZqqrkxatNoKVeJ1pW2BpBswBssvStmJaZqIvs8NjizkwPVrNAFOIdiLFa+dlLQbROivy02lvQtHORJxWwBZL4zgZzU0ZHqsHmuzfFktrcPp72pnqbdo5bf0L5O9WuJZWgsen93r8ZLqaSGfOVH+c7ICMMStaS2vBYyD207ZiUlRNTecYZ1wRVY2nHceK1tJ6OFnAOX1vASM15ThOze8TMU60U7npeuHGsQbbncLBtC2wNIE4On1vCRLH8bSCVXU5paeV4lRfqB54ZGSkocY3nfCENs2+LFMTBadvq9yRkZFxDlGiak7iqX/knKP+d6l6+eIoiqoHHhigAT9//vxxB24JvIXVKplntt2WsjGWuSSTO/2ausVxjJGREQwMDMB13aqG1CnoRJEvi+O4qlTOec1PHMfVnyiKan6CIBj3b/k89XUyhFaPa7HoTL3gHMep+ZECdV0XmUwGruuO+7f8UV8njzlh5wrV69Z7Wilm13WrInQnuJu6fP5MRGuFbGlVJqtemix5qwpWFaXrulXNTORp1XNN2W5GFV3NRFiIVxWrPEEcx9XXSXGrwp0MK1xLqzGTZVI15K33thN51ImWfcbNaeu9KoDqXFY+Ll8kf68Po1VDoyiqEbb6nIk8rRWrpdWZaqVF9ZhSF6q3rRdz/U/9OSYNj+Uf68VbL8aJDqh6WfV5ky0PWdFaWp1J11PrlnBUbzqVeCcKidXHPPnAZJlj9eQAquFv/QFlaCzXnNSwWL6uHitYiy5MWG6o6GayMLletKq46wuZJp3T1ntWddlHDZPrDVK960Retj5ZZQVr0Y2phKtqaCKvO9G/J1zuUcPjqbyt+n9phPSo6t+leGUIDdh5rMUsZjK/VQU6kZDV40waHs/UAFWUQG1iShX1RPNYK1SLaaj6qfe49ckpNZKtX/Kp1+H/B05iNMBDuQ4mAAAAAElFTkSuQmCC)
实现
存在两种实现方式,第一种是数组实现的顺序栈,第二种是链表链式栈
数组实现
数组实现我们直接使用了 slice ,并且借助 slice 实现了自动扩容
// Stack Stack
type Stack struct {
items[] string
current int
}
// NewStack NewStack
func NewStack() * Stack {
return &Stack {
items: make([] string, 10),
current: 0,
}
}
// Push 入栈
func(s * Stack) Push(item string) {
s.current++
// 判断底层 slice 是否满了,如果满了就 append
if s.current == len(s.items) {
s.items = append(s.items, item)
return
}
s.items[s.current] = item
}
// Pop 出栈
func(s * Stack) Pop() string {
if s.current == 0 {
return ""
}
item: = s.items[s.current]
s.current--
return item
}
链表实现
链式栈的实现我们利用双向循环链表,简化栈的插入操作
// node 节点
type node struct {
prev, next * node
value string
}
// Stack 链式栈
type Stack struct {
root * node
len int
}
// NewStack NewStack
func NewStack() * Stack {
n: = & node {}
n.next = n
n.prev = n
return &Stack {
root: n
}
}
// Push 入栈
func(s * Stack) Push(item string) {
n: = & node {
value: item
}
s.root.prev.next = n
n.prev = s.root.prev
n.next = s.root
s.root.prev = n
s.len++
}
// Pop 出栈
func(s * Stack) Pop() string {
item: = s.root.prev
if item == s.root {
return ""
}
s.root.prev = item.prev
item.prev.next = s.root
// 避免内存泄漏
item.prev = nil
item.next = nil
s.len--
return item.value
}
典型问题
实现一个计算器
我们实现了支持+、-、*、/、(、) 的计算器,这也是leetcode#244的一种解法,并且我们这个实现更加复杂,原题只需要计算加减法
package calculation
import (
"fmt"
"strconv"
)
// 操作符的优先级
var operatorPriority = map[string] int {
"+": 0,
"-": 0,
"*": 1,
"/": 1,
"(": 2,
")": 2,
}
// Calculator 计算器
type Calculator struct {
nums * StackInt
operators * Stack
exp string
}
// NewCalculator NewCalculator
func NewCalculator(exp string) * Calculator {
return &Calculator {
nums: NewStackInt(),
operators: NewStack(),
exp: exp,
}
}
// Calculate 获取计算结果
func(c * Calculator) Calculate() int {
l: = len(c.exp)
for i: = 0;i < l;i++{
switch e: = (c.exp[i]);
e {
case ' ':
continue
case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
// 一直往后获取数字,如果下一个还是数字说明这一个数还不完整
j: = i
for j < l && c.exp[j] <= '9' && c.exp[j] >= '0' {
j++
}
n, _: = strconv.Atoi(c.exp[i: j])
i = j - 1
c.nums.Push(n)
case '+', '-', '*', '/':
// 从计算符栈中获取栈顶元素,如果当前操作符的优先级低于栈顶元素的优先级
// 并且栈顶元素不为空,和括号
// 那么从数据栈中取两个数据和栈顶操作符进行计算
pre: = c.operators.Pop()
for pre != "" && pre != "(" && operatorPriority[string(e)] <= operatorPriority[pre] {
c.nums.Push(c.calc(pre))
pre = c.operators.Pop()
}
if pre != "" {
c.operators.Push(pre)
}
c.operators.Push(string(e))
case '(':
c.operators.Push(string(e))
case ')':
// 碰到右括号之后就一直不断操作符栈中弹出元素,并且取两个数据进行计算
// 直到碰到左括号为止
for o: = c.operators.Pop();
o != "(" && o != "";
o = c.operators.Pop() {
c.nums.Push(c.calc(o))
}
default:
panic("invalid exp")
}
}
// 最后如果不存在操作符,说明数据栈中的栈顶元素就是最后结果
o: = c.operators.Pop()
if o == "" {
return c.nums.Pop()
}
// 如果存在,就把最后的数据进行计算后返回
return c.calc(o)
}
// calc 单次计算操作,o: 计算符
func(c * Calculator) calc(o string) int {
b: = c.nums.Pop()
a: = c.nums.Pop()
fmt.Printf("%d %s %d\n", a, o, b)
switch o {
case "+":
return a + b
case "-":
return a - b
case "*":
return a * b
case "/":
return a / b
}
return 0
}
// calculate 计算器,支持加减乘除
func calculate(s string) int {
return NewCalculator(s).Calculate()
}