数据结构（java语言描述）-- 队列的循环数组实现

迷南。 2022-08-12 20:29 301阅读 0赞

首先了解下队列的概念：   
**队列**（Queue），使用时插入在队尾进行而删除则在队头进行的线性表。

（1）允许删除的一端称为队头（Front）.

（2）允许插入的一端称为队尾（Rear）。

（3）当队列中没有元素时称为空队列。

（4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。

**队列模型：**

![Center][]

### 循环队列的存储结构： ###

![Center 1][]

为什么要用循环数组来实现队列呢？原因是，如果队列中的元素个数满了，这时，队尾指针指向数组最后一个下标，而下一次再入队就会存在一个不存在的位置。然而，队列中也许只存在几个元素，因为若干元素可能已经出队了。像栈一样，即时在有许多操作的情况下队列也常常不是很大。  
简单的解决办法是，只要队头和队尾指针到达数组的尾端，它就又绕回到开头。这就叫做循环数组（circular array）。

下面给出队列的循环数组的实现代码

/**
     * 队列的循环数组实现
     * @author lenovo
     *
     */
    public class TestQueue {
    
    	private static final int DEFAULT_CAPACITY = 10;
    	private int[] arr;
    	private int front;
    	private int back;
    	private int currentSize;
    	
    	public TestQueue(int val1, int val2) {
    		arr = new int[DEFAULT_CAPACITY];
    		front = arr.length-2;
    		back = arr.length - 1;
    		this.arr[front] = val1;
    		this.arr[back] = val2;
    		
    		currentSize = 2;
    	}
    	
    	public int size() {
    		return currentSize;
    	}
    	
    	public boolean isEmpty(){  
            return size()== 0;  
        }  
           
    	/**
    	 * 从队尾入列
    	 * @param rear 要插入的队尾元素 
    	 */
    	public void enqueue(int rear) {
    		back ++;
    		if (back == arr.length) {
    			back = 0;
    		}
    		
    		currentSize ++;				
    		arr[back] = rear;		
    	}
    	
    	/**
    	 * 从队头出列
    	 * @return 返回列的下标
    	 */
    	public int dequeue() {		
    		currentSize --;
    		front ++; 
    		if (front == arr.length) {
    			front = 0;
    		}		
    		return front;		
    	}
    	
    	/**
    	 * 测试代码
    	 * @param args
    	 */
    	public static void main(String[] args) {
    		TestQueue tq = new TestQueue(2, 4);	
    		
    		tq.enqueue(1);
    System.out.println("第一次指向：" + tq.arr[tq.back] + "\t返回：" + tq.back);
    		tq.enqueue(3);
    System.out.println("第二次指向：" + tq.arr[tq.back] + "\t返回：" + tq.back);
    
    		tq.dequeue();
    		System.out.println("dequeue后第一次返回:" + tq.front);
    		tq.dequeue();
    		System.out.println("dequeue后第二次返回:" + tq.front);
    		tq.dequeue();
    		System.out.println("dequeue后第三次返回:" + tq.front);
    System.out.println("3次后大小：" + tq.size());
    		tq.dequeue();
    		System.out.println("dequeue后第四次返回:" + tq.front);
    System.out.println("dequeue后第四次指向:" + tq.arr[tq.front]);
    System.out.println("四次后大小：" + tq.size());
    
    		//检测数组大小为0时，调用isEmpty()
    		if (tq.currentSize == 0) {
    			System.out.println(tq.isEmpty());
    		}
    		
    	}
    
    }

测试结果:

![Center 2][]

若有任何问题，欢迎提出，虚心受教(●'◡'●)

[Center]: /images/20220810/f50c6e2d76704ad181ccd62c100dfea5.png
[Center 1]: /images/20220810/a50fa1870a0941a8bb5fbda717ea76f1.png
[Center 2]: /images/20220810/cc4f3362e2104448be488b9a7dcc66ea.png