数据结构--环形队列的介绍与实现

曾经终败给现在 2022-10-18 01:35 209阅读 0赞

### 数据结构--环形队列实现 ###

*   *  一、环形队列实现原理
     *   *  环形队列的几个判断条件
     *  二、代码实现
     *   *  1.环形队列类（CircleQueue）
         *  2.环形队列类测试类
         *  3.程序运行结果
         *  4.完整代码

环形队列可以用数组实现，也可以使用循环链表实现.在使用数组实现循环队列的时候，需要理解清楚队列头和队列尾的判断空还是满的处理方法；

**环形队列特点：**

*  避免假溢出现象（*由于入队和出队的操作，头尾指针只增加不减少，致使被删元素的空间永远无法重新利用，当队列继续存储元素时，出现尾指针已经到达了队列尾，而实际头指针前面并未满的情况*），可以将队列空间充分重复利用
 *  收尾相连的FIFO的数据结构，采用数据的线性空间，数据组织简单，能快速知道队列是否满/空
 *  广泛用于网络数据收发，和不同程序间数据交换，均使用了环形队列

--------------------

## 一、环形队列实现原理 ##

>  *  内存上并没有环形的结构，因此环形队列实际上是数组的线性空间来实现的。
>  *  当数据到了尾部图和处理呢？它将转回到原来位置进行处理，通过**取模**操作来实现

### 环形队列的几个判断条件 ###

front:指向队列的第一个元素，初始值front=0

rear: 指向队列的**最后一个元素的后一个位置**（预留一个空间作为约定）,初始值rear=0

maxSize: 数组的最大容量

*  队空：front == rear
 *  **队满：**(rear+1)%maxSize == front
 *  队列中的有效数据个数：（rear+maxSize-front）% maxSize

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzA0NDE1_size_16_color_FFFFFF_t_70_pic_center]

> 其中判断队列满的思想的话，可以看下图，因为是环形的，起初front=rear=0，每当添加元素时，将rear++，但是其实预留了一个长度没有用，比如定义的队列数组长度为5时，但是实际上可以使用的地址就是0,1,2,3，此时rear=4, 4这个空间用来判断队满的条件（rear+1）%maxSize==front

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzA0NDE1_size_16_color_FFFFFF_t_70_pic_center 1]

## 二、代码实现 ##

### 1.环形队列类（CircleQueue） ###

