what's the 数据结构

what‘s the 数据结构

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

　　通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

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

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

下面我来重点来学习数据结构中比较重要的几种：栈、队列、链表、哈希表、二叉搜索树

栈

　　栈(Stack)是一个数据集合，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。可以将栈理解为只能在一端进行插入或删除操作的列表。

　　栈的特点：后进先出、先进后出（类似于往箱子里放东西，要拿的时候只能拿最上面的而最上面的是最后进的）

　　栈操作：进栈push、出栈pop、取栈顶gettop（在Python中，不用自定义栈，直接用列表就行，进栈函数：append 出栈函数：pop 查看栈顶函数：li[-1]）

栈的应用

　　栈可以应用在处理括号匹配问题——括号匹配问题：给一个字符串，其中包含小括号、中括号、大括号，求该字符串中的括号是否匹配。

基本思路：按顺序遍历字符串是左括号则进栈，来的是右括号则将栈顶左括号pop，若来的右括号与栈顶左括号不匹配或空栈情况下来了右括号则返回错误信息

def brace_match(s):
    stack = []
    match = {‘)‘:‘(‘, ‘]‘:‘[‘, ‘}‘:‘{‘}
    match2 = {‘(‘:‘)‘, ‘[‘:‘]‘, ‘{‘:‘}‘}
    for ch in s:
        if ch in {‘(‘, ‘[‘, ‘{‘}:
            stack.append(ch)#左括号入栈
        elif len(stack) == 0:
            print("缺少%s" % match[ch])#栈空了，但却来了一个右括号
            return False
        elif stack[-1] == match[ch]:#栈顶左括号与来的右括号相匹配
            stack.pop()#出栈
        else:
            print("括号不匹配")
            return False
    if len(stack) > 0:#全部操作完后栈内还有剩余左括号
        print("缺少%s" % (match2[stack[-1]]))#显示栈顶左括号对应的右括号
        return False
    print(‘合法‘)
    return True


brace_match("[{()[]}{}{}")#缺少]

队列

　　队列(Queue)是一个数据集合，仅允许在列表的一端进行插入，另一端进行删除。 进行插入的一端称为队尾(rear)，插入动作称为进队或入队；进行删除的一端称为队头(front)，删除动作称为出队。和栈一样，队列是一种操作受限制的线性表。

　　队列的性质：先进先出（可以将队列理解为排队买东西）

　　特殊情况——双向队列：队列的两端都允许进行进队和出队操作。

如何用列表实现队列：

1. 初步设想：列表+两个下标指针
2. 创建一个列表和两个变量，front变量指向队首，rear变量指向队尾。初始时，front和rear都为0。
3. 进队操作：元素写到li[rear]的位置，rear自增1。
4. 出队操作：返回li[front]的元素，front自减1。

以上就是队列实现的基本思路，但是其实队列的实现原理是一个环形队列

环形队列：当队尾指针front == Maxsize + 1时，再前进一个位置就自动到0。

• 实现方式：求余数运算
• 队首指针前进1：front = (front + 1) % MaxSize
• 队尾指针前进1：rear = (rear + 1) % MaxSize
• 队空条件：rear == front
• 队满条件：(rear + 1) % MaxSize == front

在Python中，有一个内置模块可以帮我们快速建立起一个队列——deque模块

"""
使用方法：from collections import deque
创建队列：queue = deque(li)
进队：append()
出队：popleft()
双向队列队首进队：appendleft()
双向队列队尾进队：pop()
"""

栈和队列的知识点应用：

　　用栈和队列的知识来解决迷宫问题：http://www.cnblogs.com/zhuminghui/p/8414307.html