-
特性
可以像普通队列一样，拥有从队首出队、从队尾入队的特性外，双向队列，也可以从队首入队，从队尾出队。
-
Swift实现（一般）
struct Deque<T> {
private var array = [T]()
//判空
var isEmpty: Bool {
return array.isEmpty
}
var count: Int {
return array.count
}
//从队尾入队
mutating func enqueue(_ element: T) {
array.append(element)
}
//从队首入队
mutating func enqueueFront(_ element: T) {
array.insert(element, at: 0)
}
//从队首出队
mutating func dequeue() -> T? {
if isEmpty {
return nil
} else {
return array.removeFirst()
}
}
//从队尾出队
mutating func dequeueBack() -> T? {
if isEmpty {
return nil
} else {
return array.removeLast()
}
}
//查看队首元素
func peekFront() -> T? {
return array.first
}
//查看队尾元素
func peekBack() -> T? {
return array.last
}
}
上面就是对双向队列的简单实现，但是存在如下问题：
- 1 ，dequeue(队首出队)操作时，由于删除数组中第一个元素，需要将数组中剩余的所有元素，在内存中的位置，统一向前移动一个位置，来填补空白，这个操作的时间复杂度为O(n).
- 2 ，enqueueFront(队首入队)操作时，由于是在数组的最前面插入一个新的元素，所以需要将数组中原有的所有元素，在内存中的位置，统一向后移动一个位置，这个操作的时间复杂度为O(n).
上面两种情况，导致上面的双向队列实现的方法，效率有点低，我们需要优化这个问题。
同时我们会疑问，为什么在数组的尾部进行插入和删除操作时，不错在上面的问题呢，这就和Swift中数组的实现机制有关了，在Swift中，在数组初始化后，在数组的最后面面，会预留出一些空的位置，来以备将来在末尾增加新的元素。
//初始化数组
var arr = ["a", "b", "c"]
//实际在数组中情况为
["a", "b", "c", **, **, **]
//** 就是预留出来的内存，以备将来插入新的元素
arr.append("d")后
// 实际情况为
["a", "b", "c", "d", **, **]
借鉴上面的思路，我们也可以在双向队列的实现中，自己实现这种类似的机制，来解决问题1，2.
-
Swift实现（稍高效）
struct Deque<T> {
private var array: [T?]
///在数组前面预留的空间
private var spaceCount = 10
//标记数组中的头部位置
private var head = 0
init(_ spaceCount: Int = 10) {
self.spaceCount = spaceCount
array = [T?].init(repeating: nil, count: spaceCount)
head = spaceCount
}
//判空
var isEmpty: Bool {
return count == 0
}
var count: Int {
return array.count - head
}
//从队尾入队
mutating func enqueue(_ element: T) {
array.append(element)
}
//从队首入队
mutating func enqueueFront(_ element: T) {
//需要向队首插入新的空位
if head == 0{
spaceCount *= 2
let space = [T?].init(repeating: nil, count: spaceCount)
array.insert(contentsOf: space, at: 0)
head = spaceCount
}
head -= 1
array.insert(element, at: head)
}
//从队首出队
mutating func dequeue() -> T? {
//取出队首元素
guard !isEmpty, let element = array[head] else { return nil }
array[head] = nil
//标记数组头部增加1
head += 1
//定期去除多余的空间
if head >= spaceCount*2 {
let amountToRemove = spaceCount + spaceCount/2
array.removeFirst(amountToRemove)
head -= amountToRemove
spaceCount /= 2
}
return element
}
//从队尾出队
mutating func dequeueBack() -> T? {
if isEmpty {
return nil
} else {
return array.removeLast()
}
}
//查看队首元素
func peekFront() -> T? {
return array.first ?? nil
}
//查看队尾元素
func peekBack() -> T? {
return array.last ?? nil
}
}
新的实现方法，主要有以下的几处改变：
- 1， 数组中的元素由 T 变成了 T?, 这是为了在数组的前面预留空位时，将空位中的元素设置为nil
- 2，初始化时，在数组的前面预留出一定的空间，来实现我们队首插入操作时，不需要数组中的元素整体后移的思路
- 3，enqueueFront() 队首入队时，用head标签，来标记当前实际的头部位置，同时当数组前面没有空位的时候，统一的在数组的前面增加空位，增量成倍数增长，这样当插入操作多是，效率更高
- 4，dequeue() 队首出队的时候，只需要向后移动head标签的位置即可，这样防止每次数组中队首删除元素后，元素统一向前移动，但是防止数组中前面的空位过多浪费空间，我们定期的删除空位。
