标签：返回   png   head   size   row   技术   maxsize   结构   循环队列   

队列

1.先进先出

2.可以使用数组或者链表来模拟队列

数组形式

单向队列

首先需要俩个指针，front和rear。front表示头指针，rear表示尾指针。

front = -1,rear = -1

front==rear：该队列为空

rear==Maxsize-1：该队列满了

但是单纯的这样设计的话，必然会导致曾经指针指向过的数据无法再次使用，所以需要模拟循环队列来使功能最大化使用。

循环队列

思路：对于单向队列缺陷的修正，front = 0, rear = 0

队列满：( rear+1 )%Maxsize == front

队列空：rear == front

队列中的有效个数：( Maxsize + rear - front ) % Maxsize

注意：

? rear指向的是数据的当前存储位置的下一个位置

? 循环队列（顺序队列）总存储量为N - 1，如果为n的话，队列满和队列空时的标志一样，这样会出现问题，所以我们会选择通过减少一个存储空间的方法来进行保存数据。

? 整个循环队列的工作中，会循环使用三个数组的存储空间，但是每轮满队列只用俩个存储空间。

下面为模拟的输出（Maxsize=3）

第一次满队列全部输出：a[0] a[1]

第二次(取出数据后又加入数据)满队列全部输出：a[1] a[2]

第三次满队列全部输出：a[2] a[0]

代码示例

class ArrayQueueD{
	//环形队列,少一个存储空间
	//rear指向的的是下一个存储位置
	private int front;
	private int rear;
	private int Maxsize;
	private int[] arr;
	public ArrayQueueD(int ArrMaxsize) {
		Maxsize = ArrMaxsize;
		arr = new int[Maxsize];
		front = 0;
		rear = 0;
	}
	public boolean isempty() {
		return front == rear;
	}
	public boolean isfull() {
		return (rear + 1) % Maxsize == front;
	}
	public void addQ(int num) {
		if(!isfull()) {
			arr[rear] = num;
			rear = (rear+1) % Maxsize;//rear指向的是下一个地址空间
			System.out.println("rear = "+ rear);
			
		}else {
			throw new RuntimeException("队列满");
		}
	}
	public int remove() {
		if(isempty()) {
			throw new RuntimeException("队列为空");
		}
		int value = arr[front];
		front = (front + 1) % Maxsize;
		System.out.println("处理后de front"+front);
		
		return value;
	}
	public void showQue() {
		if(isempty()) {
			throw new RuntimeException("队列为空");
		}
		for(int i = front;i < front + size();i++) {
			int i1 = i % Maxsize;
			System.out.println("arr["+i1+"]="+arr[i1]);
		}	
	}
	public int size() {//返回有效数据个数
		return (rear + Maxsize - front)%Maxsize;
	}
	public void showHead() {
		System.out.println("arr["+front+"]="+arr[front]);
	}	
}

Java数据结构——队列

标签：返回   png   head   size   row   技术   maxsize   结构   循环队列   

原文地址：https://www.cnblogs.com/waydmt/p/14763344.html