数据结构与算法系列七(队列)
小杨【0和1】 人气:01.引子
1.1.为什么要学习数据结构与算法?
有人说,数据结构与算法,计算机网络,与操作系统都一样,脱离日常开发,除了面试这辈子可能都用不到呀!
有人说,我是做业务开发的,只要熟练API,熟练框架,熟练各种中间件,写的代码不也能“飞”起来吗?
于是问题来了:为什么还要学习数据结构与算法呢?
#理由一: 面试的时候,千万不要被数据结构与算法拖了后腿 #理由二: 你真的愿意做一辈子CRUD Boy吗 #理由三: 不想写出开源框架,中间件的工程师,不是好厨子
1.2.如何系统化学习数据结构与算法?
我想好了,还是需要学习数据结构与算法。但是我有两个困惑:
1.如何着手学习呢?
2.有哪些内容要学习呢?
学习方法推荐:
#学习方法 1.从基础开始,系统化学习 2.多动手,每一种数据结构与算法,都自己用代码实现出来 3.思路更重要:理解实现思想,不要背代码 4.与日常开发结合,对应应用场景
学习内容推荐:
数据结构与算法内容比较多,我们本着实用原则,学习经典的、常用的数据结构、与常用算法
#学习内容: 1.数据结构的定义 2.算法的定义 3.复杂度分析 4.常用数据结构 数组、链表、栈、队列 散列表、二叉树、堆 跳表、图 5.常用算法 递归、排序、二分查找 搜索、哈希、贪心、分治 动态规划、字符串匹配
2.考考你
你还记得在数组那一篇中,我们说过基于线性表的数据结构有哪些吗?它们是:数组、链表、栈、队列。
上一篇【数据结构与算法系列六(栈)】中,我们已经详细了解了栈这种数据结构:栈是一种操作受限的数据结构。队列是基于线性表的数据结构中,最后一种了,很巧!它也是一种操作受限的数据结构。
队列同样可以基于数组实现:顺序队列;也可以基于链表实现:链式队列。
那么问题来了:具体如何实现一个队列呢?它都有哪些应用场景呢?
#考考你: 1.你能用自己的话描述队列吗? 2.你知道常见的队列分类吗? 3.你知道队列代码实现的关键吗? 4.你知道如何实现一个循环队列吗? 5.你知道队列的常见的应用场景吗?
3.案例
3.1.队列的定义
队列是一种基于线性表的数据结构,与栈一样,都是操作受限的数据结构。栈的特点是后进先出,而队列的特点是先进先出(FIFO),就像我们平常在火车站排队候车一样。
队列有两头:队头,和队尾。从队头出队元素,在队尾入队新的元素。
3.2.代码实现
顺序队列代码:
package com.anan.struct.linetable; /** * 顺序队列:基于数组实现 * @param <E> */ public class ArrayQueue<E> { private Object[] items; private int n; // 队列需要两个下标:对头下标索引、队尾下标索引 private int head; private int tail; public ArrayQueue(int capacity){ this.items = new Object[capacity]; this.n = capacity; } /** * 入队操作: */ public boolean enqueue(E e){ // 检查队列是否满 // 队列满条件 tail==n && head == 0 if(tail == n){ // 检查对头是否没有出队 if(head == 0){ return false; } // 如果已经有元素出队,则向对头移动数据 for (int i = head; i < tail ; i++) { items[i - head] = items[i]; } tail = tail - head; head = 0; } // 入队 items[tail] = e; tail ++; return true; } /** * 出队操作: */ public E dequeue(){ // 检查队列是否空 // 队列空条件:head == tail if(head == tail){ return null; } // 出队 E e = (E)items[head]; head ++; return e; } }
测试代码:
package com.anan.struct.linetable; /** * 测试队列 */ public class ArrayQueueTest { public static void main(String[] args) { // 1.创建队列 int capacity = 10; ArrayQueue<Integer> queue = new ArrayQueue<Integer>(capacity); System.out.println("1.创建队列---------队列容量:" + capacity); // 2.入队操作 System.out.println("2.入队操作---------"); int count = 5; for (int i = 0; i < count; i++) { queue.enqueue(i); System.out.println("入队元素:" + i); } // 3.出队操作 System.out.println("3.出队操作---------"); for (int i = 0; i < count; i++) { System.out.println("出队元素:" + queue.dequeue()); } } }
测试结果:
D:\02teach\01soft\jdk8\bin\java com.anan.struct.linetable.ArrayQueueTest 1.创建队列---------队列容量:10 2.入队操作--------- 入队元素:0 入队元素:1 入队元素:2 入队元素:3 入队元素:4 3.出队操作--------- 出队元素:0 出队元素:1 出队元素:2 出队元素:3 出队元素:4 Process finished with exit code 0
3.3.循环队列代码实现
package com.anan.struct.linetable; /** * 循环队列 */ public class CircularQueue<E> { private Object[] items; private int n; // 队头、对尾指针 private int head; private int tail; public CircularQueue(int capacity){ items = new Object[capacity]; n = capacity; } /** * 入队操作 */ public boolean enqueue(E e){ // 判断队列是否满 // 队列满条件:(tail + 1) % n == head if((tail + 1) % n == head){ return false; } items[tail] = e; tail = (tail + 1) % n; return true; } /** * 出队操作 */ public E dequeue(){ // 判断队列是否空 // 队列空条件:tail == head if(tail == head){ return null; } E e = (E)items[head]; head = (head + 1) % n; return e; } }
4.讨论分享
#考考你答案: 1.你能用自己的话描述队列吗? 1.1.队列是基于线性表的数据结构 1.2.队列是一种操作受限的数据结构 1.3.队列满足先进先出(FIFO)的特点 1.4.队列在队头出队元素,在队尾入队元素 2.你知道常见的队列分类吗? 2.1.从底层数据结构分类有:顺序队列、链式队列 2.2.从实现特点分类有:循环队列、阻塞队列、并发队列 3.你知道队列代码实现的关键吗? 3.1.队列满足先进先出(FIFO)特点 3.2.队列在队头出队元素,在队尾入队元素 3.3.实现队列的关键: a.需要两个指针:head、tail分别指向队头和队尾 b.入队时,判断队列满条件:tail == n && head == 0 c.出队时,判断队列空条件:tail == head 4.你知道如何实现一个循环队列吗? 4.1.在案例中,基于数组实现了一个普通的队列 4.2.入队操作的时候,如果队列满,需要移动数据 // 如果队列满,且已经有元素出队,则向对头移动数据 for (int i = head; i < tail ; i++) { items[i - head] = items[i]; } 4.3.这样会将入队操作,时间复杂度从O(1),转变成O(n),执行效率下降 4.4.有没有更好的方式,保持入队操作的时间复杂度为O(1)不变呢? 4.5.答案是:通过循环队列来实现 4.6.关于循环队列的代码,你可以参考【3.3】循环队列实现 4.7.重点关注队列满的条件:(tail + 1) % n == head 4.8.看你是否能理解,欢迎留言我们一起讨论 5.你知道队列的常见的应用场景吗? 5.1.队列主要针对有限资源控制的应用场景 5.2.比如数据库连接池的应用 5.3.比如线程池的应用 5.4.如果你有兴趣,可以看一下JUC中线程池的底层实现 5.5.JUC线程池的底层,应用了:阻塞队列 5.6.通过队列还能实现:生产者---消费者模型
JUC创建线程池:
加载全部内容