数据结构之队列

小鱼儿 2021-12-21 21:25 219阅读 0赞

**队列**的**顺序存储**结构实现

public class Queue<E> {
        private Object[] data = null;
        private int maxSize;   //队列容量
        private int front;  // 队列头,允许删除
        private int rear;   //队列尾,允许插入
        
        public Queue() {  //默认的空构造函数队列容量为10
            this(10);
        }
        /**
         * 构造函数
         * @param initialSize 队列初始化大小
         */
        public Queue(int initialSize) {
            if (initialSize >= 0) {
                this.maxSize = initialSize;
                data = new Object[initialSize];
            }else {
                throw new RuntimeException("初始化大小不能小于0:"+initialSize);
            }
        }
        
        /* 判断是否为空 */
        public boolean empty(){
            return rear==front?true:false;
        }
        
        /* 插入 */
        public boolean add(E e){
            if (rear == maxSize) {  //如果尾等于容量上限
                //方案一,超过抛异常
                /*throw new RuntimeException("队列已满,无法插入新的元素");*/
                //方案二,直接将数组容量翻倍
                Object[] temp = Arrays.copyOf(data, maxSize*2);
                maxSize = maxSize*2;
                data = temp;
                data[rear++] = e;
                return true;
            }else {
                data[rear++] = e;
                return true;
            }
        }
        
        /**
         * 返回队首元素,但不删除
         */
        public E peek(){
            if (empty()) {
                throw new RuntimeException("空队列异常！");
            }else {
                return (E) data[front];
            }
        }
        
        /**
         * 出队,返回队首并删除
         */
        public E poll(){
            if (empty()) {
                throw new RuntimeException("空队列异常！");
            }else {
                E value = (E) data[front];
                data[front++] = null;
                //完善,上面出队列后没有把其他的往前移动一位
                int i = 0;  //待赋值的当前位置
                while (i<rear) {  //这个位置一定比末位少一(因为往前移一位)
                    data[i] = data[i+1];  //给当前位置赋值
                    i++;  //下标移动到下一位
                }
                front--;  //往前移动一位要把首位的索引减一
                rear--;
                return value;
            }
        }
        
        //队列长度
        public int length(){
            return rear-front;
        }
        
        //打印链表
        public String toString(){
            return Arrays.toString(data);
        }
    }

测试

public static void main(String[] args) {
            Queue<String> queue = new Queue(5);
            queue.add("Str111");
            queue.add("Str222");
            queue.add("Str333");
            queue.add("Str444");
            queue.add("Str555");
            queue.add("Str666");
            queue.add("Str777");
            System.out.println("出队列(首):"+queue.poll());
            System.out.println("队列首位索引:"+queue.front);
            System.out.println("队列末位索引:"+queue.rear);
            System.out.println(queue.toString());
        }

结果

![1208477-20190305111411545-1411537751.png][]

参考:[https://www.cnblogs.com/CherishFX/p/4608880.html][https_www.cnblogs.com_CherishFX_p_4608880.html]

转载于:https://www.cnblogs.com/aeolian/p/10475506.html

[1208477-20190305111411545-1411537751.png]: /images/20211220/7467c0218fe1495d888d0653719561bf.png
[https_www.cnblogs.com_CherishFX_p_4608880.html]: https://www.cnblogs.com/CherishFX/p/4608880.html