队满条件：(rear+1)%maxsize=front
class queue: def __init__(self, capacity = 10): self.capacity = capacity self.size = 0 self.front = 0 self.rear = 0 self.array = [0]*capacity def is_empty(self): return 0 == self.size def is_full(self): return self.size == self.capacity def enqueue(self, element): if self.is_full(): raise Exception(\'queue is full\') self.array[self.rear] = element self.size += 1 self.rear = (self.rear + 1) % self.capacity def dequeue(self): if self.is_empty(): raise Exception(\'queue is empty\') self.size -= 1 self.front = (self.front + 1) % self.capacity def get_front(self): return self.array[self.front] 通过两个栈做一个队列的方法1号栈进栈 模拟进队操作。
2号站出栈，如果2号栈空，把1号站依次出栈并进2号栈，模拟出队操作。
通过摊还分析，时间复杂度还是O(1)。
class queue: def __init__(self,size): self.a = [] self.b = [] self.size = size def popleft(self): if not self.b and self.b is None: el = self.b.pop(-1) self.append(el) self.a.pop(-1) else: raise Exception("empty") def append(self,item): if self.b<self.size: self.b.append[item] else: raise Exception("FUll") python关于队列的模块 import queue #涉及线程安全用queue from collections import deque #常用解题的用deque q = deque() #是一种双向队列，popleft出队 #模拟linux命令 head和tail,假如是tail 5 deque(open(\'a.text\',\'r\',encooding=\'utf8\'),5) #建立一个定长的队列，当队列满了之后，就会删除第一行，继续添加 链表 相关知识点：链表就是非顺序表，与队列和栈对应。
链表中每一个元素都是一个对象，每个对象称为一个节点，包含有数据域key和指向下一个节点的next，通过各个节点之间的相互连接，最终串联成一个链表。
在机械硬盘中，文件就是以链表的形式存储的。
以FAT32为例，文件的单位是文件块(block)，一个文件块的大小是4k，一个文件的内容是由链表的方式连接文件块组成的。
链表的第一个节点被称为头节点，数据可以是空的，也可以有值。
头节点为空也是为了表示空链表，也叫做带空节点的链表，头节点也可以记录链表的长度
节点定义 class Node(object): def __init__(self,item): self.data=data self.next=None #eg a=Node(1) b=Node(2) c=Node(3) a.next=b b.next=c #链表的最后一个节点的next就为None 链表类的实现 class LinkList: def __init___(self,li,method=\'tail\'): self.head = None self.tail = None if method == \'head\': self.create_linklist_head(li) if method == \'tail\' self.create_linklist_tail(li) else: rais ValueError(\'unsupport\') #头插法 def create_linklist_head(self,li): self.head = Node(0) for v in li: n = Node(v) n.next = self.head.next #当插入下一个元素时，应该与下一个节点连接后再跟头节点连接 self.head.next = n self.head.data += 1 #尾插法 def create_linlist_tail(self,li): #不断更新尾巴 self.head = Node(0) self.tail = self.head for v in li: p = Node(v) self.tail.next = p self.tail = p self.head.data += 1 #链表的遍历输出 def traverse_linlist(self): p = self.head.next while p: yield p.data p = p.next 插入删除总结插入
#p表示待插入节点，curNode表示当前节点 p.next = curNode.next #不能当前连接直接断开 curNode,next = p删除
p = curNode.next curNode.next = p.next del p #不写也一样，引用计数，python的内存回收机制 双链表双链表中每个节点有两个指针：一个指向后面节点、一个指向前面节点。
节点定义：
插入
p.next = curNode.next curNode.next.prior = p p.prior = curNode curNode.next = p删除
p = curNode.next curNode.next = p.next p.next.prior = curNode del p 链表的复杂度分析链表与列表相比
按元素值查找：列表可以使用二分法是O(logn)，链表是O(n)
按下标查找：O(1),O(n)
再某元素后插入：O(n),O(1)
删除莫元素：O(n),O(1)
总的来说链表再插入和删除某元素的操作时明显快于顺序表，而且通过双链表可以更容易实现栈和队列。
哈希表就是直接寻址表的改进。当关键字的全域U比较小时，直接寻址是一种简单有效的方法。
全域的意思就是它的取值范围。
也就是直接把关键字为key的value放在key的位置上
直接寻址的缺点：
当域U很大时，需要消耗大量内存。
如果U很大，但关键字很少，浪费大量空间。
若关键字不是数字则无法处理。
直接寻址表的改进：
构建大小为m的寻址表T
key为k的元素放到h(k)上
h(k)是一个函数，其将域U映射到表T(0,1,..,m-1)
哈希表哈希表是一个通过哈希函数计算数据存储位置的线性表的存储结构，又叫做散列表。
哈希表由一个直接寻址表和一个哈希函数组成。
哈希函数h(k)将元素关键字k作为自变量，返回元素的存储下标。
哈希表的基本操作：
insert(key,value):插入键值对。
get(key):如果存在键为key的键值对则返回其value。
delete(key)：删除键为key的键值对。
简单哈希函数除法哈希：h(k)= k mod m