[数据结构与算法]Java第16天——循环队列

1 整除的作用.
2 想像操场跑道里放一队人, 循环的感觉就出来了.
3 为了区分空队列与满队列, 需要留一个空间. 相当于不允许首尾相连. 还是画个图吧, 否则容易进坑.
4 用链式结构, 空间的分配与回收由系统做, 用循环队列, 则是自己把控. 想像自己写的是操作系统, 从这个代码可以感受下内存的管理.
整数型队列代码

package datastructure.list;

/**
 * @author goudiyuan
 */

public class CircularqQuene {

	//声明队列的长度
	public final int TAOTAL_SPACE = 10;
	//存放元素的位置
	int data[];
	//队列头
	int head;
	//队列尾
	int tail;

	//构造方法
	public CircularqQuene() {
		data = new int[TAOTAL_SPACE];
		head = 0;
		tail = 0;
	}

	//入队
	public void enQueue(int paraValue) {
		if ((tail + 1) % TAOTAL_SPACE == head) {
			System.out.println("队列已满");
			return;
		}
		data[tail % TAOTAL_SPACE] = paraValue;
		tail++;
	}

	//出队
	public int deQueue() {
		if (head == tail) {
			System.out.println("队列中已经没有元素");
			return -1;
		}
		int resultValue = data[head % TAOTAL_SPACE];
		head++;
		return resultValue;
	}

	//重写父类toString方法
	public String toString() {
		String resultString = "";
		if (head == tail) {
			return "空队列";
		}
		for (int i = head; i < tail; i++) {
			resultString += data[i % TAOTAL_SPACE] + ",";
		}
		return resultString;
	}

	//主函数入口
	public static void main(String[] args) {
		CircularqQuene tempQueue = new CircularqQuene();
		System.out.println("初始化后，队列为：" + tempQueue.toString());

		for (int i = 0; i < 5; i++) {
			tempQueue.enQueue(i + 1);
		}
		System.out.println("入队后，队列为：" + tempQueue.toString());

		int tempValue = tempQueue.deQueue();
		System.out.println("将元素" + tempValue + "出队之后队列为" + tempQueue.toString());

		for (int i = 0; i < 6; i++) {
			tempQueue.enQueue(i + 10);
			System.out.println("入队后，队列为：" + tempQueue.toString());
		}

		for (int i = 0; i < 3; i++) {
			tempValue = tempQueue.deQueue();
			System.out.println("将元素" + tempValue + "出队之后队列为" + tempQueue.toString());
		}

		for (int i = 0; i < 6; i++) {
			tempQueue.enQueue(i + 100);
			System.out.println("入队后，队列为：" + tempQueue.toString());

		}
	}

}

运行结果

初始化后，队列为：空队列
入队后，队列为：1,2,3,4,5,
将元素1出队之后队列为2,3,4,5,
入队后，队列为：2,3,4,5,10,
入队后，队列为：2,3,4,5,10,11,
入队后，队列为：2,3,4,5,10,11,12,
入队后，队列为：2,3,4,5,10,11,12,13,
入队后，队列为：2,3,4,5,10,11,12,13,14,
队列已满
入队后，队列为：2,3,4,5,10,11,12,13,14,
将元素2出队之后队列为3,4,5,10,11,12,13,14,
将元素3出队之后队列为4,5,10,11,12,13,14,
将元素4出队之后队列为5,10,11,12,13,14,
入队后，队列为：5,10,11,12,13,14,100,
入队后，队列为：5,10,11,12,13,14,100,101,
入队后，队列为：5,10,11,12,13,14,100,101,102,
队列已满
入队后，队列为：5,10,11,12,13,14,100,101,102,
队列已满
入队后，队列为：5,10,11,12,13,14,100,101,102,
队列已满
入队后，队列为：5,10,11,12,13,14,100,101,102,

由于后面要用到字符串匹配，所以就把队列的数据类型换成了char?

代码

package datastructure.list;

/**
 * @author goudiyuan
 */
public class CirclecharQueue {

	// 队列长度
	public static final int TOTAL_SPACE = 10;
	// 队列存放数据的地方
	char[] data;
	// 头指针
	int head;
	// 尾指针
	int tail;

	// 构造方法
	public CirclecharQueue() {
		data = new char[TOTAL_SPACE];
		head = 0;
		tail = 0;
	}

	// 入队
	public void enqueue(char paraValue) {
		if ((tail + 1) % TOTAL_SPACE == head) {
			System.out.println("队列已经满了.");
			return;
		}

		data[tail % TOTAL_SPACE] = paraValue;
		tail++;
	}

	// 出队
	public char dequeue() {
		if (head == tail) {
			System.out.println("队列中已经没有元素了");
			return '\0';
		}

		char resultValue = data[head % TOTAL_SPACE];

		head++;

		return resultValue;
	}

	// 重写父类toString方法
	public String toString() {
		String resultString = "";

		if (head == tail) {
			return "empty";
		}

		for (int i = head; i < tail; i++) {
			resultString += data[i % TOTAL_SPACE] + ", ";
		}

		return resultString;
	}

	// 函数入口
	public static void main(String args[]) {
		CirclecharQueue tempQueue = new CirclecharQueue();
		System.out.println("初始化后，队列为 " + tempQueue.toString());

		for (char i = '0'; i < '5'; i++) {
			tempQueue.enqueue(i);
		}
		System.out.println("入队后，队列为: " + tempQueue.toString());

		char tempValue = tempQueue.dequeue();
		System.out.println("将元素 " + tempValue + "出队后，队列为: " + tempQueue.toString());

		for (char i = 'a'; i < 'f'; i++) {
			tempQueue.enqueue(i);
			System.out.println("入队后，队列为: " + tempQueue.toString());
		}

		for (int i = 0; i < 3; i++) {
			tempValue = tempQueue.dequeue();
			System.out.println("将元素 " + tempValue + "出队后，队列为: " + tempQueue.toString());
		}

		for (char i = 'A'; i < 'F'; i++) {
			tempQueue.enqueue(i);
			System.out.println("入队后，队列为: " + tempQueue.toString());
		}
	}

}

运行结果

初始化后，队列为 空
入队后，队列为: 0, 1, 2, 3, 4,?
将元素 0出队后，队列为: 1, 2, 3, 4,?
入队后，队列为: 1, 2, 3, 4, a,?
入队后，队列为: 1, 2, 3, 4, a, b,?
入队后，队列为: 1, 2, 3, 4, a, b, c,?
入队后，队列为: 1, 2, 3, 4, a, b, c, d,?
入队后，队列为: 1, 2, 3, 4, a, b, c, d, e,?
将元素 1出队后，队列为: 2, 3, 4, a, b, c, d, e,?
将元素 2出队后，队列为: 3, 4, a, b, c, d, e,?
将元素 3出队后，队列为: 4, a, b, c, d, e,?
入队后，队列为: 4, a, b, c, d, e, A,?
入队后，队列为: 4, a, b, c, d, e, A, B,?
入队后，队列为: 4, a, b, c, d, e, A, B, C,?
队列已经满了.
入队后，队列为: 4, a, b, c, d, e, A, B, C,?
队列已经满了.
入队后，队列为: 4, a, b, c, d, e, A, B, C,?

?