第3讲 | 数据结构与算法 | 【栈、队列】

- 《数据结构与算法》专栏完整版在公众号【书伟认视界】中查看，转载需联系微信【econe0219】

---

栈

栈的特点是，先进后出，后进先出。只允许在一端插入和删除数据。（想象往一个桶里放东西的过程）

如浏览器页面的前进后退、函数调用都是用栈来实现的。

注：我们常说的数据结构里“堆栈”其实就是“栈”，和“堆”是完全不同的概念。

'''用 python 的列表来实现一个栈'''
class Stack(object):
    # 空列表作为初始化的栈
    def __init__(self):
        self.items = []
    # 判断栈是否为空，返回布尔值
    def is_empty(self):
        return self.items == []
    # 返回栈顶元素
    def peek(self):
        return self.items[len(self.items)-1]
    # 返回栈的大小
    def size(self):
        return len(self.items)
    # 入栈
    def push(self,item):
        self.items.append(item)
    # 出栈
    def pop(self):
        return self.items.pop()   # pop()默认输出最后一个元素

队列

队列的特点是“先进先出”。类似排队一样，队列有两个操作：入队enqueue()，放一个数据到队列尾部；出队dequeue()，从队列头部取一个元素。

普通队列

"""用python列表实现一个普通队列"""
class Queue(object):
    # 用列表初始化空队列
    def __init__(self,size):
        self.size = size
        self.queue = []   
    # 判断空队列
    def is_empty(self):
        if len(self.queue) == 0:
            return True
        return False
    # 判断满队列
    def is_full(self):
        if len(self.queue) == self.size:
            return True
        return False
    # 入队 enqueue
    def enqueue(self,item):
        if self.is_full():
            return -1
        self.queue.appand(item)
    # 出队dequeue
    def dequeue(self,item):
        if self.is_empty():
            return -1
        first_element = self.queue[0]
        self.queue.remove(first_element)
        return first_element

双端队列

双端队列的队头和队尾均可以实现入队和出队操作。

'''用python列表实现一个双端队列'''
class Deque(object):
    # 用列表初始化队列
    def __init__(self):
        self.deque = []
    # 判断队列是否为空
    def is_empty(self):
        return self.deque == []
    # 返回队列大小
    def size(self):
        return len(self.deque)
    
    # 从队头插入数据
    def push_head(self,item):
        self.deque.insert(0,item)
    # 从队尾插入数据
    def push_tail(self,item):
        self.deque.append(item)
        
    # 从队头删除数据
    def pop_head(self):
        return self.deque.pop(0)
    # 从队尾删除数据
    def pop_tail(self):
        return self.deque.pop()

双端队列又分为，输出受限队列和输入受限队列。输入受限队列指的是，在队列的一端可以实现插入和删除操作，在另一端只能实现删除操作；输出受限队列指的是，在队列的一端可以实现插入和删除操作，在另一个段只能实现插入操作。如果限定队列中从某个端点插入的的数据只能从该端点删除，那这个队列相当于两个栈底相邻的栈了。

优先队列

优先队列并不是像普通队列一样，按顺序出队或入队。如下图所示，如果是普通队列，那么数据5要比数据6出队早。但是在优先队列中，数据6比数据5大，则优先出队。

基于以上原则，优先队列的实现需要用到“堆”这种数据结构。或者说，优先队列就是堆，名称不同而已。所以相关内容后面看关于堆的讲解就好。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4cunapUz-1597899502652)(C:\Users\Thinkpad\AppData\Roaming\Typora\typora-user-images\image-20200408152401946.png)]

循环队列

简单来讲就是队列的头和尾连起来，就构成循环队列。

(图片来源于网络，侵删)

把循环队列画成一个圈更好理解。画图推导发现，当队满时，(tail+1)%n=head。其中，tail是尾指针，指向队尾；head是头指针，指向队头（图中的front）；n是队列长度（以下代码中用maxsize表示）。

"""用python实现循环队列"""
class CircularQueue(object):
    def __init__(self,maxsize):
        self.queue = [None] * maxsize  # 给定长度
        self.maxsize = maxsize
        self.head = 0
        self.tail = 0
    # 入队dequeue，队列未满时在队尾插入元素，时间复杂度时O(1)
    def enqueue(self,item):
        if (self.tail + 1) % self.maxsize == self.head:
            return -1
        else:
            self.queue[self.tail] = item
            self.tail = (self.tail + 1) % self.maxsize
    # 出队dequeue，队列不为空时删除队头元素，时间复杂度O(1)
    def dequeue(self):
        if self.tail == self.head:
            return -1
        else:
            item = self.queue[self.head]
            self.queue[self.head] = None
            self.head = (self.head + 1) % self.maxsize
            return item
    

阻塞队列和并发队列

阻塞队列就是在队列基础上增加了阻塞操作。队列为空时，从对头取数据会被阻塞，直到队列中有数据才能返回；如果队列满了，插入的数据会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。

并发队列是指，线程安全的队列。（多线程情况下，会有多个线程同时操作队列，这时候就会存在线程安全问题）

---

---

---

《数据结构与算法》专栏完整版在公众号【书伟认视界】中查看，转载需联系微信【econe0219】

.