Fork me on GitHub

数据结构学习(一)--栈

栈(Stack)是所有数据结构中最简单但却是最重要的一种,栈出现的情况在对内含反转数据的应用非常适合。栈是属于 后进先出 - Last In, First Out(LIFO) ,最后压入栈中的项总是最先从栈中弹出的项,生活中举个例子说明下,装薯片的时候按顺序装入罐子中,但是吃薯片的时候就要从开口处把最后一个装入的薯片先吃掉。

栈是一种形式的表,属于表类型中的受限表,即插入和删除只发生在一端(表的末端)。在栈当中我们把这端成为栈顶(top)。当我们对栈顶进行插入操作时,即向栈中增加一项时,称之为入栈(push);对栈进行删除操作时,即从栈中删除一项时,称之为出栈(pop)。

核心方法

对于栈来说,主要的核心方法就是入栈和出栈两个方法,向栈顶入栈一个”i”的字符串:

1
stack.push("i")

目前栈中间的元素为[“i”],从栈里面出栈当前的元素:

1
stack.pop()

这样返回了元素”i”,并且当前栈为空。继续出栈会导致返回nil,通常在实际应用中这里会做错误处理,“栈下溢(stack underflow)”。

源代码

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
//
// Stack.swift
//
//
// Created by 叶帆 on 2017/9/6.
//
public struct Stack<T> {
fileprivate var array = [T]()
/**
获取当前栈的长度
- returns: 返回栈的长度,如果Stack为空,则值为0
*/
public var count: Int {
return array.count
}
/**
判断是否为空
- returns: 如果Stack为空,则值为true,否则值为false
*/
public var isEmpty: Bool {
return array.isEmpty
}
/**
获取栈顶元素的值
- returns: 栈顶元素的值,如果为空返回nil
*/
public var top: T? {
return array.last
}
/**
向栈顶插入一个元素
- parameter element: 需要插入的值
- 时间复杂度: O(1)
*/
public mutating func push(_ element: T) {
array.append(element)
}
/**
删除栈顶元素
- returns: 返回删除栈顶元素的值,如果为空返回nil
- 时间复杂度: O(1)
*/
public mutating func pop() -> T? {
return array.popLast()
}
}
extension Stack: Sequence {
public func makeIterator() -> AnyIterator<Element> {
var curr = self
return AnyIterator {
_ -> Element? in
return curr.pop()
}
}
}

应用场景

栈的强项是处理反转的能力,所以实际的应用场景都是和此相关的。

回文字符串

所谓的回文字符串就是指那些正读和反读均相同的字符系列,如“席主席”,“aha”均是回文,通过栈这种数据结构可以很容易判断一个字符串是否为回文。

大概的思路就是找到中间的值,把中间值以前的放入栈中,然后一个个出栈,并且在出栈的同时和中间值以后的值进行比对。如果top为空的时候就说明符合回文的规则。

逆波兰计算器

所谓的逆波兰计算器指的就是在这样的计算器中,操作数(通常是数字)在操作被指定前输入,操作数放入栈中。当操作执行时,操作数从栈中弹出并且把操作结果入栈。

括号的匹配

在程序中,通常会对{}[]()<>来进行括号的匹配。


版权声明



Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证

本文首发于Ivan’s Blog | 叶帆的博客博客( http://yeziahehe.com ),版权所有,侵权必究。

本文链接:http://yeziahehe.com/2017/09/07/Structure_stack/