【Java 数据结构】队列的实现及相关OJ题
🎉🎉🎉点进来你就是我的人了
博主主页：🙈🙈🙈戳一戳,欢迎大佬指点!
人生格言：当你的才华撑不起你的野心的时候,你就应该静下心来学习!欢迎志同道合的朋友一起加油喔🦾🦾🦾
目标梦想：进大厂，立志成为一个牛掰的Java程序猿，虽然现在还是一个🐒嘿嘿
谢谢你这么帅气美丽还给我点赞！比个心
目录
一、队列的基本概念
1.什么是队列
2.普通队列和双端队列
3.关于队列一些操作的实现
4. 单向链表实现队列
5. 双向链表实现队列
6.循环队列
二、队列相关OJ题
1.设计循环队列
2. 用栈实现队列编辑
3. 用队列实现栈
一、队列的基本概念
1.什么是队列
只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的特点：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front）
2.普通队列和双端队列
3.关于队列一些操作的实现
①普通队列
Queue(一般多使用返回特殊值的处理，更加方便）
| 错误处理 | 抛出异常 | 返回特殊值 |
| 入队列 | add(e) | offer(e) |
| 出队列 | remove() | poll() |
| 队首元素 | element() | peak(） |
方法简单演示:
public class Test {public static void main(String[] args) {Queue<Integer> queue = new LinkedList<>();queue.offer(1);queue.offer(2);System.out.println("该队列队头元素为：");System.out.println(queue.peek());System.out.println("出队元素为");System.out.println(queue.poll());}
}②双端队列
Deque(一般多使用返回特殊值的处理，更加方便）
| 头部/尾部 | 头部元素(队首) | 尾部元素(队尾) | ||
| 错误处理 | 抛出异常 | 返回特殊值 | 抛出异常 | 返回特殊值 |
| 入队列 | addFirst(e) | offerFirst(e) | addLast(e) | offerLast(e) |
| 出队列 | removeFirst() | pollFirst() | removeLast() | pollLast() |
| 获取元素 | getFirst() | peekFirst() | getLast() | peekLast() |
方法简单演示:
import java.util.*;public class Test {public static void main(String[] args) {Deque<Integer> queue = new LinkedList<>();queue.offerFirst(2);queue.offerLast(1);System.out.println("该队列队头元素为：");System.out.println(queue.peek());System.out.println("出队元素为");System.out.println(queue.poll());}
}● 顺序队：Queue接口+实现类ArrayDeque
Queue<Integer> queue = new ArrayDeque<>();//顺序队列● 链式队：Queue接口+实现类LinkedList
Queue<Integer> queue2 = new LinkedList<>();//链式队列4. 单向链表实现队列
● 实现代码:
class Node{public int val;public Node next;public int usedSize;public Node(int val){this.val=val;}
}public class MyQueue {public Node head;public Node last;//入队,实质上是一个尾插法public void offer(int val){Node node=new Node(val);if(head==null){head=node;last=node;}else {last.next=node;last=last.next;}usedSize++;}//出队public int poll(){if(isEmpty()){throw new RuntimeException("队列为空！");}int oldVal=head.val;this.head=head.next;if(head == null) {last null;}usedSize--;return oldVal;}//是否为空public boolean isEmpty(){return this.usedSize == 0;}//查看栈顶元素public int peek( ){if(isEmpty()) {throw new RuntimeException("队列为空！");}return head.val;}public int getUsedSize() {return usedSize;}
}5. 双向链表实现队列
public class Queue {// 双向链表节点public static class ListNode {ListNode next;ListNode prev;int value;ListNode(int value) {this.value = value;}ListNode first; // 队头ListNode last; // 队尾int size = 0;// 入队列---向双向链表位置插入新节点public void offer(int e) {ListNode newNode = new ListNode(e);if (first == null) {first = newNode;// last = newNode;} else {last.next = newNode;newNode.prev = last;// last = newNode;}last = newNode;size++;}// 出队列---将双向链表第一个节点删除掉public int poll() {// 1. 队列为空// 2. 队列中只有一个元素----链表中只有一个节点---直接删除// 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除int value = 0;if (first == null) {return -1;} else if (first == last) {last = null;first = null;} else {value = first.value;first = first.next;first.prev.next = null;first.prev = null;}--size;return value;}// 获取队头元素---获取链表中第一个节点的值域public int peek() {if (first == null) {return -1;}return first.value;}public int size() {return size;}public boolean isEmpty() {return first == null;}
}6.循环队列
循环队列的引入:
二、队列相关OJ题
1.设计循环队列
● 写题链接:225. 用队列实现栈 - 力扣（LeetCode）
● 解题思路:front代表队头元素的下标,rear代码队尾元素的下标,每次入队出队都用取模公式来维护,入队元素增加,队尾rear下标的位置更新到(rear+1) % elem.length位置上,出队元素减少,队头front下标的位置也更新到(rear+1) % elem.length位置上,注意获取队尾元素的时候,如果rear==0说明队尾元素已经走到该数组的最后一个位置了,因为我们底层是用数组维护的,防止越界.
注意:
在循环队列中，我们添加元素时，元素被放置在队尾指针
rear当前的位置，然后rear会向后移动一步。所以，真正的元素存储在rear - 1的位置上（当rear为 0 时，元素存储在数组的末尾位置）。这意味着，在任何时刻，rear所指向的位置都是空的。当
rear的下一个位置就是队头指针front时，说明队列已经满了。这时，我们不能再向队列中添加元素，因为这将使得队头指针和队尾指针指向同一位置，导致队列为空和队列已满的歧义。所以，在这种情况下，我们不会在当前rear所指向的位置放置元素，保持这个位置为空，以区分队列为空和队列已满的状态。
● 实现代码:
class MyCircularQueue {public int[] elem; // 存储队列元素的数组public int front; // 队头下标public int rear; // 队尾下标public MyCircularQueue(int k) {// 因为牺牲了一个空间,所以数组长度+1this.elem = new int[k + 1];}// 入队操作public boolean enQueue(int value) {if (isFull()) return false; // 如果队列已满, 直接返回 falsethis.elem[rear] = value; // 将值放入队尾位置rear = (this.rear + 1) % elem.length; // 更新队尾下标，使用取模运算实现循环return true;}// 出队操作public boolean deQueue() {if (isEmpty()) return false; // 如果队列为空, 直接返回 false// 不用管原数，会被新入队的数直接替代front = (this.front + 1) % elem.length; // 更新队头下标，使用取模运算实现循环return true;}// 得到队头元素public int Front() {if (isEmpty()) {throw new RuntimeException("队列为空"); // OJ上改为 return -1;}return this.elem[front]; // 返回队头元素}// 得到队尾元素public int Rear() {if (isEmpty()) {throw new RuntimeException("队列为空"); // OJ上改为 return -1;}int index = 0;if (rear == 0) {index = elem.length - 1; // 当队尾下标为0时,队尾元素位于数组末尾} else {index = rear - 1; // 其他情况下,队尾元素位于队尾下标前一个位置}return this.elem[index]; // 返回队尾元素}// 判断队列是否为空public boolean isEmpty() {return front == rear; // 队头下标等于队尾下标时, 队列为空}// 判断队列是否已满public boolean isFull() {// 判断队尾下一个位置是队头就是满了if ((this.rear + 1) % elem.length == front) {return true;}return false;}
}
2. 用栈实现队列
● 写题链接:232. 用栈实现队列 - 力扣（LeetCode）
● 写题思路：
1) 因为队列是先进先出，所以我们要借用两个栈实现
2) 一个栈A存入队的序列，另一个栈B为出队的序列，栈B的数据由栈A出栈得到
3) 出数据从栈B出，如果栈B为空则从栈A中获取，再由栈B出数据，实现数据的先进先出。
● 图示
● 实现代码:
class MyQueue {Deque<Integer> s1; // 入队栈Deque<Integer> s2; // 出队栈public MyQueue() {s1 = new ArrayDeque<Integer>(); // 初始化入队栈s2 = new ArrayDeque<Integer>(); // 初始化出队栈}public void push(int x) {s1.push(x); // 将元素推入入队栈}public int pop() {if (empty()) { // 如果队列为空return -1;}if (s2.isEmpty() && !s1.isEmpty()) { // 如果出队栈为空且入队栈非空while (!s1.isEmpty()) { // 将入队栈的所有元素倒入出队栈s2.push(s1.pop());}return s2.pop(); // 弹出出队栈顶部元素}return s2.pop(); // 弹出出队栈顶部元素}public int peek() {if (empty()) { // 如果队列为空return -1;}if (s2.isEmpty() && !s1.isEmpty()) { // 如果出队栈为空且入队栈非空while (!s1.isEmpty()) { // 将入队栈的所有元素倒入出队栈s2.push(s1.pop());}return s2.peek(); // 返回出队栈顶部元素，但不弹出}return s2.peek(); // 返回出队栈顶部元素，但不弹出}public boolean empty() {return s1.isEmpty() && s2.isEmpty(); // 当入队栈和出队栈都为空时，队列为空}
}
3. 用队列实现栈
● 写题链接:225. 用队列实现栈 - 力扣（LeetCode）
● 写题思路：
1) 因为栈是先进后出，所以我们要借用两个队列实现
2) 哪个队列不为空则往那个队列入数据，如果都为空，默认往队列qu1入数据
3) 出数据时要先将数据不为空的队列的前length - 1个元素入到另一个空队中，然后将最后一个元素出队。
注:查看栈顶元素不需要将最后一个元素出队，要保存它，且继续把它入到另一个空队中。
● 图示
● 实现代码:
class MyStack {Queue<Integer> q1; // 第一个队列Queue<Integer> q2; // 第二个队列public MyStack() {q1 = new LinkedList(); // 初始化第一个队列q2 = new LinkedList(); // 初始化第二个队列}public void push(int x) {if (!q1.isEmpty()) { // 如果第一个队列非空q1.offer(x); // 将元素添加到第一个队列末尾} else if (!q2.isEmpty()) { // 如果第二个队列非空q2.offer(x); // 将元素添加到第二个队列末尾} else {if (q1.isEmpty() && q2.isEmpty()) { // 如果两个队列都为空q1.offer(x); // 将元素添加到第一个队列末尾}}}public int pop() {if (empty()) { // 如果栈为空return -1;}if (!q1.isEmpty()) { // 如果第一个队列非空int size = q1.size();for (int i = 0; i < size - 1; i++) { // 将前 size-1 个元素移动到第二个队列int val = q1.poll();q2.offer(val);}return q1.poll(); // 返回并移除第一个队列的最后一个元素} else {int size = q2.size();for (int i = 0; i < size - 1; i++) { // 将前 size-1 个元素移动到第一个队列int val = q2.poll();q1.offer(val);}return q2.poll(); // 返回并移除第二个队列的最后一个元素}}public int top() {if (empty()) { // 如果栈为空return -1;}if (!q1.isEmpty()) { // 如果第一个队列非空int size = q1.size();int val = -1;for (int i = 0; i < size; i++) { // 将所有元素移动到第二个队列，同时记录最后一个元素的值val = q1.poll();q2.offer(val);}return val; // 返回最后一个元素的值，即栈顶元素} else {int size = q2.size();int val = -1;for (int i = 0; i < size; i++) { // 将所有元素移动到第一个队列，同时记录最后一个元素的值val = q2.poll();q1.offer(val);}return val; // 返回最后一个元素的值，即栈顶元素}}public boolean empty() {if (q1.isEmpty() && q2.isEmpty()) { // 如果两个队列都为空return true; // 栈为空} else {return false; // 栈非空}}
}
