Python：栈和队列的 python 列表实现

柔情只为你懂 2023-07-25 06:16 26阅读 0赞

# 1. 栈 #

## 1.1 栈的基本概念 ##

栈是一种简单的数据结构，是由一系列对象组成的集合，这些对象的插入和删除操作遵循“后进先出”的原则。可以在任何时候向栈中插入一个对象，但是只能取得或者删除最后插入的对象（即所谓的“栈顶”）。

## 1.2 栈的基本操作： ##

假设栈为 S，栈的基本操作：

1.  S.push(e)：将一个元素 e 添加到栈 S 的栈顶；
2.  S.pop()：从栈 S 中返回栈顶的元素，如果栈为空，这个操作将提示错误。
3.  S.top()：不移除栈顶元素的情况下，返回栈顶元素；
4.  S.is\_empty()：判断栈是否为空
5.  len(S)：返回栈中元素的数量

## 1.3 栈的 Python List 实现： ##

class Error(Exception):
        pass
    
    
    class ArrayStack:
        def __init__(self):
            self.__data = []
    
        def __len__(self):
            return len(self.__data)
    
        def is_empty(self):
            return len(self.__data) == 0
    
        def push(self, e):
            self.__data.append(e)
    
        def top(self):
            if self.is_empty():
                raise Error('Stack is Empty!')
            else:
                return self.__data[-1]
    
        def pop(self):
            if self.is_empty():
                raise Error('Stack is Empty!')
            else:
                return self.__data.pop()
    
    
    if __name__ == '__main__':
        S = ArrayStack()
        S.push(5)
        S.push(3)
        print(len(S))
        print(S.pop())
        print(S.is_empty())
        print(S.pop())
        print(S.is_empty())
        S.push(7)
        S.push(9)
        print(S.top())
        S.push(4)
        print(len(S))
        print(S.pop())
        S.push(6)

结果如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU4OTU3NQ_size_16_color_FFFFFF_t_70]

## 1.4 时间复杂度分析： ##

基于上一篇博客[Python 序列：列表 (list)，元组（tuple），字符串（str）深入分析（包括扩容和摊销）。][Python _ _list_tuple_str]关于 append 摊销的分析，这里的时间复杂度分析就很简单了：

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th align="center">时间复杂度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>S.push(e)</td> 
   <td align="center">O(1)</td> 
  </tr> 
  <tr> 
   <td>S.pop()</td> 
   <td align="center">O(1)</td> 
  </tr> 
  <tr> 
   <td>S.top()</td> 
   <td align="center">O(1)</td> 
  </tr> 
  <tr> 
   <td>S.is_empty()</td> 
   <td align="center">O(1)</td> 
  </tr> 
  <tr> 
   <td>len(S)</td> 
   <td align="center">O(1)</td> 
  </tr> 
 </tbody> 
</table>

## 2. 队列 ##

## 2.1 队列的基本概念 ##

队列是一种简单的数据结构，是由一些列对象组成的集合，这些对象的插入和删除操作遵循“先进先出”的原则。可以在任何时候向队列中插入一个对象，但是只有处在队列最前面的元素才能被删除。队列中允许被插入的一端称为队尾，允许删除的一端称为队头。

## 2.2 队列的基本操作： ##

假设队列为 Q，队列的基本操作：

1.  Q.enqueue(e)：将一个元素 e 添加到队列 Q 的队尾；
2.  Q.dequeue()：从队列 Q 中返回队头的元素，如果队列为空，这个操作将提示错误。
3.  Q.first()：不移除队头元素的情况下，返回队头元素；
4.  Q.is\_empty()：判断队列是否为空
5.  len(Q)：返回队列中元素的数量

## 2.3 队列的 python list ##

这时候一个简单的思路就是和栈一样，插入使用 append，删除使用 pop(0) ，但是这有一个问题，就是 pop(0) 的时间复杂度是 O(n)，那么有没有和栈一样时间复杂度都是 O(1) 的实现方法呢？

这个时候可能会想到这样做，我们可以使用一个变量来保存第一个元素（即队头）的索引，每次删除元素之后，这个变量就指向下一个元素，先前的队头元素变为 None，这样就不用了每次出队之后用后面的元素覆盖前面的元素。这样时间复杂度确实是 O(1)，但是空间呢，这个时候底层数组的大小就变成了追加元素的总和，即使我们出队了很多元素。举个例子：比如一个队列入队了 10000 次，出队了 9990 次（假设每次出队时队中有元素），那么最后队列中有 10 个元素，但是实际底层列表长度为 10000，而更底层的数组可能更大（动态数组），这就有很大的空间浪费。

那么到底应该怎么办呢？

可以使用循环数组解决，基本操作和上面一样，只是我们让队列的元素在底部循环。

1.  假设底层数组的长度初始为 N
2.  出队的时候，前面的位置就空出来了
3.  入队的时候，如果到了数组的尾部，那么看前面位置是否用空，如果有，那么放在数组的前面，如果没有，申请更大的数组来保存。

这样，最后队列的空间利用率就高多了。  
具体实现如下：

