1.概念
2. 方法使用
方法 | 功能 |
boolean offer(E e) | 入队列 |
E poll() | 出队列 |
peek() | 获取队头元素 |
int size() | 获取队列中有效元素个数 |
boolean isEmpty() | 检测队列是否为空 |
java">public static void main(String[] args) {Queue<Integer> q = new LinkedList<>();q.offer(1);q.offer(2);q.offer(3);q.offer(4);q.offer(5); // 从队尾入队列System.out.println(q.size());System.out.println(q.peek()); // 获取队头元素q.poll();System.out.println(q.poll()); // 从队头出队列,并将删除的元素返回if(q.isEmpty()){System.out.println("队列空");}else{System.out.println(q.size());}}
运行结果如下:
3.功能模拟实现(以int为例)
3.1 链式结构
Queue的链式结构的底层采用双向链表结构。
代码示例:
java">public class MyQueue {static class ListNode {public int val;public ListNode prev ;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode last;public int usedSize;//从队尾入队列public void offer(int val) {ListNode node = new ListNode(val);if(head == null) {head = last = node;}else {last.next = node;node.prev = last;last = last.next;}usedSize++;}//从队头出队列,并将删除的元素返回public int poll() {if(head == null) {return -1;}int ret = head.val;if(head.next == null) {head = null;last = null;}else {head = head.next;head.prev = null;}usedSize--;return ret;}//获得队头元素public int peek() {if(head == null) {return -1;}return head.val;}//获取队列容量public int size(){return usedSize;}//判断是否为空public boolean isEmpty() {return head == null;}
}
java">public static void main(String[] args) {MyQueue q = new MyQueue();q.offer(1);q.offer(2);q.offer(3);q.offer(4);q.offer(5); // 从队尾入队列System.out.println(q.size());System.out.println(q.peek()); // 获取队头元素q.poll();System.out.println(q.poll()); // 从队头出队列,并将删除的元素返回if(q.isEmpty()){System.out.println("队列空");}else{System.out.println(q.size());}}
运行结果如下:
3.2 顺序结构(以循环队列为例)
3.2.1 概念
队列的顺序结构,通常被称为顺序队列,是一种基于数组的队列实现方式。在这种结构中,队列的元素被存储在一段连续的存储空间(如数组)中,并通过两个指针(或索引)来跟踪队列的头部(front)和尾部(rear)。
在顺序队列中,如果队列的尾部已经到达数组的末尾,而头部还有空闲空间,此时再尝试入队就会导致“假溢出”问题。为了解决这个问题,可以采用循环队列或动态调整数组大小的方法。
3.2.2 循环队列
循环队列是顺序队列的一种特殊形式,它通过将数组的末尾和开头连接起来形成一个环状结构,从而有效地解决了“假溢出”问题。在循环队列中,当 rear 指针到达数组的末尾时,它会自动回绕到数组的开头。因此,在判断队列是否已满时,需要采用特殊的方法(如保留一个空闲位置或使用取模运算)来避免与队列为空的情况混淆。
3.2.2.1 数组下标循环
1. 下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length
2.下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length
3.2.2.2 区分空和满
3.2.2.3 功能实现
本文主要介绍区分空和满的第二种方法。
代码示例:
java"> public int[] elem;public int front;public int rear;public MyCircularQueue(int capacity) {elem = new int[capacity + 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 boolean isEmpty() {return front== rear;}// 判断队列是否为满public boolean isFull() {return (rear+ 1) % elem.length == front;}
测试代码:
java">public static void main(String[] args) {MyCircularQueue q = new MyCircularQueue(5);q.enQueue(1); // 从队尾入队列q.enQueue(2); // 从队尾入队列q.enQueue(3); // 从队尾入队列q.enQueue(4); // 从队尾入队列q.enQueue(5); // 从队尾入队列System.out.println(q.size());System.out.println(q.Front()); // 获取队头元素q.deQueue();System.out.println(q.deQueue()); // 从队头出队列,并将删除的元素返回if(q.isEmpty()){System.out.println("队列空");}else{System.out.println(q.size());}}
运行结果如下:
4. 双端队列 (Deque)
双端队列(deque)是指允许两端都可以进行入队和出队操作的队列,deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队,也可以从队尾出队和入队。
注意:Deque是一个接口,使用时必须创建对象。
java">Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现
Deque的使用与实现和Queue的差不多,我们就不在进行过多的介绍了。
本文是作者学习后的总结,如果有什么不恰当的地方,欢迎大佬指正!!!