堆栈

抽象数据类型描述

具有一定操作约束的线性表,只在一端(栈顶,Top)做插入,删除

  • 插入数据:入栈(Push)
  • 删除数据:出栈(Pop)
  • 后入先出:Last In First Out(LIFO)

类型名称:堆栈(Stack)

数据对象集:一个 有0个或多个元素的有穷线性表

操作集

  • 创建空堆栈
  • 判断堆栈是否已满
  • 将元素压入堆栈
  • 判断堆栈是否为空
  • 删除并返回栈顶元素

堆栈的顺序存储实现

通常由一个一维数组和一个记录栈顶元素位置的变量组成

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Stack<T:Hashable> {
    var data : Array<T> = Array();
    var top : Int = -1
    
    
    func push(_ item:T) -> Void {
        data.append(item)
        top += 1
    }
    
    func pop() -> T? {
        if top == -1 {
            print("空堆栈")
            return nil
        }
        top -= 1
        return data.popLast()
    }
}

let stack = Stack<Int>()
stack.push(0)
stack.push(1)

print(stack.pop())
print(stack.top)

堆栈的链式存储实现

堆栈的链式存储结构实际上是一个单链表,叫做链栈,插入和删除操作只能在链栈的栈顶进行

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class StackNode<T:Hashable> {
    var data : T?
    var next : StackNode?
}

class Stack<T:Hashable> {
    var top = StackNode<T>()// 指向栈顶,本身无意义
    
    func isEmpty() -> Bool {
        if top.next == nil {
            return true
        }
        else {
            return false
        }
    }
    
    func push(_ item:T) -> Void {
        let node = StackNode<T>();
        node.data = item;
        node.next = top.next;
        top.next = node
    }
    
    func pop() -> T? {
        if isEmpty() {
            print("空堆栈")
            return nil
        }
        
        let node = top.next
        top.next = top.next?.next
        return node!.data
    }
}

let stack = Stack<String>()
stack.push("aaa")
stack.push("bbb")
print(stack.top.next?.data)
print(stack.pop())
print(stack.pop())
print(stack.isEmpty())
stack.push("cccc")
print(stack.top.next?.data)

堆栈应用

后缀表达式求值

  • 从左向右扫描,逐个处理运算数和运算符号
  • 遇到运算数,入栈
  • 遇到运算符,出栈两个运算数,做运算
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class ExpressionOperation {
    func input(expression:[String]) -> Int {
        let stack = Stack<Int>()
        
        for value in expression {
            if isInt(string: value) {
                stack.push(Int(value)!)
            }
            else {
                let a = stack.pop()!
                let b = stack.pop()!
                var ret = 0
                
                switch value {
                    case "+":
                        ret = a + b;
                    case "-":
                        ret = b - a;
                    case "*":
                        ret = a * b;
                    case "/":
                        ret = b / a;
             
                    default:
                        ret = 0
                }
                stack.push(ret)
            }
        }
        return stack.top.next!.data!
    }
    
    func isInt(string: String) -> Bool {
        let scan: Scanner = Scanner(string: string)
        var val:Int = 0
        return scan.scanInt(&val) && scan.isAtEnd
    }
}

let test1 = ["1","1","+","2","*","2","-","1","/"]
let test2 = ["2","9","3","/","+","4","-"]
let exp = ExpressionOperation()
exp.input(expression: test)

中缀表达式求值

基本策略:将中缀表达式转换为后缀表示式,然后求值

  • 从头到尾读取中缀表达式的每个元素
  • 运算数:直接输出
  • 左括号:入栈
  • 右括号:将栈顶的运算符出栈并输出,直到遇到左括号(出栈,不输出)
  • 运算符:
    • 若优先级大于栈顶运算符时,则入栈
    • 若优先级小于栈顶运算符时,将栈顶运算符出栈并输出,再比较新的栈顶运算符,直到该运算符优先级大于栈顶运算符为止,然后该运算符入栈
    • 若对各个元素处理完毕,则把堆栈中留存的运算符一并输出

其他应用

  • 函数调用及递归实现
  • 深度优先搜索
  • 回溯算法