目录

前言：

1.队列的概念

2.队列的使用

3.队列的模拟实现

3.1采用单链表来实现队列

3.2采用双向链表来实现

4.循环队列

5.双端队列

6.用队列来实现栈

7.用栈来实现队列

结束语：

前言：

上一次小编与大家分享了栈的使用方法，这节中我们来学习一下队列，它又和栈有何区别，两者之间我们又有哪些可以相互转化呢？快来跟着小编一起来学习吧！！！

1.队列的概念

只允许在一端进行插入数据操作，在另一端进行数据删除操作的特殊线性表，队列具有先进先出的特性，入队列：进行插入操作的一端的称之为队尾（rear/tail），出队列：进行删除操作的一端称之为对头（head/front）。

2.队列的使用

在java中，Queue是一个接口，底层是通过链表实现的。

代码如下所示：

package 队列的使用;import java.util.LinkedList;
import java.util.Queue;public class Test {public static void main(String[] args) {Queue queue = new LinkedList<>();//入队列queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);queue.offer(6);//出队列System.out.println(queue.poll());//1System.out.println(queue.poll());//2//查看队首元素System.out.println(queue.peek());//3System.out.println(queue.peek());//3//计算队列的大小System.out.println(queue.size());//4//检测队列是否为空System.out.println(queue.isEmpty());//false}
}

结果如下所示：

3.队列的模拟实现

3.1采用单链表来实现队列

代码如下所示：

package 采用单链表来实现队列;public class MyQueue1 {class ListNode{public ListNode next;//下一个结点public int val;//结点的值public ListNode(int val) {this.val = val;}}ListNode first;ListNode last;int size = 0;//入队列public void offer(int x) {//创建一个结点ListNode node = new ListNode(x);//以尾插法进行入队if (first == null) {first = node;last = node;} else {last.next = node;last = node;}size++;}//出队列public int poll() {//判断队列是否为空if (first == null){return -1;}int value = first.val;ListNode cur = first;first = first.next;cur.next = null;size--;return value;}//查看队首元素public int peek() {//判断是否为空if (first == null) {return -1;}return first.val;}//计算大小public int size() {return size;}//判断队列是否为空public boolean isEmpty() {return first == null;}
}

测试类代码：
 

package 采用单链表来实现队列;public class Test {public static void main(String[] args) {MyQueue1 myQueue1 = new MyQueue1();//入队列myQueue1.offer(1);myQueue1.offer(2);myQueue1.offer(3);myQueue1.offer(4);myQueue1.offer(5);myQueue1.offer(6);//出队列System.out.println(myQueue1.poll());//1System.out.println(myQueue1.poll());//2System.out.println(myQueue1.poll());//3//查看队首元素System.out.println(myQueue1.peek());//4System.out.println(myQueue1.peek());//4//计算大小System.out.println(myQueue1.size());//3//判断是否为空System.out.println(myQueue1.isEmpty());//false}
}

结果如下所示：

3.2采用双向链表来实现

代码如下所示：

package 采用双向链表来实现队列;public class MyQueue {//内置类来定义一个双向链表class ListNode{ListNode next;//下一个结点ListNode prev;//前驱结点public int val;//结点的值public ListNode(int val) {this.val = val;}}ListNode first;//队首ListNode last;//队尾int size = 0;//入队列public void offer(int x) {//创建一个新的结点ListNode node  = new ListNode(x);//向队尾插入这个结点if (first == null) {first = node;//last = node;}else {last.next = node;node.prev = last;//last = node;}last = node;size++;}//出队列public int poll() {int value = 0;//出链表的头结点if (first == null) {return -1;} else if (first == last){value = first.val;first = null;last = null;} else {value = first.val;//保存一下头结点的值first = first.next;//将头结点指向移向下一个结点first.prev.next = null;//将现在头结点的前驱的next域置为空first.prev = null;//将现在头结点的前驱置为空}size--;return value;}//查看队首元素public int peek() {if (first == null) {return -1;}return first.val;}//计算队列中元素的个数public int size() {return size;}//判断队列是否为空public boolean isEmpty() {return first == null;}
}

测试类代码：
 

package 采用双向链表来实现队列;public class Test {public static void main(String[] args) {MyQueue myQueue = new MyQueue();//如队列myQueue.offer(1);myQueue.offer(2);myQueue.offer(3);myQueue.offer(4);myQueue.offer(5);myQueue.offer(6);//出队列System.out.println(myQueue.poll());//1System.out.println(myQueue.poll());//2System.out.println(myQueue.poll());//3//查看队首元素System.out.println(myQueue.peek());//4System.out.println(myQueue.peek());//4//计算队列元素的个数System.out.println(myQueue.size());//3//判断队列是否为空System.out.println(myQueue.isEmpty());//false}
}

结果如下所示：

4.循环队列

何为循环队列呢？下面我们直接用图来解释一下什么是循环队列。

我们一般会采用数组来实现它，那么在放到最后的一个位置的时候我们如果出了前面的元素，此时在我们看来这个循环队列是不满的，但是我们又应该怎么将队尾元素来循环的指向第一个元素呢？以及我们又是怎么来区分空间是否已经满了呢？

 一、解决怎么循环的问题

当出现下面的情况下我们发现队列中并没有满，那么我们应该怎么将rear从7下标移动到0下标呢？

其实我们只要在给rear赋值的时候赋值为：rear = （rear + 1）% length即可，同理如果是front也是一样的处理方式。  

二、怎么判断是否已经满了？

1. 通过添加size属性记录
2. 保留一个位置
3. 使用标记

下面我们就采用保留一个位置为例来实现一个循环的队列。

代码如下所示：

package 循环队列;class MyCircularQueue {public int[] elem;private int front;//表示队列的尾private int rear;//表示队列的尾public MyCircularQueue(int k) {this.elem = new int[k + 1];}//入队列public boolean enQueue(int value) {//1.检查队列是否为满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 front == rear;}public boolean isFull() {if ((rear + 1) % elem.length == front) {return true;}return false;}
}

结果如下所示：

5.双端队列

双端队里就是指允许两端都可以进行入队列和出队列操作的队列，deque是"double ended queue"的简称，那就说明元素可以从队列出队和入队，也可以从队尾出队和入队。

在实际开发过程中，使用deque接口是比较多的，栈和队列均可以使用该接口。

package 双端队列;import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;//两边都可以出和进
public class Test {public static void main(String[] args) {Deque deque = new LinkedList<>();Deque deque1 = new ArrayDeque<>();}
}

6.用队列来实现栈

代码如下所示：

package 队列来实现栈;import java.util.LinkedList;
import java.util.Queue;public class MyStack {public Queue queue1;public Queue queue2;public MyStack() {//初始化queue1 = new LinkedList<>();queue2 = new LinkedList<>();}//入栈public void push(int x) {if (!queue1.isEmpty()) {queue1.offer(x);} else if (!queue2.isEmpty()) {queue2.offer(x);}else {queue1.offer(x);}}//出栈public int pop(int x) {if (empty()) {return -1;//两个队列都为空}if (!queue1.isEmpty()) {int size = queue1.size();while (size > 1) {queue2.offer(queue1.poll());}return queue1.poll();}else {int size = queue2.size();while (size > 1) {queue1.offer(queue2.poll());}return queue2.poll();}}//查看栈首元素public int top() {if (empty()) {return -1;//两个队列都为空}if (!queue1.isEmpty()) {int val = -1;int size = queue1.size();for (int i = 0; i < size; i++) {val = queue1.poll();queue2.offer(val);}return val;}else {int val = -1;int size = queue2.size();for (int i = 0; i < size; i++) {val = queue2.poll();queue1.offer(val);}return val;}}//判断是否为空public boolean empty() {return queue1.isEmpty() && queue2.isEmpty();}
}

7.用栈来实现队列

package 栈实现队列;//用两个栈来实现队列
import java.util.Stack;public class MyQueue {private Stack stack1;private Stack stack2;public MyQueue() {stack1 = new Stack<>();stack2 = new Stack<>();}//入队列public void offer(int x) {stack1.push(x);}//出队列public int poll() {if (empty()) {return -1;}if (stack2.empty()) {while (!stack1.empty()) {stack2.push(stack1.pop());}}return stack2.pop();}//查看队列顶端元素public int peek() {if (empty()) {return -1;}if (stack2.empty()) {while (!stack1.empty()) {stack2.push(stack1.pop());}}return stack2.peek();}//看两个栈是否都为空public boolean empty() {return stack1.empty() && stack2.empty();}
}

结束语：

这节中小编主要与大家分享了队列的使用方法、循环队列、双端队列、用栈来实现队列以及用队列来实现栈。希望对大家有所帮助，想要学习的同学记得关注小编和小编一起学习吧！如果文章中有任何错误也欢迎各位大佬及时为小编指点迷津（在此小编先谢过各位大佬啦！）