重学数据结构（三、队列）
1、队列的定义和特点
和上一篇的栈相反，队列(queue)是一种先进先出(First In First Out, FIFO)的线性表。
它只允许在表的一端进行插入，而在另一端删除元素。这和日常生活中的排队是一致的，最早进入队列的元素最早离开。
在队列中，允许插入的一端称为队尾(rear), 允许 删除的一端则称为队头(front)。出队列和入队列示意图如下：
2、队列的基本操作
队列的基本运算和堆栈类似，包含判空、获取长度、入队、出队、出队、取队头（不删除队头）等。
我们这里定义一个队列的接口。
/**
* @Author 三分恶
* @Date 2020/8/27
* @Description 队列
*/
public interface Queue { public boolean isEmpty(); //判空 public int size(); //获取队列容量 public void enQueue(Object element); //入队 public Object deQueue(); //出队 public Object getHead(); //取队首元素
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
队列是一种受限的线性表，同样有顺序和链式两种实现。
3、顺序队列
这里顺序队列通过可扩容数组来实现。
在类里标记了队头和对尾的下标。
入队时，队尾往后移动，队头保持不变，出队是队头往后移动，队尾保持不变。
为什么不保持队头指向0？因为如果队首指向0，那么出队的时候需要将数组前移，时间复杂度为O(n)。使用了队头和队尾标记之后，出队时队头往后移动一位，这样避免了元素的移动。
/**
* @Author 三分恶
* @Date 2020/8/27
* @Description 顺序队列
*/
public class ArrayQueue implements Queue{ private static int defaultSize=15; //默认容量 private int size; //实际容量：实际存储元素个数 private Object[] data; //存放元素的数组 private int front=0; //队头（下标） private int rear=0; //队尾（下标） /** * 无参构造方法：按默认容量构造元素数组 */ public ArrayQueue(){ data=new Object[defaultSize]; } /** * 有参构造方法：指定元素数组容量 * @param capacity */ public ArrayQueue(int capacity){ data=new Object[capacity]; } /** * 判空 * @return */ public boolean isEmpty() { return size==0; } /** * 获取队列元素个数 * @return */ public int size() { return size; } /** * 入队 * @param element */ public void enQueue(Object element) { //如果队满 if (size==data.length&&front==0){ //真队满，扩容 if (front==0){ //扩容两倍的新数组 Object [] newData=new Object[size<<1]; //拷贝数组 System.arraycopy(data,0,newData,0,size); data=newData; }else{ //假队满：前移元素 //所有数据前移front位 for (int i=front;i<size;i++){ data[i-front] = data[i]; } //队尾前移front位 rear-=front; //队头指向0 front=0; } } //队尾插入元素 data[rear]=element; rear++; size++; } /** * 出队 * @return */ public Object deQueue() { if (isEmpty()){ throw new RuntimeException("队空"); } //取队头元素 Object f=data[front]; //队头数组元素指向null，帮助gc data[front]=null; //队首指向下一元素 front++; //元素个数减1 size--; //返回队首元素 return f; } /** * 取队首元素（不删除队首元素） * @return */ public Object getHead() { if (isEmpty()){ throw new RuntimeException("队空"); } return data[front]; }
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
时间复杂度分析：
- 入队：平均O(1)，最坏情况（扩容）O(n)
- 出队：O(1)
- 取队首：O(1)
3、链式队列
这里使用单向链表来实现链式队列。
入队是将队尾指向插入的新元素，出队是将队头指向队头的下一个元素。
/**
* @Author 三分恶
* @Date 2020/8/27
* @Description
*/
public class LinkedQueue implements Queue{ /** * 节点类 * @param <T> */ class Node<T>{ private Object data; //数据 private Node next; //下一节点 Node(Object it, Node nextVal){ this.data=it; this.next=nextVal; } } private Node front; //队头 private Node rear; //队尾 private int size; //队列元素个数 /** * 判空 * @return */ public boolean isEmpty() { return size==0; } public int size() { return size; } /** * 入栈 * @param element */ public void enQueue(Object element) { Node node=new Node(element,null); //如果队列为空 if (rear==null){ rear=node; front=node; }else{ rear.next=node; } size++; } /** * 出队 * @return */ public Object deQueue() { //队列为空 if (front==null){ throw new RuntimeException("队列为空"); } //队头 Node node=front; front=front.next; size--; return node.data; } /** * 取队头元素 */ public Object getHead() { //队列为空 if (front==null){ throw new RuntimeException("队列为空"); } return front.data; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
时间复杂度分析：
- 入队：O(1)
- 出队：O(1)
- 取队首：O(1)
除此之外，顺序队列有变种循环队列，当rear到达数组的最大下标时，重新指回数组下标为0的位置;
链式队列有双端队列，队头、队尾都可以进行入队、出队操作的队列，可以通过双向链表实现；
4、java中的队列
java中有一个队列接口java.util.Queue，定义了队列的一些方法。
它有一个子接口，java.util.Deque，定义了双端队列的方法。
LinkedList实现了java.util.Deque接口，所以LinkedList能作为队列也能作为双端队列使用。详见LinkedList源码阅读笔记。
源码地址：https://gitee.com/LaughterYoung/data-structure-learn.git
上一篇：重学数据结构（二、栈）
下一篇：重学数据结构（四、数组和广义表）
本文为学习笔记类博客，主要资料来源如下！
参考：
【1】：邓俊辉 编著. 《数据结构与算法》
【2】：王世民 等编著 . 《数据结构与算法分析》
【3】： Michael T. Goodrich 等编著.《Data-Structures-and-Algorithms-in-Java-6th-Edition》
【4】：严蔚敏、吴伟民 编著 . 《数据结构》
【5】：程杰 编著 . 《大话数据结构》
【6】：看完这篇你还不知道这些队列，我这些图白作了
文章来源: blog.csdn.net，作者：三分恶，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/sinat_40770656/article/details/108267849
- 点赞
- 收藏
- 关注作者
评论（0）