循环队列

1. 回顾队列的知识

• 队列是先进先出
• 我们用的是一组地址连续的储存单元依次存放从对头到队尾的元素。
• 设了两个指针分别指向队头和队尾。
• 插入：尾指针增1，删除：头指针增1
• 头指针始终指向队头元素，尾指针始终指向队尾元素的下一个位置。
• 如图：

---

***

2. 循环队列定义

• 假设，队列空间大小为6
• 当队列处于（d）状态时，Q.front == Q.rear，判为队满。
• 浪费了很多空间
• 由此产生了循环队列
• 对空：front = rear
• 队满：(rear+1)%M == front ,M为分配的大小

3. C语言下的循环队列

3.1 定义及初始化

#define MAX_QSIZE = 100
typedef struct {
	QElemType *base;
	int front;
	int rear;
}SqCircleQueue;
Status InitSCQ(SqCircleQueue &Q) {
	// 构造一个空队列
	Q.base = (QElemType*)malloc(MAX_QSIZE*sizeof(QElemType));
	if(!Q.base) return -2;
	Q.front = Q.rear = 0;
	
	return OK;
} // of InitSCQ

3.2 返回循环队列中的元素个数

int SCQLength(SqCircleQueue &Q) {
	// 返回循环队列中的元素个数 
	return (Q.rear-Q.front+MAX_QSIZE)%MAX_QSIZE;
} // of SCQLength

3.3 入队

Status EnSCQ(SqCircleQueue &Q,QElemType e) {
	// 入队
	if((Q.rear+1)%MAX_QSIZE == Q.front) return ERROR; // 队满
	
	Q.base[Q.rear] = e;
	Q.rear = (Q.rear+1)%MAX_QSIZE;
	
	return OK; 
} // of EnSCQ

3.4 出队

Status DeSCQ(SqCircleQueue &Q, QElemType &e) {
	//出队
	if(Q.front == Q.rear) return ERROR; // 队空
	
	e = Q.base[Q.front];
	Q.front = (Q.front+1)%MAX_QSIZE;
	
	return OK; 
} // of DeSCQ

---

4. Java语言下的循环队列

4.1 构造一个循环队列

	/**
	 * 循环队列的大小
	 */
	public static final int SIZE = 100;

	/** 工作空间 */
	int[] data;

	/** 对头 */
	int head;

	/** 队尾 */
	int tail;

	/** 构造一个循环队列 */
	SqCircleQueue() {
		data = new int[SIZE];
		head = tail = 0;
	}

4.2 入循环队

	/**
	 * 入循环队
	 * 
	 * @param elem
	 * @return true or false
	 */
	public boolean enSqCircleQueue(int elem) {

		// 队满
		if ((tail + 1) % 100 == head) {
			System.out.println("CircleQueue is full");
			return false;
		}

		data[tail % SIZE] = elem;
		tail++;

		return true;
	}// of enSCQ

4.3 出循环队

	/**
	 * 出循环队
	 * 
	 * @return 删除的元素
	 */
	public int deSqCircleQueue() {

		// 队空
		if (head == tail) {
			System.out.println("Circle Queue is Empty");
			return -1;
		}

		int tempValue = data[head % SIZE];
		head++;

		return tempValue;
	}// of deSCQ

4.4 循环队列实际元素个数

	/**
	 * 循环队列实际元素个数
	 * 
	 * @return 元素个数
	 */
	public int lengthOfCircleQueue() {
		return (tail - head + SIZE) % SIZE;
	}

4.5 SqCircleQueue类

package datastructure.queue;

/**
 * 循环队列,顺序表
 * 
 * @author NoBug
 * @version 2.0
 * @time 2022/3/10
 * 
 */
public class SqCircleQueue {

	/**
	 * 循环队列的大小
	 */
	public static final int SIZE = 100;

	/** 工作空间 */
	int[] data;

	/** 对头 */
	int head;

	/** 队尾 */
	int tail;

	/** 构造一个循环队列 */
	SqCircleQueue() {
		data = new int[SIZE];
		head = tail = 0;
	}

	/**
	 * 入循环队
	 * 
	 * @param elem
	 * @return true or false
	 */
	public boolean enSqCircleQueue(int elem) {

		// 队满
		if ((tail + 1) % 100 == head) {
			System.out.println("CircleQueue is full");
			return false;
		}

		data[tail % SIZE] = elem;
		tail++;

		return true;
	}// of enSCQ

