devbox
代码探险家
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Java-队列_java 队列

作者：代码探险家 | 2024-08-10 21:53:04

赞

踩

java 队列

 

目录

​

队列

双端队列

LinkList的常用方法

​

Queue的方法

​ Deque的方法

 模拟实现队列

循环队列

队列的相关OJ题：

用队列实现栈

用栈实现队列

 

队列

队列只允许一端插入元素，从另一端进行删除元素的特殊线性表。队列具有先进先出的特点。

入队：进入插入操作，这一端称为队尾。

出队：进行删除操作，这一端称为对头。

双端队列

在前文集合中我们提到了Queue和Deque，一个是普通队列一个是双端队列，他们底层都是由一个双向链表LinkList实现的，当然Queue还有由一个优先级队列priorityQueue（二叉树实现）。

 

 那么什么是双端队列呢？

双端队列是指两端都可以进行进队和出队操作的队列，将队列的两端分别称为前端和后端，两端都可以入队和出队。所以双端队列既能够当队列使用，也能当栈使用。

LinkList的常用方法

这些方法就不进行演示了，在前面的ArrayList的方法大致类似。

Queue的方法

Deque的方法

这些方法也是有点区别的，这里做了些总结：

而且使用时尽量匹配着使用，比如offer、poll、peek是一组，add、remove、element是一组。

 模拟实现队列

前面我们了解了队列中的一些方法，也知道了队列底层是由一个双向链表实现的。那么能不能用一个单链表实现呢？

我们来分析一下，队列的入队和出队时间复杂度都是O（1）。

我们使用尾插法，发现两种方法都达不到要求。

但我们发现第一种方法其实是一个少了一个尾指针，如果我们为其增设一个尾指针：

由此我们可以写出以下代码：

  1. class Node{
  2.     int val;
  3.     Node next;
  4.  
  5.     public Node(int val, Node next) {
  6.         this.val = val;
  7.         this.next = next;
  8.     }
  9.  
  10.     public Node(int val) {
  11.         this.val = val;
  12.     }
  13. }
  14. public class myQueue {
  15.     public Node head = null;
  16.     public Node last = null;
  17.     private int size = 0;
  18.  
  19.     public void offer(int val){
  20.         Node node = new Node(val);
  21.         if(head == null){
  22.             head = node;
  23.             last = node;
  24.         }else{
  25.             last.next = node;
  26.             last = last.next;
  27.         }
  28.         size++;
  29.     }
  30.  
  31.     public boolean isEmpty(){
  32.         return size == 0;
  33.     }
  34.  
  35.     public int poll(){
  36.         Node node = head;
  37.         head = head.next;
  38.         size--;
  39.         return node.val;
  40.     }
  41.  
  42.     public int peek(){
  43.         Node node = head;
  44.         return node.val;
  45.     }
  46. }

测试：

  1. public static void main(String[] args) {
  2.         myQueue queue = new myQueue();
  3.         queue.offer(1);
  4.         queue.offer(2);
  5.         queue.offer(3);
  6.         queue.offer(4);
  7.         System.out.println(queue.peek());
  8.         System.out.println(queue.poll());
  9.         System.out.println(queue.poll());
  10.         System.out.println(queue.poll());
  11.         System.out.println(queue.poll());
  12.  
  13. }

结果：

我们发现第二种方法如果想实现，似乎只能用双向链表实现了，所以如果想试着实现的可以试试哦，其实很简单的。

循环队列

我们原来模拟栈的时候不就是用的数组嘛，那么队列是否也可以用数组实现呢？

我们发现数组入队和出队时间复杂度都是O（1），那么这不是刚刚好嘛。但是有一个问题，如何判断队列是否满了。如果出现下列这种情况：

如何证明他满了？因为它前面还有两个空格？那你怎么知道它还有两个空格？

再比如现在如何插入元素，也就是说队尾如何回到数组最前方？

