Py008-02-02数据结构之栈

栈 Stack

栈是一种数据集合，可以理解为只能在一端进行插入和删除操作的列表

栈的特点

  • 后进先出LIFO

栈的概念

  • 栈顶
  • 栈底

栈的基本操作

  • 进栈（压栈）push
  • 出栈 pop
  • 取栈顶 gettop

生活实例

  • 弹匣的 压子弹，取子弹

栈的简单实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Stack:
    def __init__(self):
        self.stack = []
    
    def push(self,element):
        self.stack.append(element)
    
    def pop(self,element):
        if len(self.stack) > 0:
            return self.pop()
        else:
            return None
    def get_top(self):
        if len(self.stack) > 0 :
            return self.stack[-1]

    def is_empty(self):
        return len(self.stack) == 0

栈的应用

括号匹配问题：给一个字符串，其中包括小括号，中括号，大括号，求该字符串中括号是否匹配

例如

1
2
3
4
()()[]{} 匹配
([{()}]) 匹配
[](      不匹配
[(])     不匹配
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
36
37
38
39
40
41
42
43
class Stack:
    def __init__(self):
        self.stack = []
    
    def push(self,element):
        self.stack.append(element)
    
    def pop(self,element):
        if len(self.stack) > 0:
            return self.pop()
        else:
            return None
    def get_top(self):
        if len(self.stack) > 0 :
            return self.stack[-1]

    def is_empty(self):
        return len(self.stack) == 0

def brace_match(s):
    match = {
        '}':'{',
        ']':'[',
        ')':'('
        }
    stack = Stack()
    for ch in s:
        if ch in {'{','[','('}:
            stack.push(ch)
        else: # {'}',']',')'}
            if stack.is_empty():
                return False
            elif stack.get_top() == match[ch]:
                stack.pop()
            else: # stack.get_top() != match[ch]
                return False
    if stack.is_empty():
        return True
    else:
        return False

print(brace_match('[{({[]})}]'))
print(brace_match('[{]'))