	/**
	 * 出循环队
	 * 
	 * @return 删除的元素
	 */
	public int deSqCircleQueue() {

		// 队空
		if (head == tail) {
			System.out.println("Circle Queue is Empty");
			return -1;
		}

		int tempValue = data[head % SIZE];
		head++;

		return tempValue;
	}// of deSCQ

	/**
	 * 循环队列实际元素个数
	 * 
	 * @return 元素个数
	 */
	public int lengthOfCircleQueue() {
		return (tail - head + SIZE) % SIZE;
	}

	/**
	 * toString
	 */
	public String toString() {
		String resultString = "";
		if (head == tail) {
			return "Empty";
		}
		for (int i = head; i < tail; i++) {
			resultString += data[i % SIZE] + " ";
		}

		return resultString;
	}

	public static void main(String[] args) {
		SqCircleQueue sqcirclequeue = new SqCircleQueue();

		// test1
		System.out.println(sqcirclequeue.toString());
		System.out.println(sqcirclequeue.lengthOfCircleQueue());

		// test2
		sqcirclequeue.enSqCircleQueue(1);
		sqcirclequeue.enSqCircleQueue(2);
		sqcirclequeue.enSqCircleQueue(6);
		sqcirclequeue.enSqCircleQueue(8);
		sqcirclequeue.enSqCircleQueue(5);
		System.out.println(sqcirclequeue.toString());
		System.out.println(sqcirclequeue.lengthOfCircleQueue());

		// test3
		sqcirclequeue.deSqCircleQueue();
		System.out.println(sqcirclequeue.toString());
		System.out.println(sqcirclequeue.lengthOfCircleQueue());
	}

}

4.6 输出样例

Empty
0
1 2 6 8 5 
5
2 6 8 5 
4

5. 泛型SqCircleQueue

package datastructure.queue;

/**
 * 循环队列,顺序表
 * 
 * @author NoBug
 * @version 2.0
 * @time 2022/3/10
 * 
 */
public class Queue<T> {

	/**
	 * 循环队列的大小
	 */
	public static final int SIZE = 100;

	/** 工作空间 */
	Object[] data;

	/** 对头 */
	int head;

	/** 队尾 */
	int tail;

	/** 构造一个循环队列 */
	Queue() {
		data = new Object[SIZE];
		head = tail = 0;
	}

	/**
	 * 入循环队
	 * 
	 * @param elem
	 * @return true or false
	 */
	public boolean enSqCircleQueue(T elem) {

		// 队满
		if ((tail + 1) % 100 == head) {
			System.out.println("CircleQueue is full");
			return false;
		}

		data[tail % SIZE] = elem;
		tail++;

		return true;
	}// of enSCQ

	/**
	 * 出循环队
	 * 
	 * @return 删除的元素
	 */
	public T deSqCircleQueue() {

		// 队空
		if (head == tail) {
			System.out.println("Circle Queue is Empty");
			return null;
		}

		@SuppressWarnings("unchecked")
		T tempValue = (T) data[head % SIZE];
		head++;

		return tempValue;
	}// of deSCQ

	/**
	 * 循环队列实际元素个数
	 * 
	 * @return 元素个数
	 */
	public int lengthOfCircleQueue() {
		return (tail - head + SIZE) % SIZE;
	}

	/**
	 * toString
	 */
	public String toString() {
		String resultString = "";
		if (head == tail) {
			return "Empty";
		}
		for (int i = head; i < tail; i++) {
			resultString += data[i % SIZE] + " ";
		}

		return resultString;
	}

	public static void main(String[] args) {
		Queue<Character> queue = new Queue<Character>();

		// test1
		System.out.println(queue.toString());
		System.out.println(queue.lengthOfCircleQueue());

		// test2
		queue.enSqCircleQueue('a');
		queue.enSqCircleQueue('b');
		queue.enSqCircleQueue('c');
		queue.enSqCircleQueue('d');
		queue.enSqCircleQueue('e');
		System.out.println(queue.toString());
		System.out.println(queue.lengthOfCircleQueue());

		// test3
		queue.deSqCircleQueue();
		System.out.println(queue.toString());
		System.out.println(queue.lengthOfCircleQueue());
	}

}

Empty
0
a b c d e 
5
b c d e 
4