循环队列LoopQueue(Java)

╰+哭是因爲堅強的太久メ 2023-06-30 15:00 285阅读 0赞

# 循环队列LoopQueue #

为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。  
在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件是front=rear，而队列判满的条件是front=（rear+1)%MaxSize。

*  循环队列中只能存储MaxSize-1个元素，会有1个位置是空着的
 *  循环队列空的条件是rear=front
 *  循环队列满的条件是front=（rear+1)%MaxSize（为了防止溢出，所以需要进行取余计算）

**队列接口**

public interface Queue<E> {
        
    	
    	void enqueue(E e);//入队
    	E dequeue();//出队
    	E getFront();//获取队首元素
    	int getSize();//获取队列中元素个数
    	boolean isEmpty();//判断队列是否为空
    }

**循环队列LoopQueue**

public class LoopQueue<E> implements Queue<E> {
        
    
    	private E[] data;//队列数组
    	private int front, tail;//头节点，尾节点
    	private int size;//队列元素个数
    
    	public LoopQueue(int capacity) {
        
    		// TODO Auto-generated constructor stub
    		data = (E[]) new Object[capacity + 1];// 循环队列中浪费1个元素，所以存储capacity个元素创建数组时需要+1
    		front = 0;//头节点
    		tail = 0;//尾节点
    		size = 0;//队列元素个数
    	}
    
    	public LoopQueue() {
        
    		// TODO Auto-generated constructor stub
    		this(10);
    	}
    
    	public int getCapacity() {
        
    		return data.length - 1;
    	}
    
    	@Override
    	public void enqueue(E e) {
        
    		// TODO Auto-generated method stub
    		if ((tail + 1) % data.length == front) {
         // 循环队列满
    			resize(getCapacity() * 2);
    		}
    		data[tail] = e;
    		tail = (tail + 1) % data.length;
    		size++;
    	}
    
    	private void resize(int newcapacity) {
        
    		// TODO Auto-generated method stub
    		E[] newData = (E[]) new Object[newcapacity + 1];
    		for (int i = 0; i < size; i++) {
        
    			newData[i] = data[(i + front) % data.length];// 需要把data中的队列按照顺序复制给newData，并且防止i+front超过data.length
    		}
    		data = newData;
    		front = 0;
    		tail = size;
    	}
    
    	@Override
    	public E dequeue() {
        
    		// TODO Auto-generated method stub
    		if (isEmpty()) {
        
    			try {
        
    				throw new Exception("队列为空");
    			} catch (Exception e) {
        
    				// TODO Auto-generated catch block
    				e.printStackTrace();
    			}
    		}
    		E ret = data[front];
    		data[front] = null;// 防止data[front]闲逛
    		front = (front + 1) % data.length;
    		size--;
    		if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
         // 缩容 
    		//size == getCapacity() / 4 防止复杂度震荡  
    		// getCapacity() / 2 != 0 防止new数组长度为0
    			resize(getCapacity() / 2);
    		}
    		return ret;
    	}
    
    	@Override
    	public E getFront() {
        
    		// TODO Auto-generated method stub
    		if (isEmpty()) {
        
    			try {
        
    				throw new Exception("队列为空");
    			} catch (Exception e) {
        
    				// TODO Auto-generated catch block
    				e.printStackTrace();
    			}
    		}
    		return data[front];
    	}
    
    	@Override
    	public int getSize() {
        
    		// TODO Auto-generated method stub
    		return size;
    	}
    
    	@Override
    	public boolean isEmpty() {
        
    		// TODO Auto-generated method stub
    		return front == tail;// 循环队列为空
    	}
    
    	public String toString() {
        
    		StringBuilder res = new StringBuilder();
    		res.append(String.format("LoopQueue：size=%d,capacity=%d\n", size, getCapacity()));
    		res.append("front [");
    		for (int i = front; i != tail; i = (i + 1) % data.length) {
        
    			res.append(data[i]);
    			if ((i + 1) % data.length != tail)// 当前索引指向的元素不是队尾元素
    				res.append(",");
    		}
    		res.append("] tail");
    		return res.toString();
    	}
    }

**测试**

public class Test01 {
        
    	public static void main(String[] args) {
        
    		LoopQueue<Integer> loopqueue = new LoopQueue<>();
    		for (int i = 0; i < 10; i++) {
        
    			loopqueue.enqueue(i);
    			System.out.println(loopqueue);
    			if (i % 3 == 2) {
         //i=2,5,8的时候出队,测试缩容与扩容
    				loopqueue.dequeue();
    				System.out.println(loopqueue);
    			}
    		}
    	}
    }

**测试结果**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70]  
**循环队列与顺序队列对比**

*  当入队和出队元素逐渐增多时，循环队列的效率明显高于顺序队列
 *  循环队列与顺序队列效率所产生的差距，主要是由出队操作引起的（顺序队列出队需要队列每个元素向前移动一次，时间复杂度为O(n);循环队列出队操作只需要改变头节点的指向即可，时间复杂度为O(1)。）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200118134633757.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw==,size_16,color_FFFFFF,t_70