数据结构-队列

1.队列

1.1什么是队列

只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表称为队列，队列遵循先进先出FIFO（First In First Out）的原则。

入队列：进行插入操作时的一段称为队尾

出队列：进行删除操作时的一段称为队头

在Java中队列时一种重要的数据结构，队列在多线程，任务调度，消息传递等场景中有着广泛的应用。

1.2队列的常用方法

在Java中，Queue是一个接口，可以通过LinkedList，ArrayDeque，PriorityQueue来实现。

Queue的常用方法如下表所示：

方法	解释
boolean offer(E,e)	将元素插入进队列
E poll()	将元素从队列中删除
E peek()	获取队头元素
int size()	获取队列中有效元素的个数
boolean isEmpty()	判断队列是否为空

代码演示：

public class Test {public static void main(String[] args) {//LinkedList实现Queue接口Queue<String> queue=new LinkedList<>();//PriorityQueue实现Queue接口Queue<String> queue1=new PriorityQueue<>();//ArrayDeque实现Queue接口Queue<String> queue2=new ArrayDeque<>();//将元素插入进队列queue.offer("my");queue.offer("name");queue.offer("is");queue.offer("hajimi");//计算队列中有效元素个数System.out.println(queue.size());//获取队头元素System.out.println(queue.peek());//计算队列中有效元素个数-->4System.out.println(queue.size());//将元素从队列中删除System.out.println("删除的元素:"+queue.poll());//计算队列中有效元素个数-->3System.out.println(queue.size());//判断队列是否为空System.out.println(queue.isEmpty());}
}

2.Queue

2.1什么是Queue

Queue是Java中一个非常重要的接口，用于实现队列数据结构。Queue接口本身并不制定底层实现的具体方式，而是由具体的实现类来决定的。Java标准库中提供了多种Queue的实现类，如LinkedList（基于双向链表实现的类），ArrayDeque（基于动态数组实现的双端队列），PriorityQueue（基于优先级堆的无界队列）

2.2 实现一个Queue

队列中既然可以存储元素，那么底层就肯定要有能够保存元素的空间，我们采用链式结构来实现队列。

package datastructure;public class MyQueue {public static class ListNode{ListNode next;ListNode prev;int value;public ListNode(int value){this.value=value;}}//用于记录队头private ListNode first;//用于记录队尾private ListNode last;//用于记录队列中有效元素的个数private int size;//入队列--将元素插入队列中public void offer(int val){ListNode newNode=new ListNode(val);if(first==null){first=newNode;last=newNode;}else {last.next=newNode;newNode.prev=last;last=newNode;}size++;}//出队列，将元素从队列中删除public int poll(){int value=0;//判断队列是否为空//如果队列中只有一个元素---链表中只有一个节点---直接进行删除//如果队列中有多个元素---链表中有多个节点---将第一个节点删掉if(first==null){System.out.println("队列中没有元素，无法进行删除操作");return Integer.MAX_VALUE;}else if(first==last){first=null;last=null;}else {value=first.value;first=first.next;first.prev.next=null;first.prev=null;}size--;return value;}//获取队头元素public int peek(){//判断队列是否为空if(first==null){System.out.println("队列中没有元素，无法获取头部元素");return Integer.MAX_VALUE;}return first.value;}//计算队列中有效元素的个数public int size(){return size;}//判断队列是否为空public boolean isEmpty(){return first==null;}
}

对我们设计的Queue实现类进行运行测试：

public class Test {public static void main(String[] args) {MyQueue myQueue=new MyQueue();myQueue.offer(1);myQueue.offer(2);myQueue.offer(3);System.out.println("获取队头元素:"+myQueue.peek());System.out.println("队列的长度:"+myQueue.size());System.out.println("出队列:"+myQueue.poll());System.out.println("队列的长度:"+myQueue.size());System.out.println("获取队头元素:"+myQueue.peek());System.out.println(myQueue.isEmpty());}
}

运行结果：

3.循环队列

3.1什么是循环队列

循环队列是一种特殊结构的队列实现，它将数组的头尾相连来解决传统数组队列中“假溢出”的问题。在循环队列中，当队尾指针到达数组的末尾时，会自动循环到数组的头部，而从充分利用数组的空间。

循环队列是基于数组实现的

数组下标循环的技巧：

1.下标最后再往后（offset(表示后移的步数)小于array.length）：

index=(index+offset)%array.length

2.下标最前再往前（offset小于array.length）：

index=(index+array.length-offset)%array.length

3.2循环队列如何区分空和满

1.通过添加size属性记录循环队列中有效元素的个数，如果size==array.length，表示队列已满，如果size==0，表示队列为空

2.通过保留一个位置（浪费一个空间）来判断是否为满，如下图所示：

3.3实现一个循环队列

实现循环队列的思路：

通过数组来存储元素，并利用两个指针（front和rear）分别标记队列的头部和尾部，当队列出元素时，front后移，当队列入元素时，rear后移，还要不断判别队列为空或为满的情况。

代码实现：

package datastructure;
//采用浪费一个空间的做法实现循环队列
public class CircularQueue {private int[] elem;private int front;private int rear;//创建一个大小为k+1，实际上有效元素个数最多为k的数组public CircularQueue(int k){elem=new int[k+1];}//判断队列是否已满private boolean isFull(){return (rear+1)% elem.length==front;}//判断队列是否为空public boolean isEmpty(){return front==rear;}//入队列方法public boolean enQueue(int value){if(isFull()){System.out.println("队列已满，无法添加新的元素");return false;}elem[rear]=value;rear=(rear+1)%elem.length;return true;}//获取队头元素public int getFront(){if(isEmpty()){System.out.println("队列为空，无法获取队头元素");return Integer.MAX_VALUE;}return elem[front];}//出队列方法public int deQueue(){if(isEmpty()){System.out.println("队列为空，无法从队列中删除元素");return Integer.MAX_VALUE;}int value=elem[front];front=(front+1)%elem.length;return value;}//获取队尾元素public int getRear(){if(isEmpty()){System.out.println("队列为空，无法获取队尾元素");return Integer.MAX_VALUE;}//当rear=0，rear-1=-1无法表示数组中的元素，应为elem.length-1int index=(rear==0)?elem.length-1:rear-1;return elem[index];}
}

运行测试上述代码：

public class Test {public static void main(String[] args) {CircularQueue cQueue=new CircularQueue(3);System.out.println(cQueue.isEmpty());cQueue.enQueue(1);cQueue.enQueue(2);cQueue.enQueue(3);cQueue.enQueue(4);System.out.println(cQueue.isEmpty());System.out.println("从队列中删除元素:"+cQueue.deQueue());System.out.println("获取队列头部元素"+cQueue.getFront());System.out.println("获取队列尾部元素"+cQueue.getRear());}
}

结果：

4.Deque

Deque时允许两端都可以进行入队和出队操作的双端队列，deque是double ended queue的简称，表示元素可以从对头出和队尾，也可以从队头入和队尾入

Deque是一个接口，使用时必须创建LinkedList的对象

5.用队列实现栈

队列遵循先入先出FIFO，而栈遵循后入先出LIFO，所以一个普通的队列是无法实现栈的功能的。一个不行，不妨试试两个队列（Queue1，Queue2）。

1.当两个队列都为空时，表示栈为空

2.当元素入栈时，将元素放入不为空的队列中，当元素出栈时，将不为空的队列中的元素出队列，只剩下一个元素，剩下的元素就是要出栈的元素

代码实现：

package datastructure;import java.util.LinkedList;
import java.util.Queue;public class QueueToStack2 {private Queue<Integer> queue1;private Queue<Integer> queue2;public QueueToStack2(){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(){if(isEmpty()){System.out.println("栈中没有元素，无法进行出栈操作");return Integer.MAX_VALUE;}int deleteElem=0;if(!queue1.isEmpty()){int n=queue1.size();for(int i=0;i<n-1;i++){int value=queue1.poll();queue2.offer(value);}deleteElem=queue1.poll();return deleteElem;}if(!queue2.isEmpty()){int n=queue2.size();for(int i=0;i<n-1;i++){int value=queue2.poll();queue1.offer(value);}deleteElem=queue2.poll();return deleteElem;}return Integer.MAX_VALUE;}//判断栈是否为空public boolean isEmpty(){//当两个队列都为空时，表示栈为空return queue1.isEmpty()&&queue2.isEmpty();}//获取栈顶元素public int peek(){if(isEmpty()){System.out.println("栈中没有元素，无法获取栈顶元素");return Integer.MAX_VALUE;}int value=0;if(!queue1.isEmpty()){int n=queue1.size();for(int i=0;i<n;i++){value=queue1.poll();queue2.offer(value);}return value;}if(!queue2.isEmpty()){int n=queue2.size();for(int i=0;i<n;i++){value=queue2.poll();queue1.offer(value);}return value;}return Integer.MAX_VALUE;}
}

运行测试：

public class Test {public static void main(String[] args) {QueueToStack2 stack2=new QueueToStack2();stack2.push(1);stack2.push(2);stack2.push(3);System.out.println(stack2.pop());System.out.println(stack2.peek());System.out.println(stack2.pop());System.out.println(stack2.pop());System.out.println(stack2.pop());}
}

运行结果：

6.用栈实现队列

栈遵循后入先出LIFO，而队列遵循先入先出FIFO，所以单纯使用一个栈无法实现队列的效果，我们可以通过两个栈（stack1，stack2）来实现队列的效果

1.当两个栈都为空时，表示队列为空

2.入队时将所有元素放入栈stack1中

3.出队列时将stack1中的所有元素依次出栈放入stack2中，然后出stack2中的元素即为出队列操作

代码实现：

package datastructure;import java.util.Stack;public class StackToQueue2 {//扮演队列入队private Stack<Integer> stack1;//扮演队列出队private Stack<Integer> stack2;public StackToQueue2(){stack1=new Stack<>();stack2=new Stack<>();}//入队列操作public void push(int x){stack1.push(x);}//出队列操作public int pop(){if(empty()){System.out.println("队列中没有元素，无法实现出队列操作");return Integer.MAX_VALUE;}if(stack2.empty()){while (!stack1.empty()){stack2.push(stack1.pop());}}return stack2.pop();}//获取队头元素public int peek(){if(empty()){System.out.println("队列中没有元素，无法获取队头元素");return Integer.MAX_VALUE;}if(stack2.empty()){while (!stack1.empty()){stack2.push(stack1.pop());}}return stack2.peek();}//判断队列是否为空public boolean empty(){return stack1.empty()&&stack2.empty();}
}

运行测试：

public class Test {public static void main(String[] args) {StackToQueue2 queue2=new StackToQueue2();queue2.push(1);queue2.push(2);queue2.push(3);queue2.push(4);queue2.push(5);System.out.println(queue2.peek());System.out.println(queue2.pop());System.out.println(queue2.pop());System.out.println(queue2.pop());System.out.println(queue2.pop());System.out.println(queue2.pop());System.out.println(queue2.empty());}
}

运行结果：