队列数据抽象类型级实现

队列Queue：什么是队列？

• 队列是一种有次序的数据集合
  • 其特征是新数据项的添加总发生在一端（通常称为“尾rear”端）
  • 而现存数据项的移除总发生在另一端（通常称为“首front”端）
  • 当数据项加入队列， 首先出现在队尾， 随着队首数据项的移除， 它逐渐接近队首。
• 新加入的数据项必须在数据集末尾等待，而等待时间最长的数据项则是队首
• 这种次序安排的原则称为（ FIFO:First-infirst-out） 先进先出
  • 或“先到先服务first-come first-served”
• 队列的例子出现在我们日常生活的方方面面：排队
  • 队列仅有一个入口和一个出口
  • 不允许数据项直接插入队中，也不允许从中间移除数据项

抽象数据类型Queue

• 抽象数据类型Queue由如下操作定义：
  Queue() ：创建一个空队列对象，返回值为 Queue对象 ；
  enqueue(item) ：将数据项item添加到队尾， 无返回值 ；
  dequeue() ：从队首移除数据项，返回值为 队首数据项，队列被修改 ；
  isEmpty() ：测试是否空队列，返回值为 布尔值
  size() ：返回 队列中数据项的个数
  • 采 用 List 来 容 纳Queue的数据项
  • 将List首端作为队列 尾端
  • List的末端作为队列 首端
  • enqueue() 复杂度为O(n)
  • dequeue() 复杂度为O(1)
  • 首尾倒过来的实现，复杂度也倒过来