队列(Queue)的详解
队列:只允许在一端进行插入操作,在另一端进行删除数据操作的特殊的线性表,队列具有先进先出
1、入队列:进行插入操作的一端称为队尾(Tail/Rear)
出队列:进行删除操作的一端称为对头(Head/Front)
2、队列的使用
在Java中,Queue是个接口,底层是通过链表实现的
注:Queue是个接口,在实例化时必须实例化LinkedList的对象,因为LinkedList实现了Queue接口。
以下代码为Queue的代码演示
import java.util.LinkedList;
import java.util.Queue;
//Queue 的演示示例
public class Demo2 {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
System.out.println(queue.size());
System.out.println(queue);
System.out.println("===============================");
//出队
queue.poll();
System.out.println(queue.peek());
System.out.println(queue);
System.out.println("===============================");
// //删除,没有元素的时候会抛出异常
// System.out.println(queue.remove());
// System.out.println(queue);
// System.out.println(queue);
// //获取,没有元素的时候会抛出异常
// System.out.println(queue.element());
// System.out.println(queue);
}
public static void main1(String[] args) {
Queue<Integer> queue = new LinkedList<>();
//入队
queue.offer(1);
queue.offer(2);
queue.offer(3);
queue.offer(4);
queue.offer(5);
System.out.println(queue.size());
System.out.println(queue);
System.out.println("===============================");
//出队
queue.poll();
System.out.println(queue.peek());
System.out.println(queue);
System.out.println("===============================");
//删除
System.out.println(queue.remove());
System.out.println(queue);
System.out.println(queue.remove(5));
System.out.println(queue);
//获取
System.out.println(queue.element());
System.out.println(queue);
}
}
3、队列的模拟实现
//用双向链表实现
public class MyQueue {
private static class ListNode {
int val;
ListNode prev;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
private ListNode head;
private ListNode tail;
public int size;
public void offer (int e){
ListNode node = new ListNode(e);
if(head == null) {
head = node;
} else {
tail.next = node;
node.prev = tail;
}
tail = node;
size++;
}
public int poll (){
if(isEmpty()) {
throw new RuntimeException("队列为空");
}
int headValue = head.val;
head = head.next;
if(head == null) {
tail = null;
} else {
head.prev.next = null;
head.prev = null;
}
size--;
return headValue;
}
public int peek(){
if(isEmpty()) {
throw new RuntimeException("队列为空");
}
return head.val;
}
public int size (){
return -1;
}
public boolean isEmpty() {
return size == 0;
}
public void display(){
ListNode cur = head;
StringBuilder sb = new StringBuilder();
sb.append("[");
while(cur != null){
sb.append(cur.val);
if(cur.next != null){
sb.append(",");
}
cur = cur.next;
}
sb.append("]");
System.out.println(sb.toString());
}
}
4、循环队列
环形队列通常使用数组实现
注意:
底层还是一个数组,指定一个队列的大小,入队时,当队列满的时候就不能再放了,出队时当队列为空的时候就不能再出队了
加一个冗余位置,当rear = front + 1这时,可以判定队列已满
改变下标位置:(index + x)% array.length = 正确的下标
以下代码设计循环队列
class MyCircularQueue {
private int[] elementData;
private int front;
private int rear;
public MyCircularQueue(int k) {
this.elementData = new int[k + 1];
}
//入队
public boolean enQueue(int value) {
if(isFull()) {
return false;
}
elementData[rear] = value;
rear = (rear + 1) % elementData.length;
return true;
}
//出队
public boolean deQueue() {
if(isEmpty()) {
return false;
}
// int res = elementData[front];出队的值
front = (front + 1) % elementData.length;
return true;
}
//取队首元素
public int Front() {
if(isEmpty()) {
return -1;//在oj题不要抛异常,return-1即可
}
return elementData[front];
}
//取队尾元素
public int Rear() {
if(isEmpty()) {
return -1;
}
return elementData[(rear - 1 + elementData.length) % elementData.length];
}
public boolean isEmpty() {
return rear == front;
}
//判断是否已满
public boolean isFull() {
return (rear + 1) % elementData.length == front;
}
}
5、双端队列(Deque)
双端队列是指允许两端都可以进行入队和出队的操作的队列,Deque是一个接口,使用时必须创建LinkedList的对象
注意:栈,在Java中是用数组实现的,Stack继承自Vector,性质是后进先出 LIFO
队列,在Java中是用双向链表实现的,实现类是LinkedList,性质是先进先出 FIFO