devbox
在线问答5
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构之队列的详解_队列数据结构

作者：在线问答5 | 2024-08-01 19:12:00

赞

踩

队列数据结构

文章目录

一.什么是队列

  • 队列是一种先入先出(FIFO)的线性表数据结构
  • 添加和删除操作只在表的两端进行,一端为队头,另一端为队尾
  • 添加操作在队尾进行,称为入队或进队,删除操作在队头进行,称为出队

二.队列的使用

2.1 队列的基本操作

在这里插入图片描述
队列的图示
在这里插入图片描述

2.2 队列的基本使用

java内部的api

在这里插入图片描述

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());
        }
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

三.队列的模拟实现

  • 可以使用数组或链表实现队列
  • 使用数组实现时,需要维护两个指针front和rear,分别指向队头和队尾的下一个位置
  • 使用链表实现时,链表的头节点作为队头,尾节点作为队尾
  • 实现需要包含的方法有:入队add、出队remove、获取队头peek、判断是否为空isEmpty等

3.1 数组实现队列

public class ArrayQueue {
    private int front;
    private int rear;
    private int[] arr;
    private int capacity;
    
    public ArrayQueue(int capacity) {
        this.capacity = capacity;
        front = rear = 0;
        arr = new int[capacity];
    }
    
    // 入队操作,将元素加入队尾
    public void add(int elem) {
        if (rear == capacity) {
            System.out.println("队列已满");
            return;
        }
        arr[rear] = elem;
        rear++;
    }
    
    // 出队操作,移除队头元素
    public int remove() {
        if (front == rear) {
            System.out.println("队列为空"); 
            return -1;
        }
        int elem = arr[front];
        front++;
        return elem;
    }  
    
    // 获取队头元素
    public int peek() {
        if (front == rear) {
            System.out.println("队列为空");
            return -1;
        }
        return arr[front];
    }  
    