因此为了便于理解我们将这个数组卷起来：

 

回到一开始的问题，如何判断数组满了？

我们有4种解决方案：

第一种：

设立一个usedSize，入队usedSize++并且%一个数组的长度，出队usedSize--并且%一个数组长度，如果usedSize等于数组的长度则判断已满。

代码实现：

  1. public class MyCircularQueue {
  2.     int []elem;
  3.     int rear;
  4.     int front;
  5.     int usedSize;
  6.  
  7.     public MyCircularQueue() {
  8.         this.elem = new int[8];
  9.     }
  10.  
  11.     public boolean isEmpty(){
  12.         return usedSize == 0;
  13.     }
  14.  
  15.     public boolean isFull(){
  16.         return usedSize == elem.length;
  17.     }
  18.  
  19.     public boolean offer(int val){
  20.         if(isFull()){
  21.             System.out.println("队列已满");
  22.             return false;
  23.         }
  24.         this.elem[rear] = val;
  25.         rear = (rear + 1) % elem.length;
  26.         usedSize++;
  27.         return true;
  28.     }
  29.  
  30.     public boolean poll(){
  31.         if(isEmpty()){
  32.             System.out.println("队列为空");
  33.             return false;
  34.         }
  35.         front = (front - 1) % elem.length;
  36.         usedSize--;
  37.         return true;
  38.     }
  39.  
  40.     public int front(){//查看队头元素
  41.         if(isEmpty()){
  42.             System.out.println("队列为空");
  43.             return -1;
  44.         }
  45.         return this.elem[front];
  46.     }
  47.  
  48.     public int rear(){//查看队尾元素
  49.         if(isEmpty()){
  50.             System.out.println("队列为空");
  51.             return -1;
  52.         }
  53.         return this.elem[rear-1];
  54.     }
  55. }

测试：

  1. public static void main(String[] args) {
  2.         MyCircularQueue qu = new MyCircularQueue();
  3.         qu.offer(1);
  4.         qu.offer(2);
  5.         qu.offer(3);
  6.         qu.offer(4);
  7.         System.out.println(qu.front());
  8.         System.out.println(qu.rear());
  9.         System.out.println(qu.poll());
  10.         System.out.println(qu.poll());
  11.         System.out.println(qu.poll());
  12.         System.out.println(qu.poll());
  13.         System.out.println(qu.poll());
  14.  
  15.     }

 结果：

 第二种：

设立一个标志位 flg ，初始值为false，入队把flg置为true，出队则把flg置为false。

 

 

思路有了，代码就不写了哈，有兴趣的可以去尝试写写。

第三种：

浪费一个空间，判断rear的下一个是不是front，如果是就代表满了

其余的思路与第一种相似。

第四种：

首先说明这个方法不是特别好，但是力扣做题时用这种方法通过了（不想说啥，只能说明力扣用例不够全）。因为rear与front相遇时不是满就是空，因此当rear与front相遇时我们判断数组是否有元素存在，不存在则不满，存在即满了。当然因为是int类型我们也不能判断元素是否为空，只能判断那个值是否是0，因为我们出队时可以把那个位置的元素置为0，（如果你一开始入队的元素全是0就没法判断是否满喽~~~）。

代码：

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

力扣链接：设计循环队列 。

队列的相关OJ题：

用队列实现栈

前面我们学习了栈，现在用队列来实现下栈。

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

实现 MyStack 类：

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

示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

 解题思路：

因为栈是后进先出，而队列是先进先出，一开始我们可以指定一个队列来入队，之后如果再入队就如那个不为空的队列，然后出队的话，如果哪个队列不为空，先把队列的大小赋给一个变量，然后这个队列出队的元素用另一个队列入队，最后剩的元素就是要出栈的元素

 

