CS基础:栈

2017-02-08  本文已影响15人  ChrisPzzz

栈:限定仅在表尾进行插入和删除操作的线性表。

其中允许插入和删除的一端成为栈顶,另一端成为栈底,不含任意元素的栈称为空栈。栈又称为后进先出(Last in first out)线性表

进栈:栈的插入操作。
出栈:栈的删除操作。

实现一个栈

推荐研读Swift Algorithm Club: Swift Stack Data Structure

定义一个结构体

struct Stack {
    fileprivate var array : [String] = []
}

结构体的数组属性用来储存栈的元素。

进栈

给结构体添加一个进栈函数:

mutating func push(element:String){
        array.append(element)
    }

出栈

给结构体添加一个出栈函数:

mutating func pop() -> String? {
        return array.popLast()
    }

查看栈顶元素

给栈添加一个查看当前栈顶的元素函数:

mutating func peek() -> String? {
        return array.last
    }

完善这个栈结构体

添加两个变量,分别表示栈是否为空栈及栈中的元素个数。

var isEmpty : Bool{
        return array.isEmpty
    }
    
    var count : Int {
        return array.count
    }

实践

首先添加一个 extension 帮助我们输出打印:

extension Stack{
    var description : String{
        let top = "---Stack---\n"
        let bottom = "\n-------\n"
        let stackElements = array.reversed().joined(separtor:"\n")
        return top + stackElements + bottom
  }
}

输入:

var stack = Stack()
stack.push(element:"熊大")
stack.push(element:"熊二")
stack.push(element:"周末")
stack.push(element:"蛋蛋")
print(stack.description)
print(stack.peek()!)
stack.pop()
print(stack.description)
print(stack.peek()!)

输出如下:

---Stack---
蛋蛋
周末
熊二
熊大
-------

蛋蛋
---Stack---
周末
熊二
熊大
-------

周末

用泛型特性来改造这个栈

改造栈:

struct Stack<T> {
    fileprivate var array : [T] = []
    
    mutating func push(element:T){
        array.append(element)
    }
    
    
    
    mutating func pop() -> T? {
        return array.popLast()
    }

    
    func peek() -> T?{
        return array.last
    }
    
    var isEmpty : Bool{
        return array.isEmpty
    }
    
    var count : Int {
        return array.count
    }
}

同时改造帮助打印输出 extension:

extension Stack{
    var description : String{
        let top = "---Stack---\n"
        let bottom = "\n-------\n"
        let stackElements = array.map{"\($0)"}.reversed().joined(separator:"\n")
        return top + stackElements + bottom
  }
}

实践

输入:

var stack = Stack<String>()
stack.push(element:"熊大")
stack.push(element:"熊二")
stack.push(element:"周末")
stack.push(element:"蛋蛋")
print(stack.description)
stack.pop()
print(stack.description)

输出:

---Stack---
蛋蛋
周末
熊二
熊大
-------

---Stack---
周末
熊二
熊大
-------

end

上一篇下一篇

猜你喜欢

热点阅读