基本概念:
队列是一种只允许在表的一端进行插入操作,而在另一端进行删除操作的线性表,先进先出(FIFO);
允许删除的一端称为队列的头,允许插入的一端称为队列的尾;
队列的顺序表示存在假性溢出的问题,为了避免假性溢出,可以考虑环形队列;
数据不变式
备注:Python list(列表)
列表中的数据项不需要具有相同的类型,使用下标索引访问列表的值
'''
a[1]
a[1:5]
list.append():在队列末尾添加新的对象
'''
广度优先搜索:用队列实现
深度优先搜索:用栈实现
双端队列和双栈
双端队列是一种特殊的线性表,对它所有的插入和删除都限制在表的两端进行;
双栈是一种加限制的双端队列,它规定从end1插入的元素只能从end1端删除;从end2端插入的元素只能从end2端删除;
超队列:一种输出受限的双端队列,删除限制在一端进行,而插入仍允许在两端进行;(特殊的队列,允许先最新插入的元素最先删除)
超栈:一种输入受限的双端队列,插入在一端进行,而删除在两端进行;(可以看做是对栈溢出的一种特殊处理,当栈溢出时,可将栈中保存最久的元素删除;)
end