代码：

  1. class MyStack {
  2.  
  3.     Queue<Integer> queue1;
  4.     Queue<Integer> queue2;
  5.  
  6.     /** Initialize your data structure here. */
  7.     public MyStack() {
  8.         queue1 = new LinkedList<Integer>();
  9.         queue2 = new LinkedList<Integer>();
  10.     }
  11.     
  12.     /** Push element x onto stack. */
  13.     public void push(int x) {
  14.         if(!queue1.isEmpty()){
  15.             queue1.offer(x);
  16.         }else if(!queue2.isEmpty()){
  17.             queue2.offer(x);
  18.         }else{
  19.             queue1.offer(x);
  20.         }
  21.     }
  22.     
  23.     /** Removes the element on top of the stack and returns that element. */
  24.     public int pop() {
  25.         if(empty())return -1;
  26.         if(!queue1.isEmpty()){
  27.             int size = queue1.size();
  28.             for(int i = 0; i < size - 1; i++){
  29.                 queue2.offer(queue1.poll());
  30.             }
  31.             return queue1.poll();
  32.         }else{
  33.             int size = queue2.size();
  34.             for(int i = 0; i < size - 1; i++){
  35.                 queue1.offer(queue2.poll());
  36.             }
  37.             return queue2.poll();
  38.         }
  39.     }
  40.     
  41.     /** Get the top element. */
  42.     public int top() {
  43.         if(empty())return -1;
  44.         if(!queue1.isEmpty()){
  45.             int size = queue1.size();
  46.             for(int i = 0; i < size - 1; i++){
  47.                 queue2.offer(queue1.poll());
  48.             }
  49.             int val = queue1.poll();
  50.             queue2.offer(val);
  51.             return val;
  52.         }else{
  53.             int size = queue2.size();
  54.             for(int i = 0; i < size - 1; i++){
  55.                 queue1.offer(queue2.poll());
  56.             }
  57.             int val = queue2.poll();
  58.             queue1.offer(val);
  59.             return val;
  60.         }
  61.     }
  62.     
  63.     /** Returns whether the stack is empty. */
  64.     public boolean empty() {
  65.         return queue1.isEmpty() && queue2.isEmpty();
  66.     }
  67. }

力扣OJ链接：队列实现栈

用栈实现队列

队列实现栈后，我们再用栈来实现下队列吧~~

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

实现 MyQueue 类：

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

示例 1：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

 解题思路：

方法与用队列实现栈类似，先用一个栈stack1存储入队的元素，如果要出队，则把栈stack1全部出栈到栈stack2中，最后出stack2中的元素，之后循环就好了，哪个栈不为空把这个栈中的元素放到另一个栈中，最后出栈栈顶元素。

代码实现：

  1. class MyQueue {
  2.  
  3.     private Stack<Integer> stack1;
  4.     private Stack<Integer> stack2;
  5.  
  6.     public MyQueue() {
  7.         stack1 = new Stack<>();
  8.         stack2 = new Stack<>();
  9.     }
  10.  
  11.     public void push(int x) {
  12.         stack1.push(x);
  13.     }
  14.  
  15.     public int pop() {
  16.         if(!stack2.isEmpty()){
  17.             return stack2.pop();
  18.         }else{
  19.             while(!stack1.isEmpty()){
  20.                 int a = stack1.pop();
  21.                 stack2.push(a);
  22.             }
  23.             return stack2.pop();
  24.         }
  25.     }
  26.  
  27.     public int peek() {
  28.         if(!stack2.isEmpty()){
  29.             return stack2.peek();
  30.         }else{
  31.             while(!stack1.isEmpty()){
  32.                 int a = stack1.pop();
  33.                 stack2.push(a);
  34.             }
  35.             return stack2.peek();
  36.         }
  37.     }
  38.  
  39.     public boolean empty() {
  40.         if(stack1.isEmpty() && stack2.isEmpty())return true;
  41.         else return false;
  42.     }
  43. }

力扣OJ链接：用栈实现队列

队列介绍告一段落。

本文收录专栏《数据结构》。

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

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

  

闽ICP备14008679号