1. Toy模板网首页
  2. > Toy博客

数据结构之队列的详解

8月前 作者：忘忧记 分类：Toy博客 阅读(22) 违法举报

这篇具有很好参考价值的文章主要介绍了数据结构之队列的详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一.什么是队列

  • 队列是一种先入先出(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());
        }
    }

三.队列的模拟实现

  • 可以使用数组或链表实现队列
  • 使用数组实现时,需要维护两个指针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;
    }
}

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

四.队列的应用

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. 保留一个位置
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. 使用标记
  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;
    }

具体步骤:
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)空间。

具体代码:文章来源地址https://www.toymoban.com/news/detail-435633.html

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

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

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

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

五.总结

  • 队列是一种先入先出的线性表数据结构
  • 可以使用数组或链表实现队列,实现需要包含的方法有入队add、出队remove等
  • 队列操作的时间复杂度均为O(1),不受队列大小影响

到了这里，关于数据结构之队列的详解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构之队列的详解

    数据结构之队列的详解

    队列是一种先入先出(FIFO)的线性表数据结构 添加和删除操作只在表的两端进行,一端为队头,另一端为队尾 添加操作在队尾进行,称为入队或进队,删除操作在队头进行,称为出队 队列的图示 java内部的api 可以使用数组或链表实现队列 使用数组实现时,需要维护两个指针front和rea

    2024年02月03日
    浏览(22)

  • 数据结构——优先队列c++详解

    百度百科定义 优先队列是0个或多个元素的集合,每个元素都有一个优先权或值,对优先队列执行的操作有1) 查找;2) 插入一个新元素;3) 删除.在最小优先队列(min priority queue)中,查找操作用来搜索优先权最小的元素,删除操作用来删除该元素;对于最大优先队列(max priority queue),查找操

    2024年02月09日
    浏览(29)
  • C++数据结构之队列详解

    C++数据结构之队列详解

    队头填充进四个元素 此时思考一个问题，当删除元素时（元素出队列时）会出现假饱和的情况，如上图m_data[0]和m_data[1]再进行出队列操作之后，这两个位置可以容纳新的元素，但m_rear没有回到原本的m_data[0]位置，因此需要引入一个新的队列结构，环形队列，m_rear这个位置可以

    2024年02月05日
    浏览(30)
  • 数据结构之队列详解（包含例题）

    数据结构之队列详解（包含例题）

    队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。 我们可以用 单链表模拟 实现顺序队列。 队列采

    2024年02月13日
    浏览(32)
  • 【数据结构】C语言队列(详解)

    【数据结构】C语言队列(详解)

    前言: 💥🎈个人主页:​​​​​​Dream_Chaser～ 🎈💥 ✨✨专栏:http://t.csdn.cn/oXkBa ⛳⛳本篇内容:c语言数据结构--C语言实现队列 目录 一.队列概念及结构 1.1队列的概念 1.2队列的结构 二.队列的实现 2.1头文件 2.2链式队列的结构定义 2.3队列接口的定义 2.4初始化队列 2.5判断队列

    2024年02月10日
    浏览(31)
  • 【数据结构】队列（Queue）的实现 -- 详解

    【数据结构】队列（Queue）的实现 -- 详解

    1、概念 队列 ：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有 先进先出 FIFO(First In First Out)。 入队列 ：进行 插入 操作的一端称为 队尾 。 出队列 ：进行 删除 操作的一端称为 队头 。 2、结构 （1）队列的顺序存储结构 入队 ，不需要

    2024年02月15日
    浏览(28)
  • 数据结构之栈与队列详解

    数据结构之栈与队列详解

    栈和队列是一种特殊的线性结构，他与之前学的线性结构不同，栈和队列是拥有一种特殊规则的线性结构，虽然它是用数组或者链表实现，但是只有符合这种规则才能被称作栈或者队列 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和

    2024年01月16日
    浏览(34)
  • 【数据结构】队列---C语言版（详解！！！）

    【数据结构】队列---C语言版（详解！！！）

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

    2024年02月10日
    浏览(38)
  • 【算法与数据结构】队列的实现详解

    【算法与数据结构】队列的实现详解

    队列的概念： 队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 新添加的元素添加到队尾,只能从队头取出元素。 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头 队列特征如

    2024年04月13日
    浏览(32)
  • 数据结构-循环队列详解（c语言版）

    数据结构-循环队列详解（c语言版）

    目录 一、什么是循环队列？ 二、特点 三、基本运算 四、代码实现  1、初始化 2、入队 3、出队 4、队满？ 5、队空？  6、输出队列 7、队列大小 8、获取队首元素 五、队列应用场景 六、完整代码 1、完整代码 2、运行结果 七、总结 前言 相比于链队列， 循环队列 有着内存固

    2024年01月20日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包