Java 队列以及循环队列

小鱼儿 2023-10-09 13:45 42阅读 0赞

#### 文章目录 ####

*  队列以及循环队列
 *   *  队列
     *   *  队列的一个场景
         *  队列介绍
         *  队列图示
     *  循环队列
     *   *  循环队列介绍
         *  循环队列图示
         *  循环队列操作
         *  动画演示
         *  代码如下

## 队列以及循环队列 ##

### 队列 ###

#### 队列的一个场景 ####

比如我们在食堂打饭就是一个典型的队列使用场景，排在前面的同学先打着饭，然后先离开，后来的同学只能排在队尾，直到前面的同学打完饭才能轮到自己。  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAV1lTQ09ERVI_size_20_color_FFFFFF_t_70_g_se_x_16]

#### 队列介绍 ####

1）队列是一个**有序列表**，可以用**数组**或是**链表**来实现。  
2）遵循**先入先出**的原则。即：先存入队列的数据，要先取出；后存入的数据要后取出。  
3）队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

#### 队列图示 ####

队列可以用数组和链表来实现，在这里我们用数组来实现。  
1 2 3 4 5 6依次进队，出队的顺序也是1 2 3 4 5 6  
![在这里插入图片描述][a675cba4d4304773a7bc8b807cf170b8.gif]

### 循环队列 ###

#### 循环队列介绍 ####

循环队列其实就是对数组模拟队列的优化（在这里循环队列用数组模拟），充分利用数组，因此将数组看做是一个环形的。（通过**取模的方式**实现）

#### 循环队列图示 ####

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAV1lTQ09ERVI_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
循环队列只是在逻辑上的循环，在内存中并不是真正的循环（即图示中1 和 6 在内存中并不是连续的）。

#### 循环队列操作 ####

1）定义一个整型变量 head 指向队头。  
2）定义一个整型变量 rear指向队头。  
3）每添加一个元素， rear往后移动一个位置， rear**+ 1**；考虑在移动的过程中rear往后＋1，但是不能超过队列最大下标，所以需要进行取模操作，rear = (rear + 1) % element.length。  
4）每取出一个元素， head 往后移动一个位置， head **+1**，同样为了防止下标越界也要进行取模操作。  
5）每取出一个元素 head 往后移动一个位置，每添加一个元素， rear往后移动一个位置，循环操作，当 head == rear时，队列已满，可是一开始队列为空， head 和 rear也是指向同一个位置的，那么  head 和 rear相等就不能作为判满操作了。在这里为解决这个问题，我们选择浪费一个空间， rear指向的位置不存数据。当( rear\+1 ) % element.length ==  head 时队列已满。

#### 动画演示 ####

![在这里插入图片描述][b158fdd32923498d8a5fe5de5e3402dc.gif]

#### 代码如下 ####

public class CircleQueue {
        
        private int[] element;
        private int head;
        private int rear;
        private int max = 6;
    
        //构造函数
        public CircleQueue() {
        
            element = new int[max];
        }
    
        //判空
        private boolean isEmpty() {
        
            return head == rear;
        }
    
        //判满
        private boolean isFull() {
        
            return (rear + 1) % element.length == head;
        }
    
        //入队
        public boolean push(T value) {
        
            if (isFull()) {
        
                System.out.println("队列已满");
                return false;
            }
            element[rear] = value;
            rear = ++rear % element.length;
            return true;
        }
    
        //出队
        public boolean pop() {
        
            if (isEmpty()) {
        
                throw new RuntimeException("队列为空");
                return false;
            }
    
            head = ++head % element.length;
            return true;
        }
    
        //获得队头元素
        public int peek() {
        
            if (isEmpty()) {
        
    			throw new EmptyStackException();
            }
            return element[head];
        }
        
        //打印队列
        public int show() {
        
        	while (!isEmpty()) {
        
                System.out.print(element[head] + " ");
                head++;
            }
        }
    }

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAV1lTQ09ERVI_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/4959ea4d095741b7bfb1c0e1cd6feadd.jpg?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAV1lTQ09ERVI=,size_20,color_FFFFFF,t_70,g_se,x_16
[a675cba4d4304773a7bc8b807cf170b8.gif]: https://img-blog.csdnimg.cn/a675cba4d4304773a7bc8b807cf170b8.gif
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAV1lTQ09ERVI_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/2ee50a19ec974bb8a789a6cf8658382e.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAV1lTQ09ERVI=,size_20,color_FFFFFF,t_70,g_se,x_16
[b158fdd32923498d8a5fe5de5e3402dc.gif]: https://img-blog.csdnimg.cn/b158fdd32923498d8a5fe5de5e3402dc.gif