devbox
黑客灵魂
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Java----队列（Queue）

作者：黑客灵魂 | 2024-07-31 04:11:51

赞

踩

Java----队列（Queue）

目录

1.队列（Queue）

1.1概念

1.2队列的使用

1.3队列的模拟实现

1.4循环队列

1.4.1循环队列下标偏移

1.4.2如何区分队列是空还是满

1.5双端队列 (Deque)

1.队列（Queue）

1.1概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头 （Head/Front）

生活实例：

食堂排队打饭，先排队的先打到饭 

1.2队列的使用

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

队列的方法：

方法功能
boolean offer(E e)入队列
E poll()出队列
peek()获取队头元素
int size()获取队列中有效元素个数
boolean isEmpty()检测队列是否为空

注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

  1. public static void main(String[] args) {
  2.     Queue<Integer> q = new LinkedList<>();
  3.     q.offer(1);
  4.     q.offer(2);
  5.     q.offer(3);
  6.     q.offer(4);
  7.     q.offer(5);                  // 从队尾入队列
  8.     System.out.println(q.size());
  9.     System.out.println(q.peek());  // 获取队头元素
  10.     
  11.     q.poll();
  12.     System.out.println(q.poll());  // 从队头出队列，并将删除的元素返回
  13.     
  14.     if(q.isEmpty()){
  15.         System.out.println("队列空");
  16.    }else{
  17.         System.out.println(q.size());
  18.    }
  19. }

1.3队列的模拟实现

队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有 两种：顺序结构和链式结构。

  1. public class Queue {
  2.     // 双向链表节点
  3.     public static class ListNode{
  4.         ListNode next;
  5.         ListNode prev;
  6.         int value;
  7.  
  8.         ListNode(int value){
  9.             this.value = value;
  10.        }
  11.    }
  12.  
  13.     ListNode first;   // 队头
  14.     ListNode last;    // 队尾
  15.     int size = 0;
  16.  
  17.     // 入队列---向双向链表位置插入新节点
  18.     public void offer(int e){
  19.         ListNode newNode = new ListNode(e);
  20.         if(first == null){
  21.             first = newNode;
  22.             // last = newNode;
  23.        }else{
  24.             last.next = newNode;
  25.             newNode.prev = last;
  26.             // last = newNode;
  27.        }
  28.  
  29.         last = newNode; 
  30.         size++;
  31.    }
  32.  
  33.     // 出队列---将双向链表第一个节点删除掉
  34.     public int poll(){
  35.         // 1. 队列为空
  36.         // 2. 队列中只有一个元素----链表中只有一个节点---直接删除
  37.         // 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除
  38.         int value = 0;
  39.         if(first == null){
  40.             return null;
  41.        }else if(first == last){
  42.             last = null;
  43.             first = null;
  44.        }else{
  45.             value = first.value;
  46.             first = first.next;
  47.             first.prev.next = null;
  48.             first.prev = null;
  49.        }
  50.         --size;
  51.         return value;
  52.    }
  53.  
  54.     // 获取队头元素---获取链表中第一个节点的值域
  55.     public int peek(){
  56.         if(first == null){
  57.             return null;
  58.        }
  59.  
  60.         return first.value;
  61.    }
  62.  
  63.     public int size() {
  64.         return size;
  65.    }
  66.  
  67.     public boolean isEmpty(){
  68.         return first == null;
  69.    }
  70. }

1.4循环队列

实际中我们有时还会使用一种队列叫循环队列。环形队列通常使用数组实现。

1.4.1循环队列下标偏移

往后偏移offset个单位

index是当前位置数组下标，offset是需要往后走的单位

偏移后数组下标计算：（index+offset）%array.length

往前偏移offset个单位

index是当前位置数组下标，offset是需要往后走的单位

偏移后数组下标计算：（index+array.length-offset）%array.length

往前走offset步就相当于往后走array.length-offset步

1.4.2如何区分队列是空还是满

1. 通过添加 size 属性记录，如果size等于数组长度则满，否则不满

2. 保留一个位置，

3. 使用标记，判断尾的下一个是不是头

622. 设计循环队列 - 力扣（LeetCode）

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

  • MyCircularQueue(k): 构造器，设置队列长度为 k 。
  • Front: 从队首获取元素。如果队列为空，返回 -1 。
  • Rear: 获取队尾元素。如果队列为空，返回 -1 。
  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
  • isEmpty(): 检查循环队列是否为空。
  • isFull(): 检查循环队列是否已满。

