乐观学习，乐观生活，才能不断前进啊！！！

我的主页：optimistic_chen

我的专栏：c语言 ，Java

欢迎大家访问~

创作不易，大佬们点赞鼓励下吧~

文章目录

前言队列Queue队列的模拟实现环形队列队列练习Deque双端队列完结

前言

由图可知：Queue接口一定意义上和List接口“平级”

注意一个细节， LinkedList不仅属于List接口下的类，也属于Queue接口下的类 。根据上篇博客所说，链表与数组都可以模拟栈，而栈也是List接口下的类。

队列Queue

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。

入队列(Enqueue)：进行插入操作的一端称为队尾

出队列(Dequeue)：进行删除操作的一端称为队头

队列具有先进先出的特性

大家可以简单理解为日常生活中“排队”这一现象。

队列的模拟实现

简单想一想，因为LinkedList实现了Queue接口，所以Queue的底层是由链表实现的。

受到LinkedList的影响，我们下意识认为Queue的底层是双向链表，那单链表能不能来实现队列呢？

那么以LinkedList来实现队列怎么样呢？

建立内部类

<code>//内部类

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;

}

获取队头元素—获取链表中第一个节点的值域

<code>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为数组长度)。由此实现循环

队列练习

设计循环队列

<code>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的对象。

<code>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数据结构】- - -二叉树