数据结构与算法- 队列（Queue）-一一网

这是我参与更文挑战的第13天，活动详情查看：更文挑战

如何理解“队列”？

队列（Queue）最大的特点就是先进先出，主要的两个操作是入队和出队。跟栈一样，它既可以用数组来实现，也可以用链表来实现。用数组实现的叫顺序队列，用链表实现的叫链式队列。

在许多算法中，我们希望在某个时间点将项目添加到临时列表中，然后在以后再次将它们从列表中拉出。添加和删除这些项目的顺序非常重要。

举一个栗子

可以把它想象成排队买票，先来的先买，后来的人只能站末尾，不允许插队。先进者先出，这就是典型的“***队列***”。

栈只支持两个基本操作：入栈push()**和**出栈pop()。队列跟栈非常相似，支持的操作也很有限，最基本的操作也是两个：入队enqueue()，放一个数据到队列尾部；出队dequeue()，从队列头部取一个元素。

用swift 数组实现队列

对于iOS队列来说，我们需要了解以下几点：

队列是先进先出的结构
iOS开发中多线程的GCD和NSOperationQueue就是基于队列实现的。
关于队列关注这几个操作：enqueue, dequeue, isEmpty, peek, size。


public struct Queue<T> {
  
    fileprivate var list = LinkedList<T>()
    
  	// 入队
    public mutating func enqueue(_ element: T) {
        list.append(element)
    }
  
  	// 出队
    public mutating func dequeque() -> T? {

        guard !list.isEmpty, let element = list.first else { return nil}
        
        list.remove(element)
        
        return element.value
    }
  
  	//查看
    public func peek() -> T? {
        return list.first?.value
    }
    
    public var isEmpty: Bool {
        return list.isEmpty
    }
}
复制代码

我们在复习下昨天的Stack

struct Stack<Element> {
    fileprivate var array:[Element] = []
    // 进栈
    mutating func push(_ element:Element) {
        array.append(element)
    }
    // 出栈
    mutating func pop()-> Element? {
        return array.popLast()
    }
    // 查看
    func peek()-> Element? {
        return array.last
    }
}
复制代码