乐观学习,乐观生活,才能不断前进啊!!!
我的主页:optimistic_chen
我的专栏:c语言 ,Java
欢迎大家访问~
创作不易,大佬们点赞鼓励下吧~
文章目录
- 前言
- 队列Queue
- 队列的模拟实现
- 环形队列
- 队列练习
- Deque双端队列
- 完结
前言
由图可知:Queue接口一定意义上和List接口“平级”
注意一个细节, LinkedList不仅属于List接口下的类,也属于Queue接口下的类 。根据上篇博客所说,链表与数组都可以模拟栈,而栈也是List接口下的类。
队列Queue
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表。
入队列(Enqueue):进行插入操作的一端称为队尾
出队列(Dequeue):进行删除操作的一端称为队头
队列具有先进先出的特性
大家可以简单理解为日常生活中“排队”这一现象。
队列的模拟实现
简单想一想,因为LinkedList实现了Queue接口,所以Queue的底层是由链表实现的。
受到LinkedList的影响,我们下意识认为Queue的底层是双向链表,那单链表能不能来实现队列呢?
那么以LinkedList来实现队列怎么样呢?
建立内部类
//内部类public static class ListNode {public ListNode prev;public ListNode next;int value;ListNode(int value){this.value=value;}}public ListNode first=null;public ListNode last=null;int Usedsize=0;
入队列—向双向链表位置插入新节点
public void offer(int val){ListNode node=new ListNode(val);if(first==null){first=last=node;}else{last.next=node;node.prev=last;}last=node;Usedsize++;}
出队列—将双向链表第一个节点删除掉
public int poll(){int val=0;if(first==null){return 0;}if(first==last){last=null;first=null;}else{val=first.value;first=first.next;first.prev.next=null;first.prev=null;}Usedsize--;return val;}
获取队头元素—获取链表中第一个节点的值域
public int peek(){if(first==null){return 0;}return first.value;}
环形队列
一般情况下,环形队列通常使用数组实现
画图介绍一下环形队列:
判断空:rear与front第一次相遇就为空
判断满:
- 定义一个有效大小usedsize,如果它和数组大小相同,那队列就满了
- 添加标记,定义一个标记符。rear与front相遇为false,添加一个元素改为true,当rear与front相遇且标记符为true时为满。
- 浪费一个空间,判断rear的下一个是不是front(rear+1=front)
最重要的一个问题,rear或者front下标怎么样从 7下标 到 0下标 ? 总不能去rear+1。。。
当rear下标为 7 时 :(rear+1)%len,(len为数组长度)。由此实现循环
队列练习
设计循环队列
class MyCircularQueue {public int front;public int rear;public int[] elem;public MyCircularQueue(int k) {elem=new int[k+1];}public boolean enQueue(int value) {if(isFull()){return false;}elem[rear]=value;rear=(rear+1) % elem.length;return true;}public boolean deQueue() {if(isEmpty()){return false;}front=(front+1)%elem.length;return true;}public int Front() {if(isEmpty()){return-1;}return elem[front];}public int Rear() {if(isEmpty()){return -1;}int index=(rear==0)?elem.length-1:rear-1;return elem[index];}public boolean isEmpty() {return rear==front;}public boolean isFull() {return (rear+1)%elem.length==front;}
}
Deque双端队列
双端队列(deque)是指允许两端都可以进行入队和出队操作的队列,deque 是 “double ended queue” 的简称。
那就说明元素可以从队头出队和入队,也可以从队尾出队和入队。
再看这张图:
Deque是一个接口,所以使用时必须创建LinkedList的对象。
public static void main(String[] args){//普通队列Deque<Integer> queue1=new LinkedList<>();//双端队列Queue<Integer> queue2=new LinkedList<>();//数组顺序的双端队列Queue<Integer> queue3=new ArrayDeque<>();
完结
好了,到这里Java语法部分就已经结束了~
如果这个系列博客对你有帮助的话,可以点一个免费的赞并收藏起来哟~
可以点点关注,避免找不到我~ ,我的主页:optimistic_chen
我们下期不见不散~~Java
下期预告: 【Java数据结构】- - -二叉树