五、基本结构_线性结构

jessie / 2024-01-29 / 原文

五、基本结构_线性结构

线性结构 Linear Structure

线性结构是一种有序数据项的集合，其中每个数据项都有唯一的前驱和后继。

除了第一个没有前驱，最后一个没有后继，新的数据项加入到数据集中时，只会加入到原有某个数据项之前或之后
具有这种性质的数据集，就称为线性结构。

线性结构总有两端，称呼不同，“左”“右”“前”“后”“顶”“底”。

两端的称呼并不是关键，不同线性结构的关键区别在于数据项增减的方式：有的结构只允许数据项从一端添加，而有的结构则允许数据项从两端移除。

四种：栈Stack、队列Queue、双端队列Deque、列表List
上面四种的共同点在于：数据项之间只存在先后次序关系，都是线性结构

运用广泛：进程、消息队列、编译

栈 Stack

一种有次序的数据项集合，在栈中，数据项的加入和移除都仅发生在同一端，这一端叫栈“顶top”，另一端叫栈“底base”。
距离栈底越近的数据项，留在栈中的时间就越长，（因为我们在栈顶操作），而最新加入的栈的数据项会被最先移除；这种次序通常称为“后进先出LIFO” last in first out

这是一种基于数据项保存时间的次序，时间越短的离栈顶越近，而时间越长的离栈底越近。
这种访问次序反转的特性，我们在某些计算机操作上碰到过：浏览器的后退back按钮，最先back的时最近访问的网页。撤销按钮，也是撤销最近的操作。

这一类特性，我们抽象成数据类型“栈”，是一个有次序的数据集，每个数据项仅从“栈顶”一端加入到数据集中、从“栈顶”一端在数据集中移除，栈具有后进显出LIFO的特性。

抽象数据类型“栈”定义为如下的操作：

Stack():创建一个空栈，不包含任何数据项
push(item):将item加入栈顶，无返回值
pop():将栈顶数据项移除，并返回，栈被修改
peek():"窥视"栈顶数据项，返回栈顶的数据项但不移除，栈不被修改
isEmpty():返回栈是否为空栈
size():返回栈中有多少个数据项

看看python如何实现它：
python的面向对象机制，可以用来实现用户自定义类型
将ADT Stack实现为python的一个class
将ADT Stack的操作实现为class的方法
由于Stack是一个数据集，所以可以采用python的原生数据集来实现，我们选用最常用的数据集List来实现。
一个细节：Stack的两端对应list设置
可以将List的任意一端(index=0,或者-1)设置为栈顶
我们选用List的末端(index=-1)作为栈顶，这样栈的操作就可以通过对list的append和pop来实现，很简单！

class Stack:
    def __init__(self):
        self.items = []
    
    def isEmpty(self):
        return self.items == []
    
    def push(self,item):
        self.items.append(item)
    
    def pop(self):
        return self.items.pop()
    
    def peek(self):
        return self.items[len(self.items)-1]
    
    def size(self):
        return len(self.items)

from pythonds.basic.stack.stack import Stack

s = Stack()

print(s.isEmpty())
s.push(4)
s.push('dog')
print(s.peek())
s.push(True)
print(s.size())
print(s.isEmpty())
s.push(8,4)
print(s.pop())
print(s.pop())
print(s.size())

如果我们把List的另一端（首端index=0）作为Stack的栈顶，同样可可以实现Stack

但性能有所不同，栈顶首端的版本（左），其push/pop的复杂度为O(n)，而栈顶尾端的实现（右），其push/pop的复杂度为O(1)

（在四、python数据类型的性能中我们知道对于列表pop()和pop(0)是不一样的。）

栈的应用：简单括号匹配

对括号是否正确匹配的识别，是很多语言编译器的基础算法。

如何让构造括号匹配识别算法

从左到右扫描括号串，最新打开的左括号，应该匹配最先遇到的右括号。这样，第一个左括号（最早打开），就应该匹配最右边一个右括号（最后遇到）

这种次序反转的识别，正好符合栈的特性！

from pythonds.basic.stack import Stack

def parChecker(symbolString):
    s = Stack()  # 定义一个空栈
    balanced = True  # 字段括号是否能全匹配
    index = 0
    while index < len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol == "(":
            s.push(symbol)  # 取出左括号(放到栈s里
        else:
            if s.isEmpty():
                balanced = False
            else:
                s.pop()   # 如果是右括号），且栈s不为空,说明栈s里有左括号可以pop()
        index = index + 1
        
    if balanced and s.isEmpty():
        return True   # 栈里的左括号都匹配完pop后，栈s为空
    else:
        return False
    
print(parChecker('((()))'))
print(parCherker('(()'))
print(parChecker('(()())'))

这样判断的逻辑是：最左边的左括号（ push 到最右边，方便最左边的左括号（能和最后边的右括号）匹配上，最右边的左括号（能和最左边的右括号）匹配上。

更多括号的匹配

[],{},()

通用括号匹配算法：代码

(待改)
from pythonds.basic.stack import Stack

def parChecker(symbolString):
    s = Stack()
    balanced = True
    index = 0
    while index < len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol in "(":
            s.push(symbol)
        else:
            if s.isEmpty():
                balanced = False
            else:
                s.pop()
        index = index + 1
        
    if balanced and s.isEmpty():
        return True
    else:
        return False

html/xml文档也有类似于括号的开闭标记，这种层次结构化文档的校验，操作也可以通过栈来实现