概述

<div class="markdown-here-wrapper" data-md-url="https://i.cnblogs.com/EditPosts.aspx?opt=1"&gt;
<h1 id="-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 24px; border-bottom: 2px solid #aaaaaa;">栈
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">栈是最简单的数据结构，也是最重要的数据结构。它的原则就是后进先出（LIFO），栈被使用于非常多的地方，例如浏览器中的后退按钮，文本编辑器中的撤销机制，接下来我们用Python来具体实现这个数据结构。

一个新的栈类,代码如下：

 :
    
<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;<a href="https://www.jb51.cc/tag/init/" target="_blank" class="keywords">__init__</a></span><span class="hljs-params" style="color: #ffc58f;"&gt;(self)</span>:</span>
    self._data = []

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;__len__</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self)</span>:</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> len(self._data)

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;is_empty</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self)</span>:</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> len(self._data) == <span class="hljs-number" style="color: #ffc58f;"&gt;0</span>

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;push</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self,e)</span>:</span>
    self._data.append(e)

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;pop</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self)</span>:</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> self.is_empty():
        <span class="hljs-keyword" style="color: #ebbbff;"&gt;raise</span> Empty(<span class="hljs-string" style="color: #d1f1a9;"&gt;'Stack is empty'</span>)
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> self._data.pop()

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;top</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self)</span>:</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> self.is_empty():
        <span class="hljs-keyword" style="color: #ebbbff;"&gt;raise</span> Empty(<span class="hljs-string" style="color: #d1f1a9;"&gt;'Stack is empty'</span>)
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> self._data[-<span class="hljs-number" style="color: #ffc58f;"&gt;1</span>]

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;<a href="https://www.jb51.cc/tag/init/" target="_blank" class="keywords">__init__</a></span><span class="hljs-params" style="color: #ffc58f;"&gt;(self)</span>:</span>
    self._data = []

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;__len__</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self)</span>:</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> len(self._data)

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;is_empty</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self)</span>:</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> len(self._data) == <span class="hljs-number" style="color: #ffc58f;"&gt;0</span>

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;push</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self,e)</span>:</span>
    self._data.append(e)

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;pop</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self)</span>:</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> self.is_empty():
        <span class="hljs-keyword" style="color: #ebbbff;"&gt;raise</span> Empty(<span class="hljs-string" style="color: #d1f1a9;"&gt;'Stack is empty'</span>)
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> self._data.pop()

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;top</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self)</span>:</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> self.is_empty():
        <span class="hljs-keyword" style="color: #ebbbff;"&gt;raise</span> Empty(<span class="hljs-string" style="color: #d1f1a9;"&gt;'Stack is empty'</span>)
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> self._data[-<span class="hljs-number" style="color: #ffc58f;"&gt;1</span>]

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;<a href="https://www.jb51.cc/tag/init/" target="_blank" class="keywords">__init__</a></span><span class="hljs-params" style="color: #ffc58f;"&gt;(self)</span>:</span>
    self._data = []

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;__len__</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self)</span>:</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> len(self._data)

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;is_empty</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self)</span>:</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> len(self._data) == <span class="hljs-number" style="color: #ffc58f;"&gt;0</span>

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;push</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self,e)</span>:</span>
    self._data.append(e)

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;pop</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self)</span>:</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> self.is_empty():
        <span class="hljs-keyword" style="color: #ebbbff;"&gt;raise</span> Empty(<span class="hljs-string" style="color: #d1f1a9;"&gt;'Stack is empty'</span>)
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> self._data.pop()

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;top</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self)</span>:</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> self.is_empty():
        <span class="hljs-keyword" style="color: #ebbbff;"&gt;raise</span> Empty(<span class="hljs-string" style="color: #d1f1a9;"&gt;'Stack is empty'</span>)
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> self._data[-<span class="hljs-number" style="color: #ffc58f;"&gt;1</span>]

 :
<span class="hljs-keyword" style="color: #ebbbff;"&gt;pass</span>

<span class="hljs-keyword" style="color: #ebbbff;"&gt;pass</span>

<span class="hljs-keyword" style="color: #ebbbff;"&gt;pass</span>

 sys
data = []
 _  range():
    a = len(data)
    b = sys.getsizeof(data)
    print(.format(a,b))
    data.append()

添加中，data的占用的字节每次增加的是越来越大。这是由于list在底层还是基于数组实现的，它每次都会先申请一个长度，当占用的字节要超过最大范围时，再将数组的大小增加。

增加数组长度的时候，这时的消耗必然比只添加数据时要大，所以在某些情况下，我们的栈的实现，可以增加一个设置固定长度，提前将所有位置初始化为None，那么在程序运行时，就会减少了再增大底层数组时的开销，这样做有时会非常有用。

如果您也喜欢它,动动您的小指点个赞吧