当前位置：首页 > article >正文

java基于数组实现队列

article 2025/2/22 14:44:23

概述

推荐阅读下基于链表实现队列。

实现

package com.lovehena.datastructure;

import lombok.extern.slf4j.Slf4j;

/*
 *   基于数组实现队列
 *       队列：先进先出的一种数据结构，一般在队头进行出队，队尾进行入队。
 *
 *   想象一下，初高中时课间操排队，是从队尾加入一个人（比如某个同学上厕所去了来晚了就排在队伍的后面），从队头出一个人（比如某班班长上台讲话）
 *
 *   先实现以下3个方法：
 *       1.从队尾入队 offer()
 *       2.从队头出队 poll()
 *       3.遍历      print()
 * */
@Slf4j
public class ArrayQueue {
    private int[] arr = null; // 用数组模拟队列 数组中的元素类型都是int 如果元素类型是其他类型 推荐用泛型机制实现
    private int capacity; // 队列容量 （实现有界队列）
    private int tail = 0; // 队列的尾指针（变量引用）

    /**
     * 构造一个指定容量的队列
     *
     * @param capacity
     */
    public ArrayQueue(int capacity) {
        this.capacity = capacity;
        arr = new int[capacity];
    }

    /**
     * 从队尾入队
     *  思路：入队时tail指向的就是最后一个元素的位置 所以让arr[tail]=value tail++即可
     *
     * @param value
     * @return
     */
    public boolean offer(int value) {
        if (tail == capacity) { //队列放满了
            log.info("元素 {} 入队失败 因为队列放满了", value);
            return false;
        }
        arr[tail] = value;
        tail++;

        return true;
    }

    /**
     * 从队头出队
     *
     *  明确：tail为几 数组中就有几个元素
     *
     *  思路：队头即数组中索引为0的位置 返回数组中索引为0的元素 数组中其他元素均往前移动一位将数组为0的元素覆盖即可
     *  重点分析System.arraycopy()方法中参数
     *
     *  数组元素 1 2 3 4 5
     *     索引 0 1 2 3 4
     *
     *  现在要将索引为0的元素出队 则索引为1（即System.arraycopy()方法中的srcPos） 2 3 4的元素（4个元素，4=tail-1）都要往前移动一位
     *  tail-1即System.arraycopy()方法中的length
     *
     *  数组变为
     *
     *   数组元素 2 3 4 5
     *      索引 0 1 2 3
     *
     *   索引0即System.arraycopy()方法中的destPos
     * @return
     */
    public int poll() {
        // tail为几 数组中就有几个元素
        if (tail == 0) { // 没有元素
            return -1;
        }

        int polled = arr[0]; // 队头元素
        System.arraycopy(arr,1,arr,0,tail-1);
        tail--; // 出队后 tail往前移动一位
        return polled;
    }

    /**
     *  遍历队列
     */
    public void print(){
        StringBuilder sb = new StringBuilder();
        // 从队头元素开始 直到队尾
        for (int i = 0; i < tail; i++) { // tail为几 数组中就有几个元素 所以遍历时 i的最大值为tail-1
            sb.append(arr[i]).append(" ");
        }
        log.info("遍历队列 队列为：{}",sb.toString());
    }

    //todo 扩展：本实现中的出队、入队的实现逻辑会不会有线程安全问题？如果有，怎么解决？
    //todo 扩展：当前的实现中，入队时，如果队列已满则入队失败，能不能不要立刻返回失败，而是等一段时间看是否有出队操作，如果发生了出队，不就可以入队了？怎么实现？（1）
    //todo 扩展：当前的实现中，出队时，如果队列为空则提示队列为空，能不能不要立刻提示队列为空，而是等一段时间看是否有入队操作，如果有入队，不就可以出队了？怎么实现？（2）
    //todo 扩展：（1）（2）这两个问题有没有让你想到什么模型或者什么关键词？
}

测试用例

package com.lovehena.datastructure.test;

import com.lovehena.datastructure.ArrayQueue;
import lombok.extern.slf4j.Slf4j;

@Slf4j
public class TestArrayQueue {
    public static void main(String[] args) {
        ArrayQueue queue = new ArrayQueue(5);
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        queue.offer(5);
        queue.offer(6);
        queue.print();

        log.info("\n");
        int polled = queue.poll();
        log.info("出队的元素：{}", polled);
        queue.print();

        log.info("\n");
        queue.offer(100);
        queue.print();

        log.info("\n");
        int polled2 = queue.poll();
        log.info("再出队一个元素：{}", polled2);
        queue.print();
    }
}