CS 基础：队列

队列

队列：只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是先进先出（First In First Out）的线性表。允许插入的一端称为队尾，允许删除的一端成为队头。

实现队列

基于双向链表的基础上来实现这个队列结构。

实现一个队列结构体

首先建立一个 List 链表类，在队列中使用链表来储存元素：

public struct Queue<T>{
    fileprivate var list = List<T>()
}

入队

给队列添加一个入队函数：

public mutating func enqueue(element:T) {
        list.append(element:element)
    }

出队

给队列添加一个出队函数：

public mutating func dequeue() -> T? {
        guard !list.isEmpty,let element = list.first else {
            return nil
        }
        list.remove(node:element)
        return element.value
    }

查看队首元素

public func peek() -> T? {
        return list.first?.value
    }
    
//是否为空队列
    public var isEmpty : Bool?{
        return list.isEmpty
    }
    

实践

添加一个 extension 帮助打印输出：

extension Queue{
    public var description : String{
        return list.description
    }
}

输入：

var queue = Queue<String>()
queue.enqueue(element:"熊大")
queue.enqueue(element:"熊二")
queue.enqueue(element:"周末")
queue.enqueue(element:"蛋蛋")

print(queue.description)

queue.dequeue()
print(queue.description)

输出:

[熊大 , 熊二 , 周末 , 蛋蛋]
[熊二 , 周末 , 蛋蛋]

end