【数据结构】队列

朱雀 2020-10-24 17:06 769阅读 0赞

队列（Queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

## 特点 ##

先进先出（First In First Out）的线性表。

## Java实现 ##

/** * The Apache License 2.0 * Copyright (c) 2018 sep6th */
    
    public class Queue { 
    
        private long[] arr;
        //有效数据个数
        private int elements;
        //队头
        private int front;
        //队尾
        private int end;
    
        public Queue() {
            arr = new long[10];
            elements = 0;
            front = 0;
            end = -1;
        }
    
        public Queue(int maxSize) {
            arr = new long[maxSize];
            elements = 0;
            front = 0;
            end = -1;
        }
    
        /** * 从队尾添加数据 */
        public void insert(long value) {
            arr[++end] = value;
            elements++;
        }
    
        /** * 删除数据，从队头删除 */
        public long remove() {
            elements--;
            return arr[front++];
        }
    
        /** * 查看数据，从队头查看 */
        public long peek() {
            return arr[front];
        }
    
        /** * 判断是否为空 */
        public boolean isEmpty() {
            return elements == 0;
        }
    
        /** * 判断是否满了 */
        public boolean isFull() {
            return elements == arr.length;
        }
    
    
    }

测试

/** * The Apache License 2.0 * Copyright (c) 2018 sep6th */
    
    public class TestQueue { 
    
        public static void main(String[] args) {
    
            Queue q = new Queue(3);
            q.insert(12);
            q.insert(23);
            q.insert(34);
    
            System.out.println(q.isFull());
            System.out.println(q.isEmpty());
            System.out.println(q.peek());
    
        }
    
    }

console

true
    false
    12

循环队列

/** * The Apache License 2.0 * Copyright (c) 2018 sep6th */
    
    public class CycleQueue { 
    
        private long[] arr;
        //有效数据的大小
        private int elements;
        //队头
        private int front;
        //队尾
        private int end;
    
        /** * 默认构造方法 */
        public CycleQueue() {
            arr = new long[10];
            elements = 0;
            front = 0;
            end = -1;
        }
    
        /** * 带参数的构造方法，参数为数组的大小 */
        public CycleQueue(int maxsize) {
            arr = new long[maxsize];
            elements = 0;
            front = 0;
            end = -1;
        }
    
        /** * 添加数据,从队尾插入 */
        public void insert(long value) {
            if(end == arr.length - 1) {
                end = -1;
            }
            arr[++end] = value;
            elements++;
        }
    
        /** * 删除数据，从队头删除 */
        public long remove() {
            long value = arr[front++];
            if(front == arr.length) {
                front = 0;
            }
            elements--;
            return value;
        }
    
        /** * 查看数据，从队头查看 */
        public long peek() {
            return arr[front];
        }
    
        /** * 判断是否为空 */
        public boolean isEmpty() {
            return elements == 0;
        }
    
        /** * 判断是否满了 */
        public boolean isFull() {
            return elements == arr.length;
        }
    
    }