队列特点
- 先进先出
- 从队尾入队列
- 从队头出队列
- 队列的相关操作集中在队头与队尾
队列的接口抽象
队列与栈一样有这以下几个基本的功能接口，如下：
protocol QueueProtocol: CustomStringConvertible {
associatedtype E
//入队
mutating func enQueue(element: E)
//出队
mutating func deQueue() -> E?
//是否是空队列
mutating func isEmpty() -> Bool
//队列的长度
mutating func size() -> Int?
//队列的头
mutating func front() -> E?
//清空队列
mutating func clear()
}
队列的种类
队列可以通过线性表来实现，基于基本队列概念，可以将队列细分为以下几种：
单端队列
单端队列从统一的一个方向进行队列的元素的基本操作，队列的元素添加是按照统一的方向进行的。可以通过双向链表进行实现，双向链表的头指针与尾指针刚刚好配合队列的出队与入队操作。所以通过双向链表来实现其操作再合适不过了。双端队列
基于单端队列的扩充，不仅仅能够从一端进行相关队列元素的基础操作，同样也能够从另一端进行相关的队列功能的操作，可以通过双向链表进行实现，道理同单端队列一样。
双端队列是能够在头尾两端添加、删除的队列。循环队列
队列的元素操作方向是循环的，保证其数据连续的同时能够同时充分的利用存储空间，可基于数组来实现。涉及到动态扩容以及动态下标查找的算法方案。
队列的几种实现形式
- 单端队列
实现的基本思路：
- 依据队列的基本抽象接口，将其设计为协议
- 双向链表作为成员变量进行队列的封装并继承队列的基本抽象接口
- 通过双向链表的头指针来进行出队操作
- 通过双向链表的尾指针用来进行入队操作
- 通过链表的长度来间接反应队列的长度
- 通过链表的头结点来找到队列的头
/*
队列：
1. FIFO 先进先出
2. 从尾进入，队头出来
3.
*/
protocol QueueProtocol: CustomStringConvertible {
associatedtype E
mutating func enQueue(element: E)
mutating func deQueue() -> E?
mutating func isEmpty() -> Bool
mutating func size() -> Int?
mutating func front() -> E?
mutating func clear()
}
struct SignalQueue<T: Equatable>: QueueProtocol, CustomStringConvertible {
typealias E = T
var list = DoubleList<T>()
var description: String {
return self.list.description
}
mutating func enQueue(element: T) {
self.list.addFromLast(element: element)
}
mutating func deQueue() -> T? {
let outNode = self.list.nodeOfIndex(index: 0) as? T
self.list.remove(index: 0)
return outNode
}
mutating func isEmpty() -> Bool {
self.list.isEmpty()
}
mutating func size() -> Int? {
self.list.size
}
mutating func front() -> T? {
self.list.nodeOfIndex(index: 0) as? T
}
mutating func clear() {
self.list.clear()
}
}
- 双端队列
基于单端队列进行实现，在单端队列的基础上添加头尾相关的功能。
- 入队分为头尾两种
- 出队也分为头尾两种
- 队头与队尾元素的获取
/*
双端队列
这里不要使用数组实现，因为数组的删除操作会有移位行为，影响性能，最好的采用双向链表去操作
*/
struct Deque<E: Equatable>: CustomStringConvertible {
var list: DoubleList = DoubleList<E>()
var description: String {
var des = "length:\(list.size),front:\(String(describing: list.first?.element)),last:\(String(describing: list.last?.element)), ["
var firstNode = list.first
while firstNode != nil {
des.append("\(String(describing: firstNode?.element)), ")
firstNode = firstNode?.next
}
des.removeLast(2)
des.append("]")
return des
}
//从队尾入队
mutating func enQueueRear(element: E) {
list.addFromLast(element: element)
}
//从队头出队
mutating func deQueueFront() -> E? {
let firstQueueNode = list.first
list.remove(index: 0)
return firstQueueNode?.element
}
//从队头入队
mutating func enQueueFront(element: E) {
list.add(element: element)
}
//从队尾出队
mutating func deQueueRear() -> E? {
let lastNode = list.last
list.remove(index: list.size - 1)
return lastNode?.element
}
//是否为空
mutating func isEmpty() -> Bool {
false
}
//队列长度
mutating func size() -> Int? {
list.size
}
//获取队头
mutating func front() -> E? {
list.first?.element
}
//获取队尾
mutating func rear() -> E? {
list.last?.element
}
//清空队列
mutating func clear() {
list.clear()
}
}
- 循环队列
可基于数组实现，对数组进行相关的添加删除操作，需要注意几点：
- 元素在数组中的
逻辑下标与真实下标转换的操作 - 数组的动态扩容操作
- 动态扩容期间，原始数组的元素复制移动操作
- 队列头的更新
let DEFAULTSIZE = 5
let QUEUENULL = 0
/*
循环队列
*/
struct CycleQueue<E: Equatable> : CustomStringConvertible, QueueProtocol{
var description: String {
var desStr = "Queue length:\(length), front:\(list[frontIndex]), ["
for idx in 0..<length {
let realIdx = realIndexInArray(index: idx)
desStr.append("\(list[realIdx]), ")
}
desStr.removeLast(2)
desStr.append("], 原始存储介质list:\(list)")
return desStr
}
var defaultTypeValue: E
var list: Array<E>
var length = 0
var frontIndex: Int = QUEUENULL
init(defaultTypeValue: E) {
self.defaultTypeValue = defaultTypeValue
self.list = [E](repeating: defaultTypeValue, count: DEFAULTSIZE)
}
//找到逻辑下标在数组中的真是下标
func realIndexInArray(index: Int) -> Int {
var realIndex = 0
if (frontIndex + index) >= list.count {
realIndex = frontIndex + index - list.count
}else {
realIndex = frontIndex + index
}
return realIndex
}
//自动扩展空间内存
mutating func autoExpandCapacity() {
if (length + 1) > list.count {
//按照旧的容量的两倍进行扩展
var newList = [E](repeating: defaultTypeValue, count: list.count * 2)
//将旧容量的数据放入到新的内存数组中
for idx in 0..<length {
newList[idx] = list[realIndexInArray(index: idx)]
}
print(newList)
self.list = newList
frontIndex = 0
print("*重新扩容* capacity:\(self.list.count), frontIndex:\(frontIndex), list:\(self.list)")
}
}
mutating func enQueue(element: E) {
autoExpandCapacity()
let rearIndex = realIndexInArray(index:length)
list[rearIndex] = element
length += 1
}
mutating func deQueue() -> E? {
let elementOfIndex = list[frontIndex]
list[frontIndex] = defaultTypeValue
frontIndex = (frontIndex + 2) > list.count ? (frontIndex + 1 - list.count) : (frontIndex + 1)
length -= 1
print("移出\(elementOfIndex) at Index:\(frontIndex), queue:\(list)")
return elementOfIndex
}
mutating func isEmpty() -> Bool {
length == 0
}
mutating func size() -> Int? {
length
}
mutating func front() -> E? {
list[frontIndex]
}
mutating func clear() {
list.removeAll()
length = 0
}
}
扩展
- 如何通过栈来实现队列
栈有着先进后出的特点，队列恰恰相反。依赖于此特点，可以对栈进行两次出栈操作，就间接的完成队列的排列顺序了。实现关键点如下：
- 定义两个分别用于入队操作的栈
inStack与出队操作outStack的栈 -
outStack栈中元素的来源是inStack的入栈 - 在
outStack栈不为空的时候，不进行两个栈的元素移动操作，主要是为了保持其队列的元素顺序不被打乱。 - 在
outStack栈为空的时候，对inStack中的所有元素进行出栈操作，将其出栈的元素放入到outStack中
以上的 3、4 步骤其主要目的就是为了避免来回的出队入队操作导致的元素顺序被打乱的可能。
/*
使用栈来实现队列
*/
struct QueueUseStack<E: Equatable> : QueueProtocol {
var inStack: Stack<E>?
var outStack: Stack<E>?
var description: String{
//拷贝一份
var copySelf = self
var infoStr = "length:\(String(describing: copySelf.size())),front:\(String(describing: copySelf.outStack?.top())),["
while !copySelf.outStack!.isEmpty() {
infoStr.append("\(String(describing: copySelf.outStack?.pop())),")
}
while !copySelf.inStack!.isEmpty() {
copySelf.outStack?.push(element: copySelf.inStack!.pop()!)
}
while !copySelf.outStack!.isEmpty() {
infoStr.append("\(String(describing: copySelf.outStack?.pop())),")
}
infoStr.removeLast()
infoStr.append("]")
return infoStr
}
init(defaultTypeValue: E) {
self.inStack = Stack<E>(arrayDefault: defaultTypeValue)
self.outStack = Stack<E>(arrayDefault: defaultTypeValue)
}
mutating func enQueue(element: E) {
self.inStack?.push(element: element)
}
mutating func deQueue() -> E? {
if outStack!.isEmpty() {
while !inStack!.isEmpty() {
outStack!.push(element: inStack!.pop()!)
}
}
return outStack?.pop()
}
mutating func isEmpty() -> Bool {
(inStack!.size() + outStack!.size()) == 0
}
mutating func size() -> Int? {
inStack!.size() + outStack!.size()
}
mutating func front() -> E? {
outStack!.top()
}
mutating func clear() {
inStack!.clear()
outStack!.clear()
}
}
