栈(stack)
Varsion

后进者先出,先进者后出,这就是典型的“栈”结构。

栈的结构

在上面这个栈中,我们加入节点的顺序是 node3, node2, node1。而访问节点的时候,我们则按照从上到下的顺序:node1, node2, node3。

从栈的操作特性上来看,栈是一种“操作受限”的线性表,只允许在一端插入和删除数据。

从功能上来说,数组或链表确实可以替代栈,但你要知道,特定的数据结构是对特定场景的抽象,而且,数组或链表暴露了太多的操作接口,操作上的确灵活自由,但使用时就比较不可控,自然也就更容易出错。

当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性,我们就应该首选“栈”这种数据结构。

实现一个栈

栈既可以用数组来实现,也可以用链表来实现。用数组实现的栈,叫作顺序栈,用链表实现的栈,叫作链式栈。

1
2
3
4
5
6
7
8
# 节点
class Node
attr_accessor :value , :next
def initialize(value)
@value = value # 节点值
@next = nil # 指向下个节点
end
end
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
class Stack
def initialize # 初始化一个栈
@first = nil
@length = 0
end

attr_reader :first, :length

def push(item) # 向栈顶压入一个节点
old_first = @first # 备份原来的栈顶节点
@first = Node.new(item) # 新建一个节点,并将它标记为新的栈顶节点
@first.next = old_first # 将新的栈顶节点的next指针指向原来的栈顶节点。
@length += 1
end

def pop # 将栈顶的节点弹出
return nil if is_empty? # 栈本身为空的情况下直接返回空
item = @first.item # 保存原先栈顶节点的item
@first = @first.next # 将原栈的第二个节点标记为栈顶节点
@length -= 1
return item
end

def first # 返回栈顶的节点
return @first
end

def length # 返回栈的长度
return @length
end

def is_empty? # 返回栈是否为空
return @length == 0
end
end

函数调用栈

操作系统给每个线程分配了一块独立的内存空间,这块内存被组织成“栈”这种结构, 用来存储函数调用时的临时变量。每进入一个函数,就会将临时变量作为一个栈帧入栈,当被调用函数执行完成,返回之后,将这个函数对应的栈帧出栈。即,根据程序执行顺序,依次将每行代码压入数据栈。

利用栈实现表达式求值

编译器通过两个栈来实现表达式求值。其中一个保存操作数的栈,另一个是保存运算符的栈。我们从左向右遍历表达式,当遇到数字,我们就直接压入操作数栈;当遇到运算符,就与运算符栈的栈顶元素进行比较。

如果比运算符栈顶元素的优先级高,就将当前运算符压入栈;如果比运算符栈顶元素的优先级低或者相同,从运算符栈中取栈顶运算符,从操作数栈的栈顶取 2 个操作数,然后进行计算,再把计算完的结果压入操作数栈,继续比较。

这边就直接使用王争老师的图了

栈在括号匹配中的应用

我们假设表达式中只包含三种括号,圆括号 ()、方括号[]和花括号{},并且它们可以任意嵌套。比如,{[] ()[{}]}[{()}([])]等都为合法格式,而{[}()][({)]为不合法的格式。那我现在给你一个包含三种括号的表达式字符串,如何检查它是否合法呢?

这里也可以用栈来解决。我们用栈来保存未匹配的左括号,从左到右依次扫描字符串。当扫描到左括号时,则将其压入栈中;当扫描到右括号时,从栈顶取出一个左括号。如果能够匹配,比如()匹配,[]匹配,{}匹配,则继续扫描剩下的字符串。如果扫描的过程中,遇到不能配对的右括号,或者栈中没有数据,则说明为非法格式。

当所有的括号都扫描完成之后,如果栈为空,则说明字符串为合法格式;否则,说明有未匹配的左括号,为非法格式。


  • Post title:栈(stack)
  • Post author:Varsion
  • Create time:2020-08-02 16:20:43
  • Post link:https://blog.varsion.cn/post/cd0a8847.html
  • Copyright Notice:All articles in this blog are licensed under BY-NC-SA unless stating additionally.
Comments