    // 判断队列是否为空
    public boolean isEmpty() {
        return front == rear;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47

3.2 链表实现队列

/**
 * @Author 12629
 * @Description：
 */
public class MyQueue {
    

    static class Node {
        public int val;
        public Node next;

        public Node(int val) {
            this.val = val;
        }
    }
    public Node head;
    public Node last;
    public int usedSize;

    //入队
    public void offer(int val) {
        Node node = new Node(val);
        if(head == null) {
            head = node;
            last = node;
        }else {
            last.next = node;
            last = node;
        }
        usedSize++;
    }

    public int poll() {
        if(empty()) {
            throw new EmptyException("队列为空");
        }
        int ret = head.val;
        head = head.next;
        if(head == null) {
            last = null;//只有一个节点 那么last也要置空
        }
        usedSize--;
        return ret;
    }

    public boolean empty() {
        return usedSize == 0;
    }

    public int peek() {
        if(empty()) {
            throw new EmptyException("队列为空");
        }
        return head.val;
    }

    public int getUsedSize() {
        return usedSize;
    }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61

四.队列的应用

4.1 设计循环队列

其实我们在设计循环队列的时候,我们最重要的一点就是如何考虑空与满的情况
大家肯定很难理解我在说什么,大家看我接下来的操作.
在这里插入图片描述
我们只要解决上面俩个核心问题,就能完整的构造循环队列
这思路巧妙的应用了一个取模运算
在这里插入图片描述

当然这里我们提供了三种思路:

  1. 通过添加 size 属性记录
 public boolean enQueue(int value) {
        if (size == elem.length) return false; //判断满
        elem[rear] = value;
        rear = (rear + 1) % elem.length;
        size++;
        return true;
    }
    
    public boolean deQueue() {
        if (size == 0) return false; //判断空
        front = (front + 1) % elem.length;
        size--;
        return true;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  1. 保留一个位置
public class MyCircularQueue {
    private int[] elem;
    private int front;
    private int rear;
    
    public MyCircularQueue(int k) {
        elem = new int[k+1];  //多一位
    }
    
    public boolean enQueue(int value) {
        if ((rear + 1) % elem.length == front) return false; //判断满
        elem[rear] = value;
        rear = (rear + 1) % elem.length;  
        return true;
    }  
}  

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  1. 使用标记
  public boolean enQueue(int value) {
        if (full) return false;   //判断满
        elem[rear] = value;
        rear = (rear + 1) % elem.length;  
        if (rear == front) full = true; //修改标记
        return true;
    }
    
    public boolean deQueue() {
        if (isEmpty()) return false;  //判断空
        front = (front + 1) % elem.length;
        full = false;     //修改标记
        return true;
    } 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

具体步骤:
5. 使用数组elem存储队列元素,定义front和rear指针表示队头和队尾位置。
6. enQueue(value)方法:先判断队列是否已满,未满则将元素加入rear位置,rear加1取模防止越界。
7. deQueue()方法:先判断队列是否为空,非空则front加1取模。
8. Front()方法:直接返回front位置元素,队空则返回-1。
9. Rear()方法:直接返回rear-1位置元素,队空则返回-1。需要判断rear是否为0,是则返回length-1位置元素。
10. isEmpty()方法:通过判断front和rear是否相等确定队列是否为空。
11. isFull()方法:通过判断rear+1位置是否等于front确定队列是否已满。
时间复杂度分析:

  • enQueue和deQueue方法时间复杂度O(1)。
  • 其他方法时间复杂度O(1)。
    空间复杂度分析:O(n),数组使用O(n)空间。

具体代码:

class MyCircularQueue {

    private int[] elem;
    private int front;//表示队列的头
    private int rear;//表示队列的尾

    public MyCircularQueue(int k) {
        //如果是浪费空间 这里必须处理多加一个1
        this.elem = new int[k+1];
    }

    /**
     * 入队列
     * @param value
     * @return
     */
    public boolean enQueue(int value) {
        //1、检查是否队列是满的
        if(isFull()){
            return false;
        }
        //2、
        elem[rear] = value;
        //rear++;
        rear = (rear+1) % elem.length;
        return true;
    }

    /**
     * 出队列
     * @return
     */
    public boolean deQueue() {
        if(isEmpty()) {
            return false;
        }
        //front++;
        front = (front+1) % elem.length;
        return true;
    }

    /**
     * 得到队头元素
     * @return
     */
    public int Front() {
        if(isEmpty()) {
            return -1;
        }
        return elem[front];
    }

    /**
     * 得到队尾元素
     * @return
     */
    public int Rear() {
        if(isEmpty()) {
            return -1;
        }
        int index = (rear == 0) ? elem.length-1 : rear-1;
        return elem[index];
    }
    
    public boolean isEmpty() {
        return front == rear;
    }

    /**
     * 队列是否为满
     * @return
     */
    public boolean isFull() {
       /* if( (rear+1) % elem.length == front) {
            return true;
        }
        return false;*/
        return (rear+1) % elem.length == front;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80

4.2 设计双端队列

具体思路:

  1. 可以使用链表或数组实现,这里我们使用数组实现。定义数组elem存储数据,front和rear分别表示头尾指针。
  2. 添加方法:
  • addFront(val):将元素插入至队头,front减1取模,将val放入front位置。
  • addRear(val):将元素插入至队尾,rear加1取模,将val放入rear位置。
  1. 移除方法:
  • removeFront():移除队头元素,front加1取模,返回front位置元素。
  • removeRear():移除队尾元素,rear减1取模,返回rear位置元素。
  1. 获取方法:
  • getFront():返回front位置元素,队空则返回-1。
  • getRear():返回rear位置元素,队空则返回-1。
  1. 判断方法:
  • isEmpty():当front==rear时,队列为空,返回true,否则返回false。
  • isFull():当(rear+1)%len==front时,队列已满,返回true,否则返回false。len为数组长度。
  1. 扩容方法:当添加元素时判断队列已满,调用扩容方法expand将数组size*2,并把原数据复制过来。

具体代码:

public class Deque {
    private int[] elem;
    private int front;
    private int rear;
    private int len;
    
    public Deque(int capacity) {
        elem = new int[capacity];
        front = rear = 0;
        len = 0;
    }
    
    //在队头添加元素
    public void addFront(int val) {
        if (isFull()) expand();
        front = (front - 1 + elem.length) % elem.length;
        elem[front] = val;
        len++;
    }
    
    //在队尾添加元素
    public void addRear(int val) {
        if (isFull()) expand();
        elem[rear] = val;
        rear = (rear + 1) % elem.length; 
        len++;
    }  
    
    //移除队头元素
    public int removeFront() {
        if (isEmpty()) return -1;
        int ret = elem[front];
        front = (front + 1) % elem.length;
        len--;
        return ret;
    }
    
    //移除队尾元素
    public int removeRear() {
        if (isEmpty()) return -1;
        rear = (rear - 1 + elem.length) % elem.length;
        int ret = elem[rear];
        len--;
        return ret;
    }
    
    //获取队头元素
    public int getFront() {
        if (isEmpty()) return -1;
        return elem[front];
    } 
    
    //获取队尾元素
    public int getRear() {
        if (isEmpty()) return -1;
        return elem[(rear - 1 + elem.length) % elem.length];
    }  
    
    //判断队列是否为空
    public boolean isEmpty() {
        return front == rear; 
    }
    
    //判断队列是否已满
    public boolean isFull() {
        return (rear + 1) % elem.length == front; 
    }
    
    //扩容方法
    private void expand() {
        int[] newElem = new int[elem.length * 2];
        for (int i = 0; i < len; i++) {
            newElem[i] = elem[(i + front) % elem.length]; 
        }
        front = 0;
        rear = len;
        elem = newElem;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79

4.3 队列实现栈

队列实现栈,在实现栈之前,我们先了解一下栈是怎么工作的,看下图

在这里插入图片描述

再看看两个队列是怎么实现栈的过程,我们用队列模拟,要记住一个核心规则

在这里插入图片描述
我演示一下入栈的规则
在这里插入图片描述
出栈的模拟演示:
在这里插入图片描述

代码如下:

import java.util.LinkedList;
import java.util.Queue;

class MyStack {

    private Queue<Integer> qu1;
    private Queue<Integer> qu2;

    public MyStack() {
        qu1 = new LinkedList<>();
        qu2 = new LinkedList<>();
    }
    
    public void push(int x) {
        if(!qu1.isEmpty()) {
            qu1.offer(x);
        } else if (!qu2.isEmpty()) {
            qu2.offer(x);
        }else {
            qu1.offer(x);
        }
    }
    
    public int pop() {
        if(empty()) {
            return -1;//两个队列都为空，意味着当前的栈为空
        }
        if(!qu1.isEmpty()) {
            int size = qu1.size();
            for (int i = 0; i < size-1; i++) {
                //for (int i = 0; i < qu1.size()-1; i++) {
                int val = qu1.poll();
                qu2.offer(val);
            }
            return qu1.poll();
        }else {
            int size = qu2.size();
            for (int i = 0; i < size-1; i++) {
                int val = qu2.poll();
                qu1.offer(val);
            }
            return qu2.poll();
        }
    }
    //peek
    public int top() {
        if(empty()) {
            return -1;//两个队列都为空，意味着当前的栈为空
        }
        if(!qu1.isEmpty()) {
            int size = qu1.size();
            int val = -1;
            for (int i = 0; i < size; i++) {
                val = qu1.poll();
                qu2.offer(val);
            }
            return val;
        }else {
            int size = qu2.size();
            int val = -1;
            for (int i = 0; i < size; i++) {
                val = qu2.poll();
                qu1.offer(val);
            }
            return val;
        }
    }
    
    public boolean empty() {
        return qu1.isEmpty() && qu2.isEmpty();
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72

4.4 栈实现队列

栈实现队列,还是老样子,我们还是来看看队列的工作状态
在这里插入图片描述
具体我们使用俩个栈模拟出队的操作

在这里插入图片描述

具体代码:

import java.util.Stack;

class MyQueue {

    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    public void push(int x) {
        stack1.push(x);
    }
    
    public int pop() {
        if(empty()) {
            return -1;
        }
        if(stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
    
    public int peek() {
        if(empty()) {
            return -1;
        }
        if(stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }
    
    public boolean empty() {
        return stack1.empty() && stack2.empty();
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44

五.总结

  • 队列是一种先入先出的线性表数据结构
  • 可以使用数组或链表实现队列,实现需要包含的方法有入队add、出队remove等
  • 队列操作的时间复杂度均为O(1),不受队列大小影响
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/在线问答5/article/detail/915484?site
推荐阅读
相关标签

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

  

闽ICP备14008679号