/** * 环形队列类 * 构造器 * 判断是否已满、判断是否空、查看队列数据、显示队列的有效数据个数、入队列、出队列 */
    
    class CircleQueue { 
    // 数组的最大容量
        private final int maxSize;
    // front指向队列的第一个元素，初始值为0
        private int front;
    // rear指向队列的最后一个元素的后一个位置，空出一个空间作为约定，初始值为0
        private int rear;
    // 存放数据，模拟队列
        private final int[] arr;
    
        // 创建队列构造器
        public CircleQueue(int maxSize) { 
            this.maxSize = maxSize;
            front = 0;
            rear = 0;
            arr = new int[maxSize];
        }
    
        // 判断队列是否已满
        public boolean isFull() { 
            return (rear + 1) % maxSize == front;
        }
    
        // 判断队列是否为空
        public boolean isEmpty() { 
            return rear == front;
        }
    
        // 查看队列数据,显示队列所有数据
        public void showQueue() { 
            if (isEmpty()) { 
                System.out.println("队列为空，没有数据！");
                return;
            }
    // 从front开始遍历，注意遍历的元素个数
            for (int i = front; i < front + size(); i++) { 
                System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
            }
    
        }
    
        // 求出当前队列有效数据的个数
        public int size() { 
            return (rear + maxSize - front) % maxSize;
        }
    
        // 显示队列的头数据，注意不是取出数据
        public int headQueue() { 
            if (isEmpty()) { 
                throw new RuntimeException("队列是空的，没有数据！");
            }
            return arr[front];
        }
    
        // 添加数据到队列
        public void addQueue(int n) { 
            if (isFull()) { 
                System.out.println("队列已满");
                return;
            }
            arr[rear] = n;
            System.out.println(n + "成功添加到队列");
            // 将rear后移，这里必须考虑取模
            rear = (rear + 1) % maxSize;
        }
    
        // 从队列取出数据,，出队列
        public int getQueue() { 
            if (isEmpty()) { 
                throw new RuntimeException("队列为空，无法取出数据");
            }
            // 这里需要分析出front是指向队列的第一个元素
            // 1. 先把front对应的值保留到一个临时变量
            // 2. 将front后移，考虑取模
            // 3. 将临时保存的变量取回
            int value = arr[front];
            front = (front + 1) % maxSize;
            return value;
        }

### 2.环形队列类测试类 ###

### 3.程序运行结果 ###

s(show),显示队列数据
    e(exit),退出队列
    a(add),添加数据到队列
    g(get),获取队列数据
    h(head),获取队列头数据
    s
    队列为空，没有数据！
    s(show),显示队列数据
    e(exit),退出队列
    a(add),添加数据到队列
    g(get),获取队列数据
    h(head),获取队列头数据
    a
    输入一个数：
    10
    10成功添加到队列
    s(show),显示队列数据
    e(exit),退出队列
    a(add),添加数据到队列
    g(get),获取队列数据
    h(head),获取队列头数据
    a
    输入一个数：
    20
    20成功添加到队列
    s(show),显示队列数据
    e(exit),退出队列
    a(add),添加数据到队列
    g(get),获取队列数据
    h(head),获取队列头数据
    a
    输入一个数：
    60
    60成功添加到队列
    s(show),显示队列数据
    e(exit),退出队列
    a(add),添加数据到队列
    g(get),获取队列数据
    h(head),获取队列头数据
    a20
    输入一个数：
    20
    队列已满
    s(show),显示队列数据
    e(exit),退出队列
    a(add),添加数据到队列
    g(get),获取队列数据
    h(head),获取队列头数据
    s
    arr[0]=10
    arr[1]=20
    arr[2]=60
    s(show),显示队列数据
    e(exit),退出队列
    a(add),添加数据到队列
    g(get),获取队列数据
    h(head),获取队列头数据
    a
    输入一个数：
    30
    队列已满
    s(show),显示队列数据
    e(exit),退出队列
    a(add),添加数据到队列
    g(get),获取队列数据
    h(head),获取队列头数据
    s
    arr[0]=10
    arr[1]=20
    arr[2]=60
    s(show),显示队列数据
    e(exit),退出队列
    a(add),添加数据到队列
    g(get),获取队列数据
    h(head),获取队列头数据
    g
    取出的数据是10
    s(show),显示队列数据
    e(exit),退出队列
    a(add),添加数据到队列
    g(get),获取队列数据
    h(head),获取队列头数据
    g
    取出的数据是20
    s(show),显示队列数据
    e(exit),退出队列
    a(add),添加数据到队列
    g(get),获取队列数据
    h(head),获取队列头数据
    s
    arr[2]=60
    s(show),显示队列数据
    e(exit),退出队列
    a(add),添加数据到队列
    g(get),获取队列数据
    h(head),获取队列头数据
    h
    队列头的数据是60
    s(show),显示队列数据
    e(exit),退出队列
    a(add),添加数据到队列
    g(get),获取队列数据
    h(head),获取队列头数据

### 4.完整代码 ###

/** * @author Manix * 环形队列测试类 */
    
    public class CircleArrayQueueDemo { 
        public static void main(String[] args) { 
    // 创建一个环形队列，maxSize设置说明，4，其队列的有效数据最大为3
            CircleQueue circleQueue = new CircleQueue(4);
    // 接收用户输入
            char key = ' ';
            Scanner scanner = new Scanner(System.in);
            boolean loop = true;
    // 输出一个菜单
            while (loop) { 
                System.out.println("s(show),显示队列数据");
                System.out.println("e(exit),退出队列");
                System.out.println("a(add),添加数据到队列");
                System.out.println("g(get),获取队列数据");
                System.out.println("h(head),获取队列头数据");
    // 接收输入的字符
                key = scanner.next().charAt(0);
                switch (key) { 
                    case 's':
                        circleQueue.showQueue();
                        break;
                    case 'a':
                        System.out.println("输入一个数：");
                        int value = scanner.nextInt();
                        circleQueue.addQueue(value);
                        break;
                    case 'g':
                        try { 
                            int res = circleQueue.getQueue();
                            System.out.printf("取出的数据是%d\n", res);
                        } catch (Exception e) { 
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'h':
                        try { 
                            int res = circleQueue.headQueue();
                            System.out.printf("队列头的数据是%d\n", res);
                        } catch (Exception e) { 
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'e':
                        loop = false;
                        scanner.close();
                        break;
                    default:
                        break;
                }
            }
            System.out.println("-----程序退出-----");
        }
    }
    
    /** * 环形队列类 * 构造器 * 判断是否已满、判断是否空、查看队列数据、显示队列的有效数据个数、入队列、出队列 */
    
    class CircleQueue { 
    // 数组的最大容量
        private final int maxSize;
    // front指向队列的第一个元素，初始值为0
        private int front;
    // rear指向队列的最后一个元素的后一个位置，空出一个空间作为约定，初始值为0
        private int rear;
    // 存放数据，模拟队列
        private final int[] arr;
    
        // 创建队列构造器
        public CircleQueue(int maxSize) { 
            this.maxSize = maxSize;
            front = 0;
            rear = 0;
            arr = new int[maxSize];
        }
    
        // 判断队列是否已满
        public boolean isFull() { 
            return (rear + 1) % maxSize == front;
        }
    
        // 判断队列是否为空
        public boolean isEmpty() { 
            return rear == front;
        }
    
        // 查看队列数据,显示队列所有数据
        public void showQueue() { 
            if (isEmpty()) { 
                System.out.println("队列为空，没有数据！");
                return;
            }
    // 从front开始遍历，注意遍历的元素个数
            for (int i = front; i < front + size(); i++) { 
                System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
            }
    
        }
    
        // 求出当前队列有效数据的个数
        public int size() { 
            return (rear + maxSize - front) % maxSize;
        }
    
        // 显示队列的头数据，注意不是取出数据
        public int headQueue() { 
            if (isEmpty()) { 
                throw new RuntimeException("队列是空的，没有数据！");
            }
            return arr[front];
        }
    
        // 添加数据到队列
        public void addQueue(int n) { 
            if (isFull()) { 
                System.out.println("队列已满");
                return;
            }
            arr[rear] = n;
            System.out.println(n + "成功添加到队列");
            // 将rear后移，这里必须考虑取模
            rear = (rear + 1) % maxSize;
        }
    
        // 从队列取出数据,，出队列
        public int getQueue() { 
            if (isEmpty()) { 
                throw new RuntimeException("队列为空，无法取出数据");
            }
            // 这里需要分析出front是指向队列的第一个元素
            // 1. 先把front对应的值保留到一个临时变量
            // 2. 将front后移，考虑取模
            // 3. 将临时保存的变量取回
            int value = arr[front];
            front = (front + 1) % maxSize;
            return value;
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzA0NDE1_size_16_color_FFFFFF_t_70_pic_center]: /images/20221014/bcbcc42ac7974136a3a324ecaa7eb854.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzA0NDE1_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221014/4791d85b1614443591620eb6c37400d0.png