一、栈
//
// Stack.swift
// DataStructure
//
// Created by dzq_mac on 2020/8/26.
// Copyright © 2020 dzq_mac. All rights reserved.
//
import Foundation
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)
}
@discardableResult
public mutating func pop() ->T?{
return array.popLast()
}
public var top:T?{
return array.last
}
}
extension Stack:Sequence{
func makeIterator() -> AnyIterator<T> {
var cul = self
return AnyIterator{
cul.pop()
}
}
}
二、队列
//
// Queue.swift
// DataStructure
//
// Created by dzq_mac on 2020/8/26.
// Copyright © 2020 dzq_mac. All rights reserved.
//
import Foundation
/*
//简单的队列
struct Queue<T> {
fileprivate var array:[T] = []
public var count:Int{
return array.count
}
public var isEmpty:Bool{
return array.isEmpty
}
public mutating func enqueue(_ element:T){
array.append(element)
}
public mutating func dequeue()->T?{
if isEmpty{
return nil
}else{
return array.first
}
}
public var front:T?{
return array.first
}
}
*/
/*
优化的队列，以数组为基础创建队列，出队的时候都是最前边的元素移除
数组的特性，移除元素它后边的所有元素都要移动位置，性能较低
队列每次出队都移除数组元素导致性能低下，
优化方案，出队到一定数量再移动元素，一次移动可满足多次出队
*/
struct Queue<T> {
fileprivate var array:[T?] = []
fileprivate var head:Int = 0
public var count:Int{
return array.count - head
}
public var isEmpty:Bool{
return count == 0
}
public mutating func enQueue(_ element:T){
array.append(element)
}
public mutating func deQueue()->T?{
guard let element = array[guarded:head] else {
return nil
}
array[head] = nil
head += 1
let persent = Double(array.count - head)/Double(array.count)
if array.count > 50 && persent > 0.25 {
array.removeFirst(head)
head = 0
}
return element
}
public var front:T?{
return array[head]
}
}
extension Array {
subscript(guarded idx : Index) ->Element?{
if (startIndex...endIndex).contains(idx) {
return self[idx]
}else{
return nil
}
}
}
//stack implement queue
struct QueueImlStark<T> {
private var stackA = Stack<T>()
private var stackB = Stack<T>()
public var count:Int{
return stackA.count + stackB.count
}
public var isEmpty: Bool{
return stackA.isEmpty && stackB.isEmpty
}
/**
* 入队操作
* @Param element
*/
public mutating func enQueue(_ element:T){
stackA.push(element)
}
/**
*
* 出队操作
*/
public mutating func deQueue() ->T?{
if (stackB.isEmpty){
if (stackA.isEmpty){
return nil
}
fetchFormStackA();
}
return stackB.pop();
}
/**
* 从stackA栈中拿到出栈元素压入栈B
*/
private mutating func fetchFormStackA() {
while (!stackA.isEmpty){
stackB.push(stackA.pop()!);
}
}
}
三、二叉树
//
// Tree.swift
// DataStructure
//
// Created by dzq_mac on 2020/8/26.
// Copyright © 2020 dzq_mac. All rights reserved.
//
import Foundation
class TreeNode<T> {
public var value:T
public var leftNode:TreeNode<T>?
public var rightNode:TreeNode<T>?
init(_ value:T) {
self.value = value
}
}
class Tree<T> {
var rootNode:TreeNode<T>?
init(head:TreeNode<T>) {
self.rootNode = head
}
/// depth,递归方法获取最大深度
/// - Parameter root: node
/// - Returns: tree depth
func maxDepth(root :TreeNode<T>? = nil) -> Int{
guard let rNode = root else{
return 0
}
return max(maxDepth(root: rNode.leftNode), maxDepth(root: rNode.rightNode)) + 1
}
/*
//1.s型顺序访问二叉树,默认先左后右；利用两个栈来实现；如果先右后左的话，改变一下入栈的顺序就行
//2.注意s1 s2插入栈的顺序是不同的
void S_LevelOrderPrint(TreeNode t)
{
stack<TreeNode> s1;
stack<TreeNode> s2;
s1.push(t);//S
while(!s1.empty() || !s2.empty())
{
if(!s1.empty())
{
while(!s1.empty())
{
TreeNode tn = s1.top();
cout<<tn.val<<"";
s1.pop();
if(tn.right != null)
{
s2.push(tn.right);
}
if(tn.left != null)
{
s2.push(tn.left);
}
}
}
else
{
while(!s2.empty())
{
TreeNode tn = s2.top();
cout<<tn.val<<" ";
s2.pop();
if(tn.left != null)
{
s1.push(tn.left);
}
if(tn.right != null)
{
s1.push(tn.right);
}
}
}
}
}
*/
}
//MARK:- 递归实现遍历
func preOrderTraversal<T>(rootNode:TreeNode<T>) ->[T] {
var arr = [T]()
func traversal(node:TreeNode<T>?){
guard let root = node else{
return
}
arr.append(root.value)
traversal(node: root.leftNode)
traversal(node: root.rightNode)
}
traversal(node: rootNode)
return arr
}
func midOrderTraversal<T>(rootNode:TreeNode<T>) ->[T] {
var arr = [T]()
func traversal(node:TreeNode<T>?){
guard let root = node else{
return
}
traversal(node: root.leftNode)
arr.append(root.value)
traversal(node: root.rightNode)
}
traversal(node: rootNode)
return arr
}
func aftOrderTraversal<T>(rootNode:TreeNode<T>) ->[T] {
var arr = [T]()
func traversal(node:TreeNode<T>?){
guard let root = node else{
return
}
traversal(node: root.leftNode)
traversal(node: root.rightNode)
arr.append(root.value)
}
traversal(node: rootNode)
return arr
}
//MARK: stack imp traversal
func preOrderTraversalWithStack<T>(rootNode:TreeNode<T>) ->[T]{
var res = [T]()
var stack = Stack<TreeNode<T>>()
var node :TreeNode<T>? = rootNode
while !stack.isEmpty || node != nil {
if node != nil {
res.append(node!.value)
stack.push(node!)
node = node!.leftNode
} else {
node = stack.pop()?.rightNode
}
}
return res
}
func midOrderTraversalWithStack<T>(rootNode:TreeNode<T>) ->[T]{
var res = [T]()
var stack = Stack<TreeNode<T>>()
var node :TreeNode<T>? = rootNode
while !stack.isEmpty || node != nil {
if node != nil {
stack.push(node!)
node = node!.leftNode
} else {
node = stack.pop()
res.append(node!.value)
node = node?.rightNode
}
}
return res
}
/*
后序遍历时由于访问完左右子树后才能访问根结点，因此需要将根结点在栈内保留到左右子树被访问后，但同时会出现一个问题，当右子树弹出后遇到根结点又会将右子树结点压入栈中，造成死循环，因此我们需要在定义一个变量last代表最后一个访问的结点，当last与栈顶结点的右子树结点相同时，则不再将右子树结点压入栈中。
*/
func aftOrderTraversalWithStack<T>(rootNode:TreeNode<T>) ->[T]{
var res = [T]()
var stack = Stack<TreeNode<T>>()
var node :TreeNode<T>? = rootNode
var last:TreeNode<T>? = nil
while !stack.isEmpty || node != nil {
if node != nil {
stack.push(node!)
node = node!.leftNode
} else {
node = stack.top
if let right = node?.rightNode,right !== last{//考虑栈顶结点的右子树结点。存在且没被访问过，将右子树结点压入栈中
node = right
}else{
res.append(node!.value)
last = node
//node置空作用在于当原栈顶结点被访问并弹出后，下一层while是将当前栈顶结点的左子树入栈，当前栈顶结点的左子树已经被遍历过
//因此会造成死循环，所以将node置空，直接考虑当前栈顶结点的右子树
//一旦某个结点入栈，首先会遍历这个结点的左子树，然后考虑右子树的情况
stack.pop()
node = nil
}
}
}
return res
}
//按层遍历
func layerTraversal<T>(rootNode:TreeNode<T>) ->[T]{
var arr = [T]()
var queue = Queue<TreeNode<T>>()
let node:TreeNode<T>? = rootNode
queue.enQueue(node!)
while !queue.isEmpty {
if let cur = queue.deQueue() {
arr.append(cur.value)
if let left = cur.leftNode{
queue.enQueue(left)
}
if let right = cur.rightNode {
queue.enQueue(right)
}
}
}
return arr
}
//S遍历
func sLayerTraversal<T>(rootNode:TreeNode<T>) ->[T] {
var arr = [T]()
var stack1 = Stack<TreeNode<T>>()
var stack2 = Stack<TreeNode<T>>()
stack2.push(rootNode)
while !stack1.isEmpty || !stack2.isEmpty {
if !stack1.isEmpty {
while !stack1.isEmpty {
let node = stack1.pop()!
arr.append(node.value)
if let right = node.rightNode {
stack2.push(right)
}
if let left = node.leftNode {
stack2.push(left)
}
}
}else{
while !stack2.isEmpty {
let node = stack2.pop()!
arr.append(node.value)
if let left = node.leftNode{
stack1.push(left)
}
if let right = node.rightNode {
stack1.push(right)
}
}
}
}
return arr
}
四、链表
//
// Link.swift
// DataStructure
//
// Created by dzq_mac on 2020/8/29.
// Copyright © 2020 dzq_mac. All rights reserved.
import Foundation
class LinkNode<T> {
var value:T
var nextNode:LinkNode<T>?
init(_ value:T) {
self.value = value
}
}
public struct LinkTable<T> {
private var headNode:LinkNode<T>?
private(set) var count:Int = 0 //内部可写，外部只读
var valueArray : [T] {
get {
var arr = [T]()
var node = headNode
while node != nil {
arr.append(node!.value)
node = node?.nextNode
}
return arr
}
}
public mutating func append(_ element :T) {
let node = LinkNode<T>(element)
if self.headNode != nil{
var tamp = self.headNode
while tamp?.nextNode != nil {
tamp = tamp?.nextNode
}
tamp?.nextNode = node
}else{
headNode = node
}
count += 1
}
@discardableResult
public mutating func insert(_ element: T,at index:Int) -> Bool{
guard index >= 0 else{
return false
}
// if index > count{
// //插入失败，越界
// return false
// }
if index == 0 {
let new = LinkNode<T>(element)
new.nextNode = headNode
headNode = new
count += 1
return true
}
var lenth = 0
var node = headNode
while node != nil {
lenth += 1
if lenth == index {
let new = LinkNode<T>(element)
new.nextNode = node?.nextNode
node?.nextNode = new
count += 1
return true
}
node = node?.nextNode
}
return false
}
public mutating func removeAll(){
guard headNode != nil else{
count = 0
return
}
var node = headNode
headNode = nil
while node != nil {
let tamp = node?.nextNode
node?.nextNode = nil
node = tamp
}
count = 0
}
@discardableResult
public mutating func removeObject(at index:Int) -> Bool{
guard index >= 0 && headNode != nil else{
return false
}
if index == 0{
headNode = headNode?.nextNode
return true
}
var lenth = 0
var node = headNode
while node != nil {
lenth += 1
if lenth == index {
node?.nextNode = node?.nextNode?.nextNode
return true
}
node = node?.nextNode
}
return false
}
public mutating func reverse(){
var node = headNode
var nextNode = headNode?.nextNode
node?.nextNode = nil
while node != nil && nextNode != nil{
let tamp = nextNode?.nextNode
nextNode?.nextNode = node
node = nextNode
nextNode = tamp
}
headNode = node
//
}
public mutating func reverseWithStack(){
var node = headNode
var stack = Stack<LinkNode<T>>()
while node != nil {
stack.push(node!)
node = node?.nextNode
}
headNode = stack.pop()
node = headNode
while stack.top != nil {
node?.nextNode = stack.pop()
node = node?.nextNode
}
node?.nextNode = nil//原来的头节点，现在的尾节点，next置空
}
}
public extension LinkTable where T : Comparable {
mutating func remove(element:T) {
while let val = headNode?.value,val == element{
headNode = headNode?.nextNode
}
var node = headNode
while node != nil {
if node?.nextNode?.value == element {
node?.nextNode = node?.nextNode?.nextNode
}
node = node?.nextNode
}
}
}