数据结构-循环队列实现

港控/mmm° 2023-10-11 18:13 58阅读 0赞

这里使用顺序存储的方式实现循环队列。如果实现循环队列，此时需要废弃掉一个存储单元，例如长度为5的循环队列只能存储4个元素。

public class CircleQueue {
        
    
        private int rear;//队尾指针
    
        private int front;//队头指针
    
        private int[] elements;
    
        private int maxsize;
    
        public CircleQueue(int size){
        
            elements = new int[size];
            maxsize = size;
            rear = front = 0;
        }
    
        //判断循环队列是否已满，因为是循环队列，所以头指针和尾指针是随时变化的。
        //在循环队列中，front指向最先入队的元素下边，而rear指向最后入队的元素的下一个位置，rear指向的是一个空位置。
        //初始状态下rear == front == 0
        public boolean isFull(){
        
            return (rear + 1) % maxsize == front; //rear + 1后的下标对数组最大长度取模，判断结果是否等于front。
        }
    
        //循环队列判空的条件是 rear 和 front 是否相等。而不是判断 rear是否为0.
        public boolean isEmpty(){
        
            return rear == front;
        }
    
        //元素入队
        public void push(int data){
        
            if (isFull()){
        
                System.out.println("队列已满，无法入队");
                return;
            }
            //添加元素后要移动队尾指针，队尾指针该如何移动？不能只是简单的++，应该由当前值+1对数据取模
            elements[rear] = data;
            rear = (rear + 1) % maxsize;
        }
    
        //元素出队
        public Integer pop(){
        
            if (isEmpty()){
        
                System.out.print("队列已空！！！");
                return null;
            }
            Integer data = elements[front];
            //移动队头指针
            front = (front + 1) % maxsize;
            return data;
        }
    
        public static void main(String[] args) {
        
            CircleQueue circleQueue = new CircleQueue(5);
            circleQueue.push(1);
            circleQueue.push(2);
            circleQueue.push(3);
            circleQueue.push(4);
            circleQueue.push(5);
            circleQueue.push(6);
    
            System.out.println(circleQueue.pop());
            System.out.println(circleQueue.pop());
            System.out.println(circleQueue.pop());
            System.out.println(circleQueue.pop());
            System.out.println(circleQueue.pop());
    
            circleQueue.push(10);
            circleQueue.push(11);
            circleQueue.push(12);
            circleQueue.push(13);
            circleQueue.push(14);
            circleQueue.push(15);
    
            System.out.println(circleQueue.pop());
            System.out.println(circleQueue.pop());
            System.out.println(circleQueue.pop());
    
            circleQueue.push(16);
            circleQueue.push(17);
            circleQueue.push(18);
            System.out.println("===========");
            System.out.println(circleQueue.pop());
            System.out.println(circleQueue.pop());
            System.out.println(circleQueue.pop());
            System.out.println(circleQueue.pop());
            System.out.println(circleQueue.pop());
            System.out.println(circleQueue.pop());
    
        }
    
    }

注意四个地方：

1.循环队列的判空条件 ：rear == front  
2.循环队列的判满条件：(rear + 1) % maxsize == front  
3.元素入队时，移动队尾指针 rear = (rear + 1) % maxsize  
4.元素出队时,移动队头指针 front = (front + 1) % maxsize

对一个数取余，结果只能是从0到这个数-1，例如对5取余结果只能是0,1,2,3,4。这里为什么是rear+1后取余，因为rear指向的是一个空地址，假设一个长度为5的队列已经存了4个元素，此时rear指向4，如果继续插入元素 4+1 % 5 = 0 == front ， 表示队列已满，如果不加1, 4 % 5 = 4,将新元素插入4这个位置，此时移动rear指针，rear = (rear + 1) % maxsize = 0,此时rear == front，此时满足了队列为空的条件，但是此时队列是满的。不满足循环队列的要求了。