本文共 1637 字，大约阅读时间需要 5 分钟。

数据结构&栈

    今天来简单介绍一下啥是数据结构，啥是栈？

1. 啥是数据结构?

数据结构:指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。 简单来说，数据结构就是设计数据以何种方式组织并存储在计算机中。比如:列表、集合与字典等都是一种数据结构。

数据结构按照其逻辑结构可分为线性结构、树结构、图结构

• 线性结构:数据结构中的元素存在一对一的相互关系
• 树结构:数据结构中的元素存在一对多的相互关系
• 图结构:数据结构中的元素存在多对多的相互关系

2. 啥是栈？

栈(Stack)是一个数据集合，可以理解为只能在一端进行插入或删除操作的列表。

• 栈的特点:后进先出LIFO (last-in, first- -out)
• 栈的概念:栈顶、栈底
• 栈的基本操作:
  - 进栈(压栈) : push
  - 出栈: pop
  - 取栈顶: gettop

使用一般的列表结构即可实现栈

• 进栈: li.append
• 出栈: li.pop
• 取栈顶: li[-1]

栈的简单代码实现：

class Stack:    def __init__(self):        self.stack = []    def push(self, element):        self.stack.append(element)    def pop(self):        return self.stack.pop()    def get_top(self):        if len(self.stack) > 0:            return self.stack[-1]        else:            return None    def is_empty(self):        return len(self.stack) == 0

3. 栈的简单应用——括号匹配问题

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

()[]{}      匹配([{[]}])    匹配[](         不匹配[(])        不匹配

代码:

def brace_match(s):    match = {
   '}': '{', ']': '[', ')': '('}    stack = Stack()    for ch in s:        # 将所有左括号进栈，作为待匹配的括号        if ch in {
   '(', '[', '{'}:            stack.push(ch)        # 当字符不是左括号时，即字符为右括号时        else:    # ch in {')', ']', '}'}            # 如果栈是空的，即没有待匹配的左括号            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 Falseprint(brace_match('[{([])}]'))print(brace_match('[{({)}}]'))

结果为:

TrueFalse

即第一个为匹配，第二个为不匹配

转载地址：http://dbiwi.baihongyu.com/