栈（Stack）
栈（stack）是限制对元素的插入（push）和删除（pop）只能在一个位置上进行的表，该位置是表的末端，叫做栈的栈顶（top)。
进栈和出栈
基于栈结构的特点，在实际应用中，通常只会对栈执行以下两种操作：
- 向栈中添加元素，此过程被称为
"进栈"（入栈或压栈）；- 从栈中提取出指定元素，此过程被称为
"出栈"（或弹栈）；
栈的实现
栈是一种 "特殊" 的线性存储结构，因此栈的具体实现有以下两种方式：
1. 数组实现
public struct Stack<T> {
fileprivate var array = [T]()
public var isEmpty: Bool {
return array.isEmpty
}
public var count: Int {
return array.count
}
public mutating func push(_ element: T) {
array.append(element)
}
public mutating func pop() -> T? {
return array.popLast()
}
public var top: T? {
return array.last
}
}
注意到，压栈操作是将新元素压入数组的尾部，而不是头部。在数组的头部插入元素是一个很耗时的操作，它的时间复杂度为 O(n)，因为需要将现有元素往后移位为新元素腾出空间。而在尾部插入元素的时间复杂度为 O(1)；无论数组有多少元素，这个操作所消耗的时间都是一个常量。
2. 链表实现
这里我们使用单链表来实现，定义一个first指针指向栈顶，栈的链表实现实际上是简化了单链表实现，具体实现看以下代码。
/// 链表节点类
public class ListNode<T> {
var value: T // 值
var next: ListNode<T>? = nil // 下一个节点
weak var previous: ListNode<T>? = nil
init(value: T) {
self.value = value
}
}
public class StackList<T> {
public var count: Int = 0
public var first: ListNode<T>?
public var isEmpty: Bool {
return count == 0
}
public func push(_ element: T) {
let oldNode = first
first = ListNode(value: element)
first?.next = oldNode
count += 1
}
public func pop() -> T? {
let value = first?.value
first = first?.next
count -= 1
return value
}
}
队列（queue）
wiki: 队列，又称为伫列（queue），是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。
多种队列
队列一般分为普通的数组队列，链表队列和循环队列。
链表队列：长度一般是无限的，一般不存在溢出的可能性，用完就销毁，不会浪费内存空间。
普通的数组队列：长度一般是有限的，即数组长度。由于元素出队后其位置的内存空间并不会释放，因此会浪费大量的内存空间。
image.png
循环队列：特殊的数组队列，由于普通的数组的队列会浪费大量的内存空间，因此出现了循环队列。当循环队列的队尾指针到达数组末尾后，会重新回到数组起始位置，实现了对内存的重复利用。
image.png
队列的实现
1. 数组队列
public struct Queue<T> {
fileprivate var array = [T]()
public var isEmpty: Bool {
return array.isEmpty
}
public var count: Int {
return array.count
}
public mutating func enqueue(_ element: T) {
array.append(element)
}
public mutating func dequeue() -> T? {
if isEmpty {
return nil
} else {
return array.removeFirst()
}
}
public var front: T? {
return array.first
}
}
2. 链表队列
/// 链表节点类
public class ListNode<T> {
var value: T? // 值
var next: ListNode<T>? = nil // 下一个节点
weak var previous: ListNode<T>? = nil
init(value: T?) {
self.value = value
}
}
public class QueueByLinkList<T> {
public var count: Int = 0
public var first: ListNode<T>?
public var last: ListNode<T>?
public var isEmpty: Bool {
return count == 0
}
//初始化队列
init() {
first = ListNode(value: nil)
last = first
count = 0
}
//入队
public func enqueue(_ element: T) {
if isEmpty {
last?.value = element
count += 1
return
}
let oldNode = last
last = ListNode(value: element)
oldNode?.next = last
count += 1
}
//出队
public func dequeue(_ element: T) -> T? {
if isEmpty {
print("***队列为空***")
return nil
}
let value = first?.value
first = first?.next
count -= 1
return value
}
}
3. 循环队列
public struct CycleQueue<T> {
fileprivate var queue = [T]()
fileprivate var queue_Capacity: Int = 0
var count: Int {
return queue.count
}
// 构造函数创建出一个队列数据模型来
init(queue_Capacity: Int) {
self.queue_Capacity = queue_Capacity
self.clearQueue()
}
/// 清空队列
public mutating func clearQueue() {
queue.removeAll()
}
/// 判断队列是否已经满了
public func queueFull() -> Bool {
return queue_Capacity == count
}
var isEmpty: Bool {
return queue.isEmpty
}
/// 往队列中添加一个元素
public mutating func enQueue(_ element : T) -> Bool {
if queueFull() {
print("队列已满")
return false
} else {
queue.append(element)
return true
}
}
/// 从队列中取出来一个元素 如果队列为空 那么 取出来的为 nil
public mutating func deQueue() -> T? {
if isEmpty {
return nil
} else {
let element = queue.removeFirst()
return element
}
}
/// 遍历队列
public func queueTraverse() {
if isEmpty {
print("队列为空")
} else {
queue.forEach { (element) in
print("element: \(element)")
}
}
}
}
参考文章
浅谈栈和队列