方法：

  1. class MyCircularQueue {
  2.  
  3. private int front;
  4. private int rear;
  5. private int[]arr;
  6. private int k;
  7.  
  8.     public MyCircularQueue(int k1) {
  9. k=k1+1;
  10. arr=new int[k];
  11.     }
  12.     
  13.     public boolean enQueue(int value) {
  14. if(isFull()){
  15.     return false;
  16. }
  17. arr[rear]=value;
  18. rear=(rear+1)%k;
  19. return true;
  20.     }
  21.     
  22.     public boolean deQueue() {
  23. if(isEmpty()){
  24.     return false;
  25. }
  26. front=(front+1)%k;
  27. return true;
  28.     }
  29.     
  30.     public int Front() {
  31. if(isEmpty()){
  32.     return -1;
  33. }
  34. return arr[front];
  35.     }
  36.     
  37.     public int Rear() {
  38. if(isEmpty()){
  39.     return -1;
  40. }
  41. return arr[(rear-1+k)%k];
  42.     }
  43.     
  44.     public boolean isEmpty() {
  45. return front==rear;
  46.     }
  47.     
  48.     public boolean isFull() {
  49. return (rear+1)%k==front;
  50.     }
  51. }

1.5双端队列 (Deque)

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

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

  1. Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
  2. Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现

用队列实现栈

225. 用队列实现栈 - 力扣（LeetCode）

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

方法：

使用两个队列，队列一用来存储数据，队列二始终保持空，当入栈时，将数据入队到队列二，然后将队列一的数据出队后入队到队列二，将队列一和队列二互换，使得队头放后放入的数据，队尾放先放入的数据，完成入栈

出栈：出队队列一

top：返回队列一的队头元素

判断是否为空：调用isEmpty方法判断队列是否为空

  1. class MyStack {
  2.         Queue<Integer>que1;
  3.         Queue<Integer>que2;
  4.  
  5.     public MyStack() {
  6. que1=new LinkedList<>();
  7. que2=new LinkedList<>();
  8.     }
  9.     
  10.     public void push(int x) {
  11. que2.offer(x);
  12. while(!(que1.isEmpty())){
  13.     que2.offer(que1.poll());
  14. }
  15. Queue<Integer>tmp=que1;
  16. que1=que2;
  17. que2=tmp;
  18.     }
  19.     
  20.     public int pop() {
  21. return que1.poll();
  22.     }
  23.     
  24.     public int top() {
  25. return que1.peek();
  26.     }
  27.     
  28.     public boolean empty() {
  29. return que1.isEmpty();
  30.     }
  31. }

用栈实现队列

232. 用栈实现队列 - 力扣（LeetCode）

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

方法：

创建两个栈，一个用来模拟入队，一个用来模拟出队，入队时，压栈进stack1，出队时先调用peek方法，然后再stack2出栈，peek方法是先判断stack2是否为空，不为空返回栈顶元素，为空就看stack1是否也为空，都为空说明队列为空，不为空就将stack1的元素出栈再压栈到stack2中，然后返回stack2的栈顶元素

判断是否为空，就判断两个栈是否都为空

  1. class MyQueue {
  2. private Stack<Integer> stack1;
  3. private Stack<Integer> stack2;
  4.  
  5.     public MyQueue() {
  6. stack1=new Stack<>();
  7. stack2=new Stack<>();
  8.     }
  9.     
  10.     public void push(int x) {
  11. stack1.push(x);
  12.     }
  13.     
  14.     public int pop() {
  15. peek();
  16. return stack2.pop();
  17. }
  18.     
  19.     
  20.     public int peek() {
  21.         if(!stack2.isEmpty()){
  22.             return stack2.peek();
  23.         }
  24.         if(stack1.isEmpty()){
  25.             return -1;
  26.         }
  27. while(!stack1.isEmpty()){
  28.     stack2.push(stack1.pop());
  29. }
  30. return stack2.peek();
  31.     }
  32.     
  33.     public boolean empty() {
  34. return stack1.isEmpty()&&stack2.isEmpty();
  35.     }
  36. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/黑客灵魂/article/detail/906973
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号