基本结构——栈_栈的基本结构

中国大学MOOC，数据结构与算法（Python版）学习笔记
课程网址：“https://www.icourse163.org/course/PKU-1206307812”

一. 什么是线性结构：

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

二. 栈（Stack）:

基本概念：

栈就是一种有次序的数据项集合，是一种线性结构。在栈中 ，数据项的加入和移除都仅发生在同一端，这一端叫栈“顶(top)”，另一端叫栈“底(base)”。

基本特点：

离栈底越近的数据项，留在栈中的时间就越长，而最新加入栈的数据项会被最先移除，这种次序通常称为后进先出LIFO（Last in First out）这是一种基于数据项保存时间的次序，时间越短的离栈顶越近，而时间越长的离栈底越近。反转次序，进栈和出栈的次序正好相反。

抽象数据类型Stack:

Python实现：

# 栈的实现，以列表的尾端作为栈顶
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)
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

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

三. 栈的应用实例：

简单括号匹配：

如何构造括号匹配识别算法:
从左到右扫描括号串，最新打开的左括号，应该匹配最先遇到的右括号。这样，第一个左括号（最早打开），就应该匹配最后一个右括号（最后遇到）。这种次序反转的识别，正好符合栈的特性。

Python实现：

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:
                top = s.pop()
                if not matches(top, symbol):
                    balanced = False
        index = index + 1
    if balanced and s.isEmpty():
        return True
    else:
        return False
def matches(open, close):
    opens = "([{"
    closers = ")]}"
    return opens.index(open) == closers.index(close)
print(parChecker('{{([][])}()}'))
print(parChecker('[{()]}'))
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

十进制转二进制：

十进制转换为二进制，采用的是“除2取余法”将整数不断除以2，每次得到的余数就是由低到高的二进制位。
“除以2”的过程，得到的余数是从低到高的次序，而输出则是从高到低，所以需要一个栈来反转次序。

Python实现：

def divideBy2(decNum):
    remstack = Stack()
    while decNum > 0:
        rem = decNum % 2
        remstack.push(rem)
        decNum = decNum // 2
    binString = ""
    while not remstack.isEmpty():
        binString = binString + str(remstack.pop())
    return binString
print(divideBy2(42))
1
2
3
4
5
6
7
8
9
10
11