class Error(Exception):
        pass
    
    
    class ArrayQueue:
        DEFAULT_CAPACITY = 3
    
        def __init__(self):
            self.__data = [None] * ArrayQueue.DEFAULT_CAPACITY
            self.__size = 0
            self.__font = 0
    
        def __len__(self):
            return self.__size
    
        def is_empty(self):
            return self.__size == 0
    
        def first(self):
            if self.is_empty():
                raise Error("Queue is Empty")
            else:
                return self.__data[self.__font]
    
        def dequeue(self):
            if self.is_empty():
                raise Error("Queue is Empty")
            else:
                res = self.__data[self.__font]
                self.__data[self.__font] = None
                self.__font = (self.__font + 1) % len(self.__data)
                self.__size -= 1
                return res
    
        def enqueue(self, e):
            if self.__size == len(self.__data):
                self.__resize(2 * len(self.__data))
            avail = (self.__font + self.__size) % len(self.__data)
            self.__data[avail] = e
            self.__size += 1
    
        def __resize(self, cap):
            old = self.__data
            self.__data = [None] * cap
            walk = self.__font
            for k in range(self.__size):
                self.__data[k] = old[walk]
                walk = (walk + 1) % len(old)
            self.__font = 0
    
    
    if __name__ == '__main__':
        Q = ArrayQueue()
        Q.enqueue(5)
        Q.enqueue(3)
        print(len(Q))
        print(Q.dequeue())
        print(Q.is_empty())
        print(Q.dequeue())
        print(Q.is_empty())
        Q.enqueue(7)
        Q.enqueue(9)
        Q.enqueue(10)
        print(Q.first())
        Q.enqueue(4)
        print(len(Q))
        print(Q.dequeue())
        Q.enqueue(6)
        print(Q.dequeue())
        print(Q.dequeue())
        print(Q.dequeue())
        print(Q.dequeue())

结果如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU4OTU3NQ_size_16_color_FFFFFF_t_70 1]  
我们设置的初始大小为 2 是为了方便测试，一般可以设得大一点。我们的扩容方法是扩大为原来的 2 倍，这样摊销的时间复杂度为 1，具体原因参考 [Python 序列：列表 (list)，元组（tuple），字符串（str）深入分析（包括扩容和摊销）。][Python _ _list_tuple_str]

def __init__(self):
        self.__data = [None] * ArrayQueue.DEFAULT_CAPACITY
        self.__size = 0
        self.__font = 0

初始化中，\_\_size 是队列实际元素的多少，\_\_font 始终指向队头元素。

def dequeue(self):
        if self.is_empty():
            raise Error("Queue is Empty")
        else:
            res = self.__data[self.__font]
            self.__data[self.__font] = None
            self.__font = (self.__font + 1) % len(self.__data)
            self.__size -= 1
            return res

再来看出列操作：如果为空报错，反之进入 else。然后由于 \_\_font 指向队头，那么返回值为 res。后续把出队位置的值设为 None，然后 \_\_font 变量后移，由于是循环使用，所以是 + 1 之后模底层数组的长度。最后队列元素的总和 -1。

def enqueue(self, e):
        if self.__size == len(self.__data):
            self.__resize(2 * len(self.__data))
        avail = (self.__font + self.__size) % len(self.__data)
        self.__data[avail] = e
        self.__size += 1

再来看入队操作：如果底层数组满了，那么就申请一个 2 倍数的空间。然后可用位置索引为队头加上队列长度去模数组的长度（还是由于循环使用）。最后赋值，队列长度 + 1。

def __resize(self, cap):
        old = self.__data
        self.__data = [None] * cap
        walk = self.__font
        for k in range(self.__size):
            self.__data[k] = old[walk]
            walk = (walk + 1) % len(old)
        self.__font = 0

最后是申请的时候，回申请一个 2 倍的空间，然后将原来的队列元素放在新数组的开头位置。相当于重新摆放，让前面的空位置没有了，然后重新设置指向队头的变量 \_\_font。

## 2.4 时间复杂度： ##

最开始简单的类似于栈一样的实现：

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th align="center">时间复杂度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>Q.enqueue(e)</td> 
   <td align="center">O(1)</td> 
  </tr> 
  <tr> 
   <td>Q.dequeue()</td> 
   <td align="center">O(n)</td> 
  </tr> 
  <tr> 
   <td>Q.first()</td> 
   <td align="center">O(1)</td> 
  </tr> 
  <tr> 
   <td>Q.is_empty()</td> 
   <td align="center">O(1)</td> 
  </tr> 
  <tr> 
   <td>len(Q)</td> 
   <td align="center">O(1)</td> 
  </tr> 
 </tbody> 
</table>

按照我们修改之后的实现：

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th align="center">时间复杂度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>Q.enqueue(e)</td> 
   <td align="center">O(1)</td> 
  </tr> 
  <tr> 
   <td>Q.dequeue()</td> 
   <td align="center">O(1)</td> 
  </tr> 
  <tr> 
   <td>Q.first()</td> 
   <td align="center">O(1)</td> 
  </tr> 
  <tr> 
   <td>Q.is_empty()</td> 
   <td align="center">O(1)</td> 
  </tr> 
  <tr> 
   <td>len(Q)</td> 
   <td align="center">O(1)</td> 
  </tr> 
 </tbody> 
</table>

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU4OTU3NQ_size_16_color_FFFFFF_t_70]: /images/20230528/0199fdc16da14505948ad285667fb0e7.png
[Python _ _list_tuple_str]: https://blog.csdn.net/weixin_37589575/article/details/105470849
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU4OTU3NQ_size_16_color_FFFFFF_t_70 1]: /images/20230528/fbb0cc5cc80d45c695cb47df93c809ef.png