队列的相关概念

队列（ queue ）种线性数据结构，遵循“ 先进先出 ”的原则。我们可以将其想象成排队买票，先来的人先买到票。

与栈结构不同的是，队列是双端开口。类似一个管道，只能从一端进入，从另一端离开。

队列的两个基本操作： 入队 将一个数据放到队列尾部； 出队 从队列的头部取出一个元素。

下面我们通过之前封装好的数组实现“ 队列 “

//定义一个Queue接口
public interface Queue<E> {
 void enqueue(E e);
 E dequeue();
 E getFront();
 int getSize();
 boolean isEmpty();
}
//定义一个ArrayQueue类实现Queue接口
public class ArrayQueue<E> implements Queue<E> {
//默认数组
 private Array<E> array;
//初始化容量的 构造函数 
 public ArrayQueue(int capacity){
 array = new Array<>(capacity);
 }
//无参构造函数，默认容量为10
 public ArrayQueue(){
 array = new Array<>();
 }
//入队
 @Override
 public void enqueue(E e) {
 //往数组中添加元素（通过数组模拟队列，我们将数组从左往右看，数组左边是队首，数组右边是队尾。）
 array.addLast(e);
 }
//出队
 @Override
 public E dequeue() {
 //删除并返回数组下标为0的元素，然后将其余元素左移。
 return array.removeFirst();
 }
//查看队首元素
 @Override
 public E getFront() {
 //获取数组下标为0的元素
 return array.get(0);
 }
//获取队列长度
 @Override
 public int getSize() {
 //返回数组长度
 return array.getSize();
 }
//判断队列是否是空队列
 @Override
 public boolean  isEmpty () {
 //数组是否为空
 return array.isEmpty();
 }

 @Override
 public String toString() {
 StringBuilder sb = new StringBuilder();
 sb. append ("queue:");
 sb.append("front[");
 for(int i = 0;i < array.getSize(); i++){
 sb.append(array.get(i));
 if(i!=array.getSize()-1){
 sb.append(",");
 }
 }
 sb.append("]end");
 return sb.toString();
 }
}
 

我们可以发现这种实现方式入队操作均摊复杂度是O(1) (触发扩容时是O(n)) , 而出队操作是O(n)，原因是出队时需要移除数组第一个元素并将其他元素整体往左移动一位。

下一篇我们通过实现一个循环队列来解决出队操作性能低下的问题

———本文源于日常学习笔记记录，如有错误欢迎批评指正