您好，我是码农飞哥，感谢您阅读本文，欢迎一键三连哦。
这是Pyhon系列文章的第三篇，本文主要介绍用数组和链表实现单向队列。
干货满满，建议收藏，需要用到时常看看。 小伙伴们如有问题及需要，欢迎踊跃留言哦~ ~ ~。
线性表
前面我们学习了链表的相关知识，今天我们接着来学习另外一种数据结构-----》队列。其实，不管是数组还是链表，都是属于线性表，那么什么是线性表呢？线性表是具有相同数据类型的n（n>=0）个数据元素的有限序列。其中n为表长，当n=0时，该线性表是一个空表。若用 L 命名线性表，则其一般表示如下：
L = ( a1 , a2 , a3 , … , a(i) , a( i + 1) , … , a(n) ) 其中，a1 是唯一的 “ 第一个 ” 数据元素，又称为表头元素；a(n) 是唯一的 “ 最后一个 ” 数据元素， 又称为表尾元素。除了第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外 ，每个 元素 有且仅有一个直接后继。以上就是线性表的逻辑特性，这种线性表有序的逻辑结构正是线性表 名字的由来。
队列
队列，是一种操作受限，先进先出的的线性表数据结构，其只有入队enqueue和出队dequeue两个操作。我们可以用数组和链表来实现队列。用数组实现的是顺序队列，用链表实现的是链式队列。
数组实现队列的逻辑
队列有两个指针，分别是队头指针head和队尾指针tail。队头的指针指向队列的头部。例如：
我们定义一个大小为6的数组，然后，以及将 a,b,c,d 入队。那么过程变化图如下：
如上图，我们可以清楚的看出队列入队的话就是tail指针不断向后移动，知道tail等当前数组的长度，就表示队列已满，head指针保持不变。
代码实现如下：
public boolean enqueue(String item) {
//如果tail==n 表示队列已经满了
if (tail == n) {
return false;
}
//将要插入的元素放在tail 位置上
items[tail] = item;
++tail;
return true;
}
接下来，我们来看看队列的出队操作。出队的过程图如下所示：
如上图所示，我们可以清楚的看出队列的出队操作过程就是每出一个元素，head指针就向后移动一次，直到head等于tail 就表示队列为空。tail指针不变。
代码实现如下：
public String dequeue() {
//如果head==tail,表示队列为空
if (head == tail) {
return null;
}
String ret = items[head];
++head;
return ret;
}
每次进行出队操作都相当于删除数组下标为0的数据，要搬移这个队列中的数据，这样出队的操作的时间复杂度就会从原来的O(1)变成O(n)。
实际上，我们在出队时如果不用搬移数据，如果没有空闲空间了，我们只需要在入队是，在集中触发一次数据的搬移操作。借助这个思想，出队函数dequeue() 保持不变，我们稍加改造下入队函数
enqueue()。
public boolean enqueueNew(String item) {
//tail==n 表示队列末尾没有空间了
if (tail == n) {
//tail==n && head==0 表示整个队列都占满了
if (head == 0) {
return false;
}
//数据搬移
for (int i=head;i<tail;++i) {
items[i - head] = items[i];
}
//搬移完之后重新更新head和tail
tail -= head;
head = 0;
}
items[tail] = item;
++tail;
return true;
}
如上代码，当tail==n是表示队列末尾没有空间，此时,就可以进行数据的迁移，迁移的过程就是将位置为i的元素移动到 i-head上去搬移的操作如下图所示：
链表实现队列的逻辑
说完了通过数组实现的顺序队列，接下来我们来看看通过链表实现的链式队列。首先我们还是先定义好链表的数据结构
class Node {
/**
* 数据域
*/
String value;
/**
* 下一个结点对象的引用
*/
Node next;
public Node(String value, Node next) {
this.value = value;
this.next = next;
}
public Node(String value) {
this.value = value;
}
public Node(Node next) {
this.next = next;
}
}
入队和出队的操作示意图如下所示：
如上图，队列中有a,b,c,d四个节点，此时，head指针指向a节点，tail 指向d节点。当我们需要向队列中插入e节点时，我们只需要将tail指针指向e节点，即tail->next=e,tail=tail->next;
当a节点从队列中出队时，那么只需要将head指针指向后一个结点。即head=head->next。
所以：入队的实现代码是：
public void enqueue(String item) {
Node newNode = new Node(item);
//队列没有元素
if (tail == null) {
head = newNode;
tail = newNode;
} else {
tail.next = newNode;
tail = tail.next;
}
}
入队操作其实是尾插法，从队列的尾部插入元素。当tail为null时表示队列中没有元素，此时head指针和tail指针都指向新结点。否则，只需要调整tail指针的指向即可。
出队的实现代码是：
public Object dequeue() {
//队列为空
if (head == null) {
return null;
}
String value = head.value;
head = head.next;
//队列为空
if (head == null) {
tail = null;
}
return value;
}
当head为null时表示队列为空。否则，就调整head结点的位置。
总结
本文我们主要介绍了如何用数组和链表实现单向队列。队列是一种操作受限先进先出的的线性表数据结构，其只有入队和出队操作。可以通过数组和链表来实现队列
参考
https://time.geekbang.org/column/article/41330