数据结构和算法之--数组队列、环形队列

数组队列:

1. 先进先出
2. 入列：新数据加入队列中（在队列后面加数据）
3. 出列：数据逐步离开队列（从头部开始离开）
4. front：记录队列中第一个元素的位置
5. rear：记录队列中的最后一个元素的下一个位置
6. 入列：rear不断向后移动
7. 出列：front不断向后移动
8. 判断队列是否满了：rear ==  maxSize - 1（单独方法）
9. 进行异常处理：队列的初始长度是否合法
10. 队列添加元素
11. 队列元素出列
12. 判断队列是否为空
13. 获取队列数组的长度
14. 获取队列中元素的个数
15. 查看第一个元素

16. public class FullQueueException extends RuntimeException{
        private static final long serialVersionUID = -4138898487109950739L;
    
        
        public FullQueueException(String message) {
            super(message);
        }
    }

17. public class EmptyQueueException extends RuntimeException {
        private static final long serialVersionUID = -6511950980580054433L;
    
        
        public EmptyQueueException(String message) {
            super(message);
        }
    }

    import com.colin.exception.EmptyQueueException;
    import com.colin.exception.FullQueueException;
    
    public class ArrayQueue {
        
        public ArrayQueue(int maxSize) {
            if (maxSize <= 0) {
                throw new IllegalArgumentException("队列长度不合理");
            }
            this.maxSize = maxSize;
            this.elementData = new String[maxSize];
        }
    
        
        private int front;
        
        private int rear;
        
        private int maxSize;
        
        private String[] elementData;
    
        
        private boolean isFull() {
            return this.rear == this.maxSize - 1;
        }
    
        
        public void add(String element) {
            if (isFull()) {
                throw new FullQueueException("队列已满，无法添数据");
            }
            this.elementData[this.rear++] = element;
        }
    
        
        private boolean isEmpty() {
            return this.front == this.rear;
        }
    
        
        public String get() {
            if (isEmpty()) {
                throw new EmptyQueueException("队列已空，无法出列");
            }
            String result = this.elementData[this.front];
            this.elementData[this.front++] = null;
            return result;
        }
    
        
        public int queueLength() {
            return this.maxSize;
        }
    
        
        public int elementCount() {
            return this.rear - this.front;
        }
    
        
        public String peekFirstElement() {
            return this.elementData[this.front];
        }
        @Override
        public String toString() {
            if (isEmpty()) {
                return "[]";
            }
            StringBuilder result = new StringBuilder("[");
            for (int i = this.front; ; i++) {
                result.append(this.elementData[i]);
                if (i == this.rear - 1) {
                    return result.append("]").toString();
                }
                result.append(", ");
            }
    
        }
    }

数组实现环形队列：

public class CircleArrayQueue {
    
    public CircleArrayQueue(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("队列长度不合理");
        }
        this.maxSize = maxSize;
        this.elementData = new String[maxSize];
    }

    
    private int front;
    
    private int rear;
    
    private int maxSize;
    
    private String[] elementData;

    
    public boolean isFull() {
        return (this.rear + 1) % this.maxSize == this.front;
    }

    
    private boolean isEmpty() {
        return this.front == this.rear;
    }

    
    public void add(String element) {
        if (isFull()) {
            throw new FullQueueException("队列已满，无法添数据");
        }
        this.elementData[this.rear] = element;
        this.rear = (this.rear + 1) % maxSize;
    }
    
    public String get() {
        if (isEmpty()) {
            throw new EmptyQueueException("队列已空，无法出列");
        }
        String result = this.elementData[this.front];
        this.elementData[this.front] = null;
        this.front = (this.front + 1) % maxSize;
        return result;
    }

    
    public int queueLength() {
        return this.maxSize;
    }

    
    public int elementCount() {
        return (this.rear - this.front + this.maxSize) % this.maxSize;
    }

    
    public String peekFirstElement() {
        return this.elementData[this.front];
    }


    @Override
    public String toString() {
        if (isEmpty()) {
            return "[]";
        }
        StringBuilder result = new StringBuilder("[");

        for (int i = this.front; ; i++) {
            result.append(this.elementData[i % this.maxSize]);
            if (i == this.elementCount() + this.front - 1) {
                return result.append("]").toString();
            }
            result.append(", ");
        }

    }
}