目录
- 基本性质
- 栈和队列的基本操作
- 双端队列和优先级队列
- 深度优先遍历(DFS)和广度优先遍历(BFS)
- 递归函数与系统函数栈
-
实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作
- 如何保存最小值
-
仅用栈结构实现队列结构
- 如何保证栈结构能够先进先出
- 何时进行倾倒操作
- 仅用队列结构实现栈结
-
实现一个栈的逆序，不能申请额外的数据结构，只能使用栈本身的功能
- 移除栈底元素，并将其返回
- 将栈中的元素排序
基本性质
-
栈---先进后出
-
队列---先进先出
-
栈和队列通常都有数组和链表两种实现方式
数组相对容易，链表需要进行一些指针操作
栈和队列的基本操作
-
pop操作
弹出栈顶元素
-
top或peek操作
只访问而不弹出栈顶元素
-
push操作
从栈顶压入一个元素
-
size操作
返回当前栈中元素个数
对于队列，push是在队列头部加入一个元素，pop是在尾部弹出一个元素。
栈和队列的基本操作，时间复杂度都是O(1) 。
双端队列和优先级队列
-
双端队列
首尾都可以压入和弹出元素
-
优先级队列
弹出时，根据元素的优先级决定弹出的顺序。
具体实现上为一个堆结构，而不是线性表结构。
深度优先遍历(DFS)和广度优先遍历(BFS)
-
深度优先遍历(前序遍历)。使用栈的结构
先尝试将左元素入栈，若栈顶元素为空则将栈顶推出然后尝试遍历右节点。直到栈为空则遍历结束。
func preorderTraversal(root: TreeNode?) -> [Int] {
var res = [Int]()
var stack = [TreeNode]() //遍历用的栈
var node = root//遍历的根节点
while !stack.isEmpty || node != nil {
if node != nil {
res.append(node!.val) //将当前节点的值记录
stack.append(node!) //将当前节点加入栈中
node = node!.left //尝试遍历当前节点的左节点
} else {
node = stack.removeLast().right //将栈顶节点推出，并尝试遍历其父元素的右节点。
}
}
return res
}
遍历的结果为：1，2，4，5，3，6，7
-
广度优先遍历。使用队列结构
从root节点开始依次入队，当从队列推出一个元素时，尝试将其两个子元素依次加入加入队列。直到队列为空遍历结束。
遍历的结果为：1，2，3，4，5，6，7
递归函数与系统函数栈
平时使用的递归函数实际上是有系统负责向系统函数栈中进行压栈
递归过程可以看作是递归函数依次进入函数栈的处理过程
所有用递归函数可以做的过程，都可以用非递归的方式实现。
实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作
【要求】
- pop、push、getMin操作的时间复杂度都是O(1)。
- 设计的栈类型可以使用现成的栈结构。
如何保存最小值
需要两个栈，StackData以及StackMin。StackData负责正常压栈，StackMin负责记录当前最小值。
当进行push操作时，当前元素与StackMin栈顶元素进行比较，将较小的数压入StackMin。
当进行pop操作时，StackData以及StackMin同时进行pop。
当进行getmin操作时，由StackMin负责进行peek。
时间复杂度为O(1)，额外空间复杂度为O(N)
仅用栈结构实现队列结构
需要两个栈结构实现。一个栈作为压入栈(StackPush)负责承接push元素，一个栈作为弹出栈(StackPop)负责弹出pop元素。
-
如何保证栈结构能够先进先出
通过将StackPush的数据倒入StackPop中，来将StackPush中数据的顺序颠倒，保证先进先出。
这个倾倒操作需要有两个注意的点：
-
StackPop栈为空。 - 每次需要将
StackPush栈所有的数据全部倒入StackPop栈。
-
何时进行倾倒操作
当任何StackPush或者StackPop栈内的数据改变时，可以尝试倾倒操作。
仅用队列结构实现栈结
需要两个队列实现。
当进行pop操作时，将当前使用的CurrentQueue中元素推入辅助队列HelpQueue，仅保留队尾元素返回给用户。
然后将CurrentQueue与HelpQueue的指针互换，保证push操作时，CurrentQueue始终为有内容的队列。
实现一个栈的逆序，不能申请额外的数据结构，只能使用栈本身的功能
-
移除栈底元素，并将其返回
通过递归的方式，每层保存相应的栈顶元素。获取到栈底元素后再依次压入栈中
/// 移除栈底元素，并将其返回
///
/// - Parameter stack: 栈
/// - Returns:栈底元素
func getLast(stack : Stack) -> Int {
let value = stack.pop() //获得当前栈顶元素
if stack.isEmpty() { //如果栈为空
return value //当前元素则为栈底元素
}else {
let last = getLast(stack)
stack.push(value)
return last
}
}
将栈中的元素排序
【要求】
- 值允许申请一个栈
- 可以申请变量
- 不能申请额外的数据结构
原栈为stack，辅助栈为help。
从stack栈中pop出来的元素计作current
若current小于help栈顶元素，则直接压入栈中。
若current大于help栈顶元素，则将help栈顶推出并压入stack。
重复，直到stack中元素为0。然后将help倒回给stack
