栈和队列

柔光的暖阳◎ 2023-07-02 03:24 1阅读 0赞

## 物理结构与逻辑结构 ##

把物质层面的人体比作数据存储的物理结构，那么精神层面的人格则是数据存储的逻辑结构。逻辑结构是抽象的概念，它依赖于物理结构而存在。  
![在这里插入图片描述][20200126132128947.png]  
下面我们来讲解两个常用数据结构：栈和队列。这两者都属于逻辑结构，它们的物理实现既可以利用数组，也可以利用链表来完成。

## 栈 ##

假如有一个又细又长的圆筒，圆筒一端封闭，另一端开口。往圆筒里放入乒乓球，先放入的靠近圆筒底部，后放入的靠近圆筒入口。  
![在这里插入图片描述][20200126144400397.png]  
那么，要想取出这些乒乓球，则只能按照和放入顺序相反的顺序来取，先取出后放入的，再取出先放入的，而不可能把最里面最先放入的乒乓球优先取出。  
![在这里插入图片描述][20200126144557249.png]  
栈（stack）是一种线性数据结构，它就像一个上图所示的放入乒乓球的圆筒容器，栈中的元素只能先入后出（First In Last Out，简称FILO）。最早进入的元素存放的位置叫作栈底（bottom），最后进入的元素存放的位置叫作栈顶（top）。

栈这种数据结构既可以用数组来实现，也可以用链表来实现。

栈的数组实现如下。  
![在这里插入图片描述][20200126144730496.png]  
栈的链表实现如下。  
![在这里插入图片描述][20200126144830507.png]  
栈的基本操作：

class Stack(object):
        """用数组实现栈"""
        def __init__(self):
            self.__list =[]
    
        def push(self,item):
            """添加一个新元素item到栈顶"""
            self.__list.append(item)
    
    
        def pop(self):
            """弹出栈顶元素"""
            return self.__list.pop()
    
        def peek(self):
            """返回栈顶元素"""
            if self.__list:
                return self.__list[-1]
            else:
                return None
    
        def is_empty(self):
            """判断栈是否为空"""
            return self.__list is None
    
        def size(self):
            """返回栈的元素个数"""
            return len(self.__list)

## 队列 ##

假如公路上有一条单行隧道，所有通过隧道的车辆只允许从隧道入口驶入，从  
隧道出口驶出，不允许逆行。  
![在这里插入图片描述][20200126145247205.png]  
因此，要想让车辆驶出隧道，只能按照它们驶入隧道的顺序，先驶入的车辆先驶出，后驶入的车辆后驶出，任何车辆都无法跳过它前面的车辆提前驶出。  
![在这里插入图片描述][20200126145341992.png]  
队列（queue）是一种线性数据结构，它的特征和行驶车辆的单行隧道很相似。不同于栈的先入后出，队列中的元素只能先入先出（First In First Out，简称FIFO）。队列的出口端叫作队头（front），队列的入口端叫作队尾（rear）。

与栈类似，队列这种数据结构既可以用数组来实现，也可以用链表来实现。

队列的数组实现如下。  
![在这里插入图片描述][20200126145544132.png]  
队列的链表实现如下。  
![在这里插入图片描述][20200126145611830.png]  
队列的基本操作：

class Queue(object):
        """用顺序表实现队列"""
        def __init__(self):
            self.__list = []
    
        def enqueue(self,item):
            self.__list.append(item)    # 入队频繁
           # self.__list.insert(0,item) # 出队少
    
        def del_queue(self):
            return self.__list.pop(0) # 入队频繁
           # return self.__list.pop() # 出队少
    
        def is_empty(self):
            return self.__list is None
    
        def size(self):
            return len(self.__list)

## 双端队列 ##

双端队列（deque，全名double-ended queue），是一种具有队列和栈的性质的数据结构。

双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。  
![在这里插入图片描述][20200126150527791.png]

双端队列的基本操作：

class Queue(object):
        """用顺序表实现双端队列"""
        def __init__(self):
            self.__list = []
    
        def add_front(self,item):
            self.__list.append(item)  
    
        def add_rear(self,item):
            self.__list.append(item)  
    
        def pop_front(self):
            return self.__list.pop(0)
    
        def pop_rear(self):
            return self.__list.pop(0)
    
        def is_empty(self):
            return self.__list is None
    
        def size(self):
            return len(self.__list)

## 优先队列 ##

还有一种队列，它遵循的不是先入先出，而是谁的优先级最高，谁先出队。  
![在这里插入图片描述][20200126153007531.png]  
优先队列已经不属于线性数据结构的范畴了，它是基于二叉堆来实现的。关于优先队列的原理和使用情况，我们会在其它文章中进行详细介绍。

## 栈和队列的应用 ##

**栈**

栈的输出顺序和输入顺序相反，所以栈通常用于对“历史”的回溯，也就是逆流而上追溯“历史”。

例如实现递归的逻辑，就可以用栈来代替，因为栈可以回溯方法的调用链。  
![在这里插入图片描述][20200126152533147.png]

栈还有一个著名的应用场景是面包屑导航，使用户在浏览页面时可以轻松地回溯到上一级或更上一级页面。  
![在这里插入图片描述][20200126151546754.png]  
使用栈虽然很方便，但是也要付出代价：存储详尽的信息可能占用大量的内存。每个函数调用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。在这种情况下，你有两种选择。

*  重新编写代码，转而使用循环。
 *  使用尾递归 。这是一个高级递归主题，不在本节的讨论范围内。另外，并非所有的语言都支持尾递归。

**队列**  
队列的输出顺序和输入顺序相同，所以队列通常用于对“历史”的回放，也就是按照“历史”顺序，把“历史”重演一遍。

例如在多线程中，争夺公平锁的等待队列，就是按照访问顺序来决定线程在队列中的次序的。

再如网络爬虫实现网站抓取时，也是把待抓取的网站URL存入队列中，再按照存入队列的顺序来依次抓取和解析的。  
![在这里插入图片描述][20200126152853507.png]

[20200126132128947.png]: https://img-blog.csdnimg.cn/20200126132128947.png
[20200126144400397.png]: https://img-blog.csdnimg.cn/20200126144400397.png
[20200126144557249.png]: https://img-blog.csdnimg.cn/20200126144557249.png
[20200126144730496.png]: https://img-blog.csdnimg.cn/20200126144730496.png
[20200126144830507.png]: https://img-blog.csdnimg.cn/20200126144830507.png
[20200126145247205.png]: https://img-blog.csdnimg.cn/20200126145247205.png
[20200126145341992.png]: https://img-blog.csdnimg.cn/20200126145341992.png
[20200126145544132.png]: https://img-blog.csdnimg.cn/20200126145544132.png
[20200126145611830.png]: https://img-blog.csdnimg.cn/20200126145611830.png
[20200126150527791.png]: https://img-blog.csdnimg.cn/20200126150527791.png
[20200126153007531.png]: https://img-blog.csdnimg.cn/20200126153007531.png
[20200126152533147.png]: https://img-blog.csdnimg.cn/20200126152533147.png
[20200126151546754.png]: https://img-blog.csdnimg.cn/20200126151546754.png
[20200126152853507.png]: https://img-blog.csdnimg.cn/20200126152853507.png