数据结构&算法_队列

队列

对列是一个有序列表,可以用数组或是链表来实现

原则:

遵循先入先出的原则。即：先存入队列的数据，使用时要先取出，后存入的数据，使用时后取出。

数组模拟队列

  • 当我们将数据存入队列时称为“addQueue”，addQueue的处理需要有两个步骤：
    1. 将尾指针往后移：rear+1，当front == rear【空】
    2. 若尾指针rear小于队列的最大下标maxSize-1，则将数据存入rear所指的数组元素中，否则无法存入数据。rear == maxSize-1【队列满】
public class QueueForArr {
    public static void main(String[] args) throws Exception {
        ArrayQueue arrayQueue = new ArrayQueue(5);
        arrayQueue.addQueueData(16);
        arrayQueue.addQueueData(16);
        arrayQueue.addQueueData(16);
        arrayQueue.addQueueData(16);
        System.out.println("为空吗?" + arrayQueue.isEmpty());
        System.out.println("满了吗?" + arrayQueue.isFull());
        arrayQueue.addQueueData(16);
        System.out.println("满了吗?" + arrayQueue.isFull());
        System.out.println("头部数据为" + arrayQueue.getHeadPointerData());
        arrayQueue.printQueue();
    }
}

class ArrayQueue {
    //队列最大的容量
    private int maxSize;
    //队列头指针
    private int headPointer;
    //队列尾指针
    private int tailPointer;
    //创建数组用来保存队列中的数据
    private int[] queueArr;

    //队列构造器
    public ArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        //初始状态头指针指向头部位置
        headPointer = -1;
        //初始状态尾指针指向头部位置
        tailPointer = -1;
        queueArr = new int[maxSize];
    }

    //判断队列是否为空
    public boolean isEmpty() {
        //头部数据和尾部数据相同时即为空
        return headPointer == tailPointer;
    }

    //判断队列是否已满
    public boolean isFull() {
        return tailPointer == maxSize - 1;
    }

    //往队列里添加元素
    public void addQueueData(int data) throws Exception {
        if (isFull()) {
            throw new Exception("队列已满,不能添加数据了");
        }
        tailPointer++;
        queueArr[tailPointer] = data;
    }

    //取出队列中的数据
    public void getQueueData() throws Exception {
        //判断队列是否为空
        if (isEmpty()) {
            throw new Exception("队列已经空了,你还能取啥,歇歇吧!!");
        }
        headPointer++;
    }

    //得到队列的头部数据
    public int getHeadPointerData() throws Exception {
        if (isEmpty()) {
            throw new Exception("都空了,头肯定没有了呀");
        }
        return queueArr[headPointer + 1];
    }

    //打印队列的所有元素
    public void printQueue() {
        if (isEmpty()) {
            System.out.println("都空了,还打印啥");
        }
        for (int i = 0; i < queueArr.length; i++) {
            System.out.printf("queueArr[%d]=%d\n", i, queueArr[i]);

        }
    }
}

数组模拟环形队列

思路:

  1. headPointer的初始值需做调整,由 -1 变为 0
  2. tailPointer的初始值需做调整,由 -1 变为 0
  3. 判断队列满的条件 (tailPointer+1)%maxSize == headPointer
  4. 判断队列为空的条件 tailPointer = =headPointer
  5. 判断队列中有效数据的个数 (tailPointer-headPointer+maxSize)%maxSize
public class CycleQueueForArr {
    public static void main(String[] args) throws Exception {
        //创建循环队列类
        CycleQueue cycleQueue = new CycleQueue(5);//有效数据为4个
        Scanner scanner = new Scanner(System.in);
        String key = "";
        boolean flag = true;
        while (flag) {

            System.out.println("a:添加数据");
            System.out.println("b:取出数据");
            System.out.println("c:得到有效数据的个数");
            System.out.println("d:打印数据");
            System.out.println("q:退出");
            key = scanner.next();
            switch (key) {
                case "a":
                    System.out.println("请输入一个数");
                    cycleQueue.addData(scanner.nextInt());
                    break;
                case "b":
                    System.out.println("取出头部数据");
                    System.out.println("头部数据为" + cycleQueue.getData());
                    break;
                case "c":
                    cycleQueue.getValidData();
                    break;
                case "d":
                    cycleQueue.printData();
                    break;
                case "q":
                    flag = false;
                    break;
                default:
                    break;
            }
        }

    }
}

class CycleQueue {
    //创建头节点
    private int headPointer;
    //创建尾节点
    private int tailPointer;
    //创建数组保存数据
    private int[] arrForQueue;
    //创建队列容量指示器
    private int maxSize;
    //记录队列中有效数据的个数
    private int validData;

    //构造器
    public CycleQueue(int maxSize) {
        this.maxSize = maxSize;
        headPointer = 0;
        tailPointer = 0;
        validData = 0;
        arrForQueue = new int[maxSize];
    }

    //判断队列是否已满
    public boolean isFull() {
        return (tailPointer + 1) % maxSize == headPointer;
    }

    //判断队列是否为空
    public boolean isEmpty() {
        return headPointer == tailPointer;
    }

    //得到队列中有效数据的个数
    public void getValidData() throws Exception {
        if (isEmpty()) {
            throw new Exception("队列为空");
        }
        validData = (tailPointer - headPointer + maxSize) % maxSize;
        System.out.println("有效数据的个数为:" + validData + "个");
    }

    //往队列中添加数据
    public void addData(int data) throws Exception {
        //判断队列是否已满
        if (isFull()) {
            throw new Exception("都满了还加啥");
        }
        arrForQueue[tailPointer] = data;
        tailPointer = (tailPointer + 1) % maxSize;
        System.out.println(tailPointer);
    }

    //取出队列中的数据
    public int getData() throws Exception {
        if (isEmpty()) {
            throw new Exception("都空了还取啥");
        }
        int data = arrForQueue[headPointer];
        headPointer = (headPointer + 1) % maxSize;
        return data;
    }

    //打印队列中的所有数据
    public void printData() throws Exception {
        if (isEmpty()) {
            throw new Exception("都空了还打印啥");
        }
        for (int i = headPointer; i < headPointer+((tailPointer -headPointer+ maxSize) % maxSize); i++) {
            System.out.printf("arr[%d]=%d\n", i % maxSize, arrForQueue[i % maxSize]);
        }
    }

}