3、队列与链表

摘要：跟随b站陈斌老师学习数据结构与算法第三课。

队列(Queue)

队列是一种有次序的数据集合，与先前的栈类似。但是与栈的特性（只在栈顶添加与删除数据项）不同，队列中数据项的添加与删除发生在不同的两端，其中数据项的添加端称为尾端，数据项的删除端称为首端。

队列具有**先进先出(FIFO)**的特性。

队列的例子可以用排队来类比：排在前面的先服务。计算机科学中的进程调度、键盘缓冲也是队列的实例。

抽象数据类型Queue有如下操作定义：

• Queue()：创建一个空队列对象，返回值为Queue对象

• enqueue()：将数据项item添加到队尾，无返回值

• dequeue()：从队首移除数据项，返回值为移除的那个数据项，队列被修改

• isEmpty()：测试队列是否为空队列，返回布尔值

• size()：返回队列中数据项的个数

队列的python实现如下：

class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        return self.items.pop(0)
    
    def isEmpty(self):
        return self.items == []
    
    def size(self):
        return len(self.items)

可以发现，数据项添加与删除端的复杂度一定有一个是 $O(1)$ 一个是 $O(n)$。

队列应用——丢手绢问题

问题描述：有n个人坐成一圈，手绢从某个人开始，报数1~m，报到m的人淘汰，手绢给下一个人，重复上述过程，直到只剩下一个人。问开始编号多少的人能笑道最后？

这是一个典型的队列应用：可以将这n个人放在一个队列中，默认队首有手绢，手绢的传递就是将队首的人移到队尾去，如此重复m次删除队首元素，直到剩最后一个人。

python实现如下：

def solution(n, m):
    nameList = Queue()
    for i in range(n):
        nameList.enqueue(i)
    while nameList.size() > 1:
        for i in range(m):
            nameList.enqueue(nameList.dequeue())
        nameList.dequeue()
    return nameList.dequeue()

双端队列(Deque)

双端队列与队列差不多，但是集成了栈和队列的能力。数据项可以在双端队列的两端添加和移除。

双端队列定义的操作如下：

• Deque()：创建一个空的双端队列

• addFront(item)：将item加入队首

• addRear(item)：将item加入队尾

• removeFront()：移除队首的元素，有返回值

• removeRear()：移除队尾的元素，有返回值

• isEmpty()：返回队列是否为空

• size()：返回队列长度

链表

链表不是具体的一种抽象数据类型，它是介于线性数据与栈、队列等之间的一种东西，链表主要是用以实现抽象数据类型无序表与有序表的实现。

链表的每个元素是节点(Node)，节点的属性方法如下：

• Node()：创建一个节点

• self.data：数据属性

• self.next：下一个数据的指向

• getData()、getNext()、setData()、setNext()：返回、设置数据和下一个数据

顾名思义，链表就是一个一个数据链接起来的数据集合，其元素在内存中不是连续存在的。

节点的python实现如下：

class Node:
    def __init__(self, data = None):
        self.data = data
        self.next = None

    def set_data(self, data):
        self.data = data
    
    def set_next(self, next):
        self.next = next

    def get_data(self):
        return self.data
    
    def get_next(self):
        return self.next

无序表(UnorderedList)

列表是一种数据项按照相对位置存放的数据集合，其操作如下：

• List()：创建一个空列表

• add(item)：添加一个数据项到列表中

• remove(item)：返回移除的item，如果不存在，则报错

• search(item)：在列表中查找item，返回布尔值

• isEmpty()：判断列表是否为空

• size()：返回列表长度

• append(item)：添加一个数据项到表末尾

······还有其他的操作如index()、insert()、pop()等

无序表的实现用链表实现，无序表必须有一个属性head，用以指向表中第一个数据项。

其python的部分实现如下：

class UnorderedList:
    def __init__(self):
        self.head = None
    
    def add(self, item):
        temp = Node(item)
        temp.set_next(self.head)
        self.head = temp

    def size(self):
        current = self.head
        count = 0
        while current != None:
            count += 1
            current = current.get_next()
        return current
    # ······

---