一文搞懂队列 _队列

概念队列（queue）是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。
和栈一样，队列是一种操作受限制的线性表。队列是先进先出（FIFO）的。进行插入操作的端称为队尾，进行删除操作的端称为队头。
队列和栈非常相似，栈有入栈和出栈两个基本操作操作，队列也有两个基本操作：入队（enqueue），把数据放到队尾。出队（dequeue）,从队头取出一个数据。
【一文搞懂队列】队列出队和入队的时间复杂度都是O(1) 。
顺序队列用数组实现的队列叫做顺序队列。
// 用数组实现的队列public class ArrayQueue {// 数组：arr ，数组大小：lenprivate String[] arr;private int len = 0;// front 队头下标， rear 队尾下标private int front = 0;private int rear = 0;// 创建一个数组public ArrayQueue(int length) {items = new String[length];n = length;}// 入队public boolean enqueue(String item) {// 队列已满if (rear == len) return false;items[rear] = item;rear++;return true;}// 出队public String dequeue() {// 队列为空if (front == rear) return null;String result = items[front];front++;return result;}}队列有两个指针一个是front指向队头，一个是rear指向队尾。
如a、b、c、d、e 入列后，队头指针指向是的下标为0的位置，队尾指针指向的是下标为6的位置。

文章插图

然后不断进行出列和入列的操作，两个指针也不断往后移动，当队尾指针到达最右边的位置，就算数组中还有一个空闲的空间，但也没有办法继续向队列中加数据了。
回想数组空间不足，进行扩容，迁移数据的操作。
同理在这里也要对队列进行数据搬迁，只要在入列的时候判断一下（rear == len ）队列尾是已经到最后的话就进行数据迁移，然后重新计算两个指针的指向，然后再入列就可以了。

文章插图

链式队列用链表实现的队列叫做链式队列。同样需要两个指针，队头指向第一个节点，队尾指向最后一个节点。
入队：rear -> next = newnode , rear = rear -> next
出队：front = front-> next
循环队列用数组实现队列的时候，如果 rear == len ，就需要进行数据迁移操作。
为了避免进行数据迁移操作，可以用循环队列来解决。
循环队列首尾相接。
队空条件：front == rear
队满条件：(rear + 1) % len = front
确定好上面的两个条件，代码实现就很容易了。