大邓和他的Python

查看原文

其他

数据结构：队列与堆栈

Original 2018-01-17

作者大邓

队列与堆栈都是一种数据的存储方式。

队列可以提供先进先出的顺序（FIFO）。它每一次移除的元素，都是你最先放进去的元素。这里有一个非常类似的数据结构，堆栈Stack，属于后进先出的顺序（LIFO,Last in，Last out）。

一、队列

1.1 队列的主要方法

enqueue入队，在最顶层加入数据。
dequeue出队，将最旧的数据从队列中移除

1.2 队列使用场景

队列的最主要用途是异步任务，异步的思路主要用来缓解瞬间压力。

若系统每秒处理能力是100请求，而最高峰值可能达到每秒1000请求，若不采用队列，很有可能会出现服务不可用或者长时间等待。此时可以用队列将未能成功执行的请求放入队列，顺序执行，直到所有请求都被处理。

之前有一篇 gevent：异步理论与实战文中gevent异步有一段代码，其实应用的就是队列数据结构的特性。

gevent.join([gevent.spawn(请求函数名,url) for url in urls ])

1.3 队列代码实现

class Queue(object) :
    """
    队列数据结构
    """
    def __init__(self, size=10):
        """
        初始化队列，建立容器，并设定队列的容量
        """
        self.size = size
        self.queue = []


    def getsize(self):
        """
        获取队列的当前长度
        """
        return len(self.quene)


    def enqueue(self, items):
        """
        入队，如果队列满了返回-1，否则将元素插入队列尾
        """
        if self.size==len(self.queue):
            return -1
        else:
            self.queue.append(items)

    def dequeue(self):
        """
        出队，如果队列空了返回-1，否则返回队列头元素并将其从队列中移除
        """
        if self.is_empty():
            return -1
        else:
            # [1,2,3,4].pop(0)会移除1
            return self.queue.pop(0)


    def is_empty(self):
        """
        判断队列是否为空队列。空，返回True；非空，返回False
        """
        return self.size == 0

二、堆栈

stack的第一种含义是一组数据的存放方式，特点为LIFO，即后进先出（Last in, first out）。

2.1 stack的主要方法：

push：在最顶层加入数据。
pop：返回并移除最顶层的数据。

2.2 什么时候用到栈

需要保存之前的状态
状态涉及先后顺序

这里引用知乎周毅刚举的例子，

首先你打开app，是一个问题列表，之后你点击一个问题，进入了相应的界面，之后你点击评论，进入了评论页面。

好了，现在你想返回主界面怎么办呢？按两下返回键吧，第一次回到问题详情，第二次回到主界面。这时候你就发现了，这些界面的储存结构可以说是一个栈结构，你想回到主界面（位于栈底），必须经历两次弹栈把前面两个界面移除。

2.3 堆栈代码实现

代码很简单，客官一看就懂！

class Stack(object):
    """
    栈数据结构
    """
    def __init__(self, size=10):
        """
        初始化栈，建立容器，并设定栈的容量
        """
        self.stack = []
        self.size = size    

    def push(self, data):
        """
        入栈，如果栈溢出（超过栈的容量），返回-1
        """
        if len(self.stack) >= self.size:
            return -1       
        else:
            self.stack.append(data)


    def pop(self):
        """
        出栈(弹出栈中最新加入的元素)，如果栈是空的，返回-1；
        """
        if len(self.stack) <= 0:
            return -1       
        else:
            #[1,2,3,4].pop(-1)会移除4
            return self.stack.pop(-1)

    def top(self):
        """
        返回栈内最新加入的元素，但并不移除该元素
        """
        return self.stack[-1]

    def is_empty(self):
        """
        判断栈是否为空，为空返回True；非空，返回False
        """
        return self.size == 0
    
    def getSize(self):
        """
        获取栈的容量，长度
        """
        return len(self.stack)