数组实现队列【二】

一时失言乱红尘 2021-08-19 15:36 405阅读 0赞

【一】实现思路

基于上一篇文档[数组实现队列【一】][Link 1]加以改进，将浪费掉的空间用起来。

改进：

*  front头指针和rear尾指针的默认值为0，头指针指向头元素，尾指针指向尾元素的下一个位置；
 *  将数组最大长度的最后一个位置queue\[maxSize-1\]预留出来；
 *  判断队列为空的条件：rear==front;
 *  判断队列已满的条件：(rear+1)%maxSize==front;
 *  队列的有效个数:（rear+maxSize-front）%maxSize

【二】堆满的条件图解

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RoZV9CZXN0X0hhY2tlcg_size_16_color_FFFFFF_t_70][]

【三】代码实现

package array.queue;
    
    /*
     * front头指针和rear尾指针的默认值为0，头指针指向头元素，尾指针指向尾元素的下一个位置；
    	判断队列为空的条件：rear==front;
    		解释：当rear和front指向同一个区域的时候，证明队列为空
    	判断队列已满的条件：(rear+1)%maxSize==front;
    		解释：因为rear可能比front小也可能比front大，但是能够确定的就是rear指针的后一个为front时队列已满。
    	队列的有效个数:（rear+maxSize-front）%maxSize
     */
    class NewQueue {
    	private int maxSize;
    	private int front;
    	private int rear;
    	private int[] queue;
    	public NewQueue(int maxSize){
    		this.maxSize=maxSize;
    		queue=new int[maxSize];
    	}
    	//队列是否为空
    	public boolean isEmpty() {
    		return front==rear;
    	}
    	//队列是否已满
    	public boolean isFull() {
    		return (rear+1)%maxSize==front;
    	}
    	//添加值
    	public void addValue(int n) {
    		if(isFull()) {
    			System.out.println("队列已满，不能添加值");
    			return;
    		}
    		queue[rear]=n;
    		rear=(rear+1)%maxSize;
    	}
    	//取出值
    	public int getValue() {
    		if(isEmpty()) {
    			throw new RuntimeException("队列为空，不能取值");
    		}
    		int temp=queue[front];
    		front=(front+1)%maxSize;
    		return queue[front++];
    	}
    	//显示队列的头数据
    	public int headQueue() {
    		if(isEmpty()) {
    			throw new RuntimeException("队列为空");
    		}
    		return queue[front];
    	}
    	
    	//求当前队列的而有效数据
    	public int size() {
    		return (rear+maxSize-front)%maxSize;
    	}
    	
    	//遍历队列
    	public void showQueue() {
    		if(isEmpty()) {
    			System.out.println("队列为空");
    			return;
    			
    		}
    		for(int i=front;i<front+size();i++) {
    			System.out.printf("arr[%d]=%d\n",i%maxSize,queue[i%maxSize]);
    		}
    	}
    }

[Link 1]: https://blog.csdn.net/The_Best_Hacker/article/details/100544668
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RoZV9CZXN0X0hhY2tlcg_size_16_color_FFFFFF_t_70]: /images/20210811/323a5c52eb8e41b9bda125a6bc4292ea.png