1.基础概念

1.1数据结构定义

数据结构=数据+存储方式+操作

数据 - 存储什么数据？如int,string类型存储方式 - 如何组织数据与数据之间的关系操作 - 如何快速的读取查询数据，写入数据到数据结构中

1.2何为线性数据结构

元素的顺序取决于添加顺序或移除顺序。一旦某个元素被添加进来，它与前后元素的相对位置 将保持不变。这样的数据集合经常被称为线性数据结构。

线性数据结构可以看作有两端。这两端有时候被称作“左端”和“右端”，有时候也被称作 “前端”和“后端”。当然，它们还可以被称作“顶端”和“底端”。名字本身并不重要，真正区 分线性数据结构的是元素的添加方式和移除方式，尤其是添加操作和移除操作发生的位置。

2.栈与队列

2.1栈

2.1.1原理

栈是一种后进先出（LIFO)的数据结构。后进的是顶端，先进的是底端。 观察元素的添加顺序和移除顺序，就能理解栈的重要思想。

2.1.2操作

push 放入一个元素pop 弹出一个元素top 获取栈顶元素empty 判断栈是否为空 # -*- coding:utf-8 -*- class Stack: """使用List模拟栈""" def __init__(self): self.items = [] def isEmpty(self): return len(self.items)==0 def push(self, item): self.items.append(item) def pop(self): return self.items.pop() def peek(self): if not self.isEmpty(): return self.items[len(self.items)-1] def size(self): return len(self.items)

2.1.3 实例

leetcode T20 有效括号

class Solution: def isValid(self, s: str) -> bool: stack=[] for c in s: if c in ('(', '[','{'): stack.append(c) else: if len(stack)==0: return False if stack[-1] in '(' and c not in ')': return False if stack[-1] in '[' and c not in ']': return False if stack[-1] in '{' and c not in'}': return False stack.pop() return len(stack)==0

2.2队列

2.2.1 原理

队列是有序集合，添加操作发生在‘队尾’，移除操作发生在‘队首’。新元素从尾部进入队列，然后一直向前移动到头部，直到成为下一个被移除的元素。

2.2.2 操作

Queue()创建一个空队列 enqueue(item)在队列的尾部添加一个元素 dequeue()从队列的头部移除一个元素

2.2.2.1 Python模块操作

import Queue queue = Queue.Queue(maxsize= 10)#创建一个空队列 queue.put() #在队列的尾部添加一个元素 queue.get()#从队列的头部移除一个元素

2.2.2.2 用Python实现队列_基于链表

class Node: def __init__(self, value): self.value = value self.next = None class Queue: def __init__(self): self.count = 0 self.head = None self.tail = None def enqueue(self, value): node = Node(value) if self.head is None: self.head = node self.tail = node else: self.tail.next = node self.tail = node self.count += 1 def dequeue(self): if self.head is None: # or self.count == 0 or se.f.is_empty() raise Exception('This is a empty queue') cur = self.head self.head = cur.next self.count -= 1 return cur.value def is_empty(self): return self.head is None # or self.count == 0 def size(self): return self.count

引用

Python数据结构与算法分析（第2版）作者: [美] 布拉德利·米勒 / [美] 戴维·拉努姆 译者: 吕能 / 刁寿钧