队列
队列是一种运算受限的线性表，元素的添加操作在表的一端进行，而另一端的删除在另一端进行，允许插入的一端称为队尾，允许删除的一端称为队头。
假设队列 q = [x1,x2,x3,,,,,xn] x1是队头，x2是队尾，队列中的数据的入队序列是x1,x2,x3,,,xn,队列也只能按这个顺序进行出队，队列的特点是先进入队列的先出来，后进队的必须等前面的数据出队完成以后才可以出队，所以队列也成为先进先出表(First in First out)
队列的操作
队列由由多种实现方式，这里就选三个比较有代表性的实现方式讲解’基础队列,循环队列，链队列，代码放在后面，在讲解的途中就在分别展示了
说明：循环队列也是用数组来实现的，只不过通过，一些算法实现了数组空间的复用，而且不用频繁的移动数组中的元素。
初始化队列
入队
出队
原队列
出队
顺序队列：就是将第一个元素返回出去，其余的元素向前移动一单位
循环队列：就是将队头的指针向后移动一个单位，里面的元素变为无效数据，等待覆盖
链队列：就是链表的删除，将头部指针front，指向队头的的指针移动到，指向队头后一个元素
遍历队列
顺序队列：将数组中的中的数据从开头一直遍历到最后
循环队列：创建一个临时的指针tmp该指针的位置和front指针一样,根据这个临时指针tmp的移动一次访问元素，直至临时指针和rear指针指向同一个位置的时候停止。
链队列：从头部直接遍历，循环调用next方法，直至到next==null的时候停止遍历
清空队列
清空队列就是将队列中的所有元素清空，让队列回归最初的状态
顺序队列：清空列表中的元素，并将rear指针回归到最初的位置
循环队列：清空列表中的元素，并将指针回归到最初的位置
链队列：将头部指针指向为null
队列的存储结构
顺序存储
基础队列的队头始终在数组的头部，每删除一个元素，整个队列就会向前移动一个单位，保证队列头始终在数组的第一个元素。这样我门就可以发现每执行删除操作(出队)，队列就要移动一次，这样会造成系统的额外开销。
class BaseQueue: def __init__(self): self.data = [] self.front = 0 self.rear = 0 # 记录队尾 self.maxlength = 10 # 设置队列的最大长度 def enqueue(self, arg): """入队""" if self.rear >= self.maxlength: print("队列已满") return self.rear += 1 self.data.append(arg) def dequeue(self): """出队""" if self.rear == 0: print("队列已空") return self.rear -= 1 return self.data.pop(0) def gethead(self): """获取队头""" if self.rear == 0: print("队列已空") return return self.data[0] def size(self): """返回队列的长度""" return self.rear def isEmpty(self): """判断队列是否为空""" return self.rear == 0 def next(self): """遍历并输出""" p = self.rear for i in range(0, p): print(self.data[i]) def clear(self): """清空队列""" self.data.clear() self.rear = 0
循环队列
循环队列，本质上还是使用数组进行实现，只是在逻辑上将首部、尾部连接起来，形成一个环状的循环队列，循环队列存储的元素个数比数组的长度少一，用来区分队满还是对待队空。
class LoopQueue: def __init__(self): self.maxsize = 10 self.data = [0 for i in range(self.maxsize)] self.front = 0 self.rear = 0 def enqueue(self, arg): """入队""" if (self.rear + 1) % self.maxsize == self.front: print("队列已满，无法入队") return self.data[self.rear] = arg self.rear = (self.rear + 1) % self.maxsize def dequeue(self): """出队""" if self.isEmpty(): print("队列已空，无法读取元素") return tmp = self.data[self.front] self.front = self.front + 1 % self.maxsize return tmp def gethead(self): """获取队头""" if self.isEmpty(): print("队列已空，无法读取元素") return tmp = self.data[self.front] return tmp def size(self): """返回队列的长度""" if self.front <= self.rear: return self.rear - self.front else: return self.maxsize - (self.front - self.rear) def isEmpty(self): """判断队列是否为空""" return self.front == self.rear def next(self): """遍历并输出""" tmp = self.front while tmp < self.rear: print(self.data[tmp]) tmp += 1 def clear(self): """清空队列""" self.front = 0 self.rear = 0
链式存储
队列的链存储结构称为链队列，它是限制在表头删除和表尾插入的单链表，由于需要在表尾进行插入操作，所以为操作方便除头指针外有必要再增加一个指向尾节点的指针
这个部分用到的链表的知识比较多，如果有不理解的可以去补补链表的知识
class Node(object): """节点类""" def __init__(self, data=None): self.data = data self.next = None class LinkQueue: def __init__(self): self.length = 0 self.front = None # 头节点 self.rear = None # 尾节点 def enqueue(self, arg): """入队""" node = Node(data=arg) if self.isEmpty(): self.front = self.rear = node self.length += 1 else: self.rear.next = node self.rear = node self.length += 1 def dequeue(self): """出队""" if self.isEmpty(): print("队列为空") else: resulst = self.front.data self.front = self.front.next self.length-=1 return resulst def gethead(self): """获取队头""" if not self.isEmpty(): return self.front.data else: print("队列为空") def size(self): """返回队列的长度""" return self.length def isEmpty(self): """判断队列是否为空""" if self.length == 0: return True else: return False def next(self): """遍历并输出""" tmp = self.front while tmp: print(tmp.data) tmp = tmp.next def clear(self): """清空队列""" self.front = None self.rear = None
队列实战题目
这两个题目我们再刚开始讲解的时候已经写过了
总结
栈是限定再表尾进行插入或删除的线性表，又称后进先出的线性表，栈有两种存储表示，顺序栈，链式栈，链的主要操作是进栈和出栈，对于出栈和进栈操作判断栈满还是栈空
队列是一种先进先出的线性表，它只允许在表的一端进行插入，而在另一端进行删除，队列也有两种存储结构，顺序存储，链式存储，队列的主要操作是进队和出队，对于顺序表需要注意队满和队空的情况
栈和队列是在程序设计中被广泛使用的两种数据结构，其具体的应用场景都是与其展示方法和运算规则相互关联的。
