Python数据结构与算法-栈

栈

栈（stack）又名堆栈，是一种运算受限的线性表。其是仅允许在表的一端进行插入和删除运算。

允许进行插入和删除操作的一段称为栈顶（top）,另一端称为栈底（bottom）

栈底固定，栈顶浮动。

栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH）， 删除则称为退栈（POP）。

后进先出（LIFO，Last In First Out）, 后进先出表。

进栈和退栈时间复杂度都为O（1）

class Stack(object):
    def __init__(self, limit=10):
        """ 创建空栈
        """
        self.stack = [] # 存放元素
        self.limit = limit # 栈容量
    
    def push(self, data):
        """ 将元素data加入栈，也常称为压入或推入
        """
        # 判断栈是否溢出
        if len(self.stack) >= self.limit:
            raise IndexError('超出栈的最大容量！')
        self.stack.append(data)

    def pop(self):
        """ 删除栈里最后压入的元素并将其返回，常称为弹出。
        """
        if self.stack:
            return self.stack.pop()
        else:
            raise IndexError('pop from an empty stack')

    def top(self):
        """ 取得栈里最后压入的（最上面的）元素，不删除。
        """
        if self.stack:
            return self.stack[-1]

    def is_empty(self):
        """ 判断栈是否为空， 空时返回True, 否则返回 False
        """
        return not bool(self.stack)

    def size(self):
        """ 取得栈中的元素个数
        """
        return len(self.stack) 
st = Stack()

应用：括号匹配

"""
使用一个堆栈检查括号字符串是否平衡

有效括号字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
举例：

((())): True

((()): False

(())): False
"""
import stack
st = stack.Stack()

input_str = "(()"

for s in input_str:
	if st.top() == s:
		st.pop()
	else:
		st.push(s)

result = True if st.is_empty() else False
print(result)