数据结构与算法简单入门——队列

队列

1. 队列介绍

队列(Queue)。队列简称队。是一种操作受限的线性表,只允许在表的一端进行插入,而在表的另一端进行删除。向队列中插入元素称为入队或进队;删除元素称为出队或离队。其操作特性为先进先出(First In First Out,FIFO),并且只允许在队尾进,队头出。

2. 队列数组实现

先定义两个指针,front用于指向头部元素,rear用于指向尾部元素。当取出元素时front指针后移,当存入元素时rear指针后移。front、rear默认值-1。

两个理解点:

  • 当 front = rear 时队列为空
  • 当 rear = maxSize - 1 时队列满(maxSize为数组长度)
    数据结构与算法简单入门——队列

代码实现:

package com.zlp.datastructure.controller;

import java.util.Arrays;
import java.util.Scanner;

public class Queue {
    public static void main(String[] args) {
        // 创建队列
        System.out.println("请输入队列长度:");
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        ArrayQueue arrayQueue = new ArrayQueue(size);

        boolean flag = true;
        while (flag) {
            // 操作指南
            System.out.println("显示队列:1");
            System.out.println("添加数据:2");
            System.out.println("取出数据:3");
            System.out.println("结束:4");
            int choose = scanner.nextInt();
            switch (choose) {
                case 1:
                    arrayQueue.showQueue();
                    break;
                case 2:
                    System.out.println("请输入要添加的数据:");
                    int data = scanner.nextInt();
                    arrayQueue.addQueue(data);
                    System.out.println("数据添加成功~");
                    break;
                case 3:
                    int queue = arrayQueue.getQueue();
                    System.out.println("数据取出:" + queue);
                    break;
                case 4:
                    System.out.println("程序结束~");
                    return;
                default:
                    System.out.println("输入错误~");
                    break;
            }
        }
    }
}
class ArrayQueue{
        private int maxSize;
        private int front;// 头指针
        private int rear;// 尾指针
        private int[] arr;

  			// 队列构造方法
        public ArrayQueue(int size) {
            maxSize = size;
            arr = new int[maxSize];
            front = -1;
            rear = -1;
        }

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

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

        // 添加数据到队列
        public void addQueue(int data) {
            // 判断是否队列满
            if (isFull()) {
                System.out.println("队列已满~");
                return;
            }
            rear++;// 尾指针后移
            arr[rear] = data;
        }

        // 取出数据
        public int getQueue() {
            // 判断为空
            if (isEmpty()) {
                System.out.println("队列为空~");
                return 0;
            }
            front++; // 头指针后移
            return arr[front];
        }

        // 显示所有队列数据
        public void showQueue() {
            if (isEmpty()) {
                System.out.println("队列为空~");
                return;
            }
            System.out.println(Arrays.toString(arr));
        }

        // 显示队列头数据
        public int headQueue() {
            if (isEmpty()) {
                System.out.println("队列为空~");
                return 0;
            }
            return arr[front + 1];
        }
}

问题分析:

数组实现有个明显的缺点:这个队列我们只能用一次,不能重复使用,循环队列便可以解决这个问题。

3. 循环队列

利用数组取模,从而时数组形成环形。

一句话看起来抽象,我们举个例子:

比如该数组长度maxSize为3,也就是坐标有三种情况 0、1、2,这时候我们有一个指针index,当index=1时,通过取模index%3得到结果是1,同理index=2时得到结果2;index=3时得到结果0,这时如果index继续增加变为index=4,取模index%3得到结果为1,这样就有从1开始了一个新的循环。
数据结构与算法简单入门——队列
同样定义两个指针,front表示头指针,rear表示尾指针,指针默认值0

难点:

  • front指针直接指向第一个元素,即arr[front]就是第一个元素
  • rear指针指向最后一个元素的后一个位置,我们约定空出一个空间,方便操作
  • 循环队列移动指针时取模赋值,front = (front + 1) % maxSize rear = (rear + 1) % maxSize
  • 当front = rear时队列空
  • 当front = (rear + 1) % maxSize 时队列满

代码实现:

package com.zlp.datastructure.controller;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 环形队列
 */
public class CirQueue {
    public static void main(String[] args) {
        // 创建队列
        System.out.println("请输入队列长度:");
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        CirArrayQueue arrayQueue = new CirArrayQueue(size);

        boolean flag = true;
        while (flag) {
            // 操作指南
            System.out.println("显示队列:1");
            System.out.println("添加数据:2");
            System.out.println("取出数据:3");
            System.out.println("结束:4");
            int choose = scanner.nextInt();
            switch (choose) {
                case 1:
                    arrayQueue.showQueue();
                    break;
                case 2:
                    System.out.println("请输入要添加的数据:");
                    int data = scanner.nextInt();
                    arrayQueue.addQueue(data);
                    System.out.println("数据添加成功~");
                    break;
                case 3:
                    int queue = arrayQueue.getQueue();
                    System.out.println("数据取出:" + queue);
                    break;
                case 4:
                    System.out.println("程序结束~");
                    return;
                default:
                    System.out.println("输入错误~");
                    break;
            }
        }
    }
}
class CirArrayQueue{
    private int maxSize;
    private int front;// 头指针
    private int rear;// 尾指针
    private int[] arr;

    public CirArrayQueue(int size) {
        maxSize = size;
        arr = new int[maxSize];
        front = 0; //front 为当前第一个元素
        rear = 0; // 约定rear指向最后一个元素的后一个位置,也就是空出一个空间
    }

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

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

    // 添加数据到队列
    public void addQueue(int data) {
        // 判断是否队列满
        if (isFull()) {
            System.out.println("队列已满~");
            return;
        }
        arr[rear] = data; // 当前位置插入元素
        rear = (rear + 1) % maxSize;// 尾指针后移,尾指针指向最后一个元素的后一个位置
    }

    // 取出数据
    public int getQueue() {
        // 判断为空
        if (isEmpty()) {
            System.out.println("队列为空~");
            return 0;
        }
        int data = arr[front]; // 取出当前元素
        front = (front + 1) % maxSize; // 头指针后移
        return data;
    }

    // 显示所有队列数据
    public void showQueue() {
        if (isEmpty()) {
            System.out.println("队列为空~");
            return;
        }
        System.out.println(Arrays.toString(arr));
    }

    // 显示队列头数据
    public int headQueue() {
        if (isEmpty()) {
            System.out.println("队列为空~");
            return 0;
        }
        return arr[front + 1];
    }
}

手敲一遍代码,更容易理解~~

上一篇:C++实现栈和队列


下一篇:Java如何检测环形队列是空还是满(数据结构)