Java数据结构与算法之队列

偏执的太偏执、 2022-08-09 15:52 168阅读 0赞

队列的知识点也不是很复杂，所以直接上代码

package com.wayne.QueueX;
    
    /* * 1， 队列特性：先进先出。 * 2， 折断的序列：队列中的数据项存在数组两个不同的序列中。 * 3， 队列的两个基本操作： * a) 插入一个数据项：把数据项放入队尾 * b) 删除一个数据项：移除队头数据 * 4， 队列的效率 * 队列的插入和移除数据项的时间复杂度均为O(1). */
    public class MyQueue { 
        /* * 队列需要有五个元素： * 队列的最大长度maxSize,队列的实际类型queArray, * 队头索引front,队尾索引rear,队列的实际个数nItems */
        private int maxSize;
        private int[] queArray;
        private int front;
        private int rear;
        private int nItems;
    
        /** * 初始化一个长度为length的空队列 * @param length 队列的预计长度 */
        public MyQueue(int length){
            maxSize = length;
            queArray = new int[maxSize];
            front = 0;//队头删除元素
            rear = -1;//队尾插入元素
            nItems=0;
        }
    
        /** * 向队尾插入一个元素 * @param i 待插入的元素 */
        public void insert(int i){
            if(rear == maxSize -1)
                rear = -1;
            queArray[++rear] = i;
            nItems++;
        }
    
        /** * 从队头删除一个元素 * @return 返回移除的元素 */
        public int remove(){
            int temp = queArray[front++];
            if(front == maxSize)
                front = 0;
            nItems--;
            return temp;
        }
    
        /** * 判断队列是否为空， * @return 如果为空，则返回true;如果不为空，则返回false; */
        public boolean isEmpty(){
            return nItems == 0;
        }
    
        /** * 判断队列是否满 * @return 如果为满，则返回true；如果不满，则返回false; */
        public boolean isFull(){
            return nItems == maxSize;
        }
    
        /** * 获取队列的实际长度 * @return 返回队列的实际长度 */
        public int size()
        {
            return nItems;
        }
    }

测试用例

package com.wayne.test;
    
    import com.wayne.QueueX.MyQueue;
    
    public class MyQueueTest {
    
        public static void main(String[] args) {
            MyQueue myQueue = new MyQueue(5);
    
            myQueue.insert(4);
            myQueue.insert(5);
            myQueue.insert(2);
            myQueue.insert(1);
            myQueue.insert(6);
            myQueue.insert(7);
            myQueue.insert(8);
            myQueue.insert(9);
    
            System.out.println("the length of the array is "+myQueue.size());
    
            while(!myQueue.isEmpty())
            {
                System.out.println(myQueue.remove());
            }
    
        }
    }