Swift 数据结构 - 栈和队列

栈（Stack）

栈（stack）是限制对元素的插入（push）和删除（pop）只能在一个位置上进行的表，该位置是表的末端，叫做栈的栈顶（top)。

进栈和出栈

基于栈结构的特点，在实际应用中，通常只会对栈执行以下两种操作：

• 向栈中添加元素，此过程被称为"进栈"（入栈或压栈）；
• 从栈中提取出指定元素，此过程被称为"出栈"（或弹栈）；

栈的实现

栈是一种 "特殊" 的线性存储结构，因此栈的具体实现有以下两种方式：

1. 顺序栈：采用顺序存储结构可以模拟栈存储数据的特点，从而实现栈存储结构；
2. 链栈：采用链式存储结构实现栈结构；

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)")
            }
        }
    }
}

参考文章
浅谈栈和队列