数据结构与算法——栈（python详细版附带例子）

author：小黄
缓慢而坚定的生长

栈

栈是由一系列对象组成的一个集合，这些对象的插入和删除遵循后进先出（LIFO）的原则。其基本结构如下图所示，

栈是最简的数据结构，但同样也是最重要的书籍结构。

用S表示一个栈，其基本的一些函数如下：

• S.push(a)：将一个元素a添加到栈S的栈顶；
• S.pop()：从栈S中移除并返回该元素，如果此时栈是空的，则返回一个错误；
• S.top()：返回栈顶元素但并不移除，就是说看栈顶的元素值，如果栈为空，则返回一个错误；
• S.isEmpty()：如果是空栈，则返回“True”，否则“False”;
• S.len()：返回栈S中元素的数量。

下面用一个例子讲解一下栈的相关操作：

看完这个例子，相信你们对这个栈有了进一步的了解，下面将用函数来带你们了解栈。

基于数组的栈实现

可以通过在python列表中存储一些元素来实现一个栈；用到的相关函数有：append()、pop()、len()
详细代码如下：

class ArrayStack:

    def __init__(self):
        # 创建一个空栈
        self._data = []
    
    def __len__(self):
        # 返回栈中的元素数量
        return len(self._data)

    def isEmpty(self):
        # 如果栈为空则返回“True”
        return len(self._data) == 0
    
    def push(self,a):
        # 向栈顶添加元素a
        self._data.append(a)

    def pop(self):
        # 移除栈顶的元素并返回，如果栈为空，则返回一个错误
        if self.isEmpty():
            raise Exception('Stack is empty')
        return self._data.pop()

    def top(self):
        # 返回栈顶的元素但不移除，如果栈为空，则返回一个错误
        if self.isEmpty():
            raise Exception('Stack is empty')
        return self._data[-1]

复杂度分析：

例1：（）匹配问题

每个开始符合必须与其相对应的结束符合相匹配：

• 正确 ()(())
• 错误 ()()(
• 错误 ()())

完整代码如下:

class ArrayStack:

    def __init__(self):
        # 创建一个空栈
        self._data = []
    
    def __len__(self):
        # 返回栈中的元素数量
        return len(self._data)

    def isEmpty(self):
        # 如果栈为空则返回“True”
        return len(self._data) == 0
    
    def push(self,a):
        # 向栈顶添加元素a
        self._data.append(a)

    def pop(self):
        # 移除栈顶的元素并返回，如果栈为空，则返回一个错误
        if self.isEmpty():
            raise Exception('Stack is empty')
        return self._data.pop()

    def top(self):
        # 返回栈顶的元素但不移除，如果栈为空，则返回一个错误
        if self.isEmpty():
            raise Exception('Stack is empty')
        return self._data[-1]


def parCheck(s):
    # s是字符串类型
    a = ArrayStack()
    balance = True # 这是标记
    for i in  s:
        if i == '(':
            a.push(i)
        else:
            if a.isEmpty():
                balance = False
                break
            else:
                a.pop()
    if a.isEmpty() and balance:
        return True
    else:
        return False
    

例2：{}匹配问题

• 正确 (){}[]
• 错误 {}[(])

class ArrayStack:

    def __init__(self):
        # 创建一个空栈
        self._data = []
    
    def __len__(self):
        # 返回栈中的元素数量
        return len(self._data)

    def isEmpty(self):
        # 如果栈为空则返回“True”
        return len(self._data) == 0
    
    def push(self,a):
        # 向栈顶添加元素a
        self._data.append(a)

    def pop(self):
        # 移除栈顶的元素并返回，如果栈为空，则返回一个错误
        if self.isEmpty():
            raise Exception('Stack is empty')
        return self._data.pop()

    def top(self):
        # 返回栈顶的元素但不移除，如果栈为空，则返回一个错误
        if self.isEmpty():
            raise Exception('Stack is empty')
        return self._data[-1]

def isright(s):
    left = '{[(' # 注意左右括号的索引要一一对应
    right = '}])'
    a = ArrayStack()
    for i in s:
        if i in left:
            a.push(i)
        elif i in right:
            if a.isEmpty():
                return False
            # 判断此时右括号与当前栈弹出的左括号的索引是否相同
            if right.index(i) != left.index(a.pop()):
                return False
    return a.isEmpty()