队列

队列

队列是一个有序列表，可以用数组和链表来实现。
遵循先进先出原则。

1、数组模拟队列

public class ArrayQueueDemo {
	public static void main(String[] args) {
		ArrayQueue queue = new ArrayQueue(3);
		char key = ' ';
		Scanner in = new Scanner(System.in);
		boolean loop = true;
		while(loop) {
			System.out.println("s:显示队列   a:添加数据到队列   g:取出数据  h:查看队列头  e:退出");
			System.out.println("请输入要执行的操作：");
			key = in.next().charAt(0);
			switch (key) {
			case 's':
				queue.showQueue();
				System.out.println();
				break;
			case 'a':
				System.out.print("请输入一个数字：");
				int num = in.nextInt();
				queue.addQueue(num);
				break;
			case 'g':
				try {
					int num1 = queue.getQueue();
					System.out.println("取出的数据为："+ num1);
				} catch (Exception e) {
					// TODO Auto-generated catch block
					e.getMessage();
				}
				break;
			case 'h':
				try {
					int head = queue.headQueue();
					System.out.println("队列头为："+ head);
				} catch (Exception e) {
					// TODO Auto-generated catch block
					e.getMessage();
				}
				break;
			case 'e':
				loop = false;
				System.out.println("程序退出");
			default:
				break;
			}		
		}
	}
}

// 使用数组模拟队列---编写一个ArrayQueue类
class ArrayQueue {
	private int maxSize;// 表示数组的最大容量
	private int front;// 队列头
	private int rear;// 队列尾
	private int[] arr;// 用于存放数据，模拟队列
	
	// 创建队列的构造器
	public ArrayQueue(int maxSize){
		this.maxSize = maxSize;
		this.arr = new int [maxSize];
		this.front = -1;// 指向队列头部的前一个位置
		this.rear = -1;// 指向队列尾部
	}
	
	// 判断队列是否满
	public boolean isFull() {
		return rear == maxSize-1;
	}
		
	// 判断队列是否为空
	public boolean isEmpty() {
		return front == rear;
	}
	
	// 添加数据到队列，入队列
	public void addQueue(int num) {
		// 判断队列是否已满
		if(isFull()) {
			System.out.println("队列已满！");
			return ;
		}else {
			rear++; // 让rear后移
			arr[rear]=num;
		}
	}
	
	// 获取队列数据，出队列
	public int getQueue() {
		// 判断队列是否为空
		if(isEmpty()) {
			throw new RuntimeException("队列为空！");// 抛出异常
		}
		front++;
		return arr[front];
	}
	
	// 显示队列所有数据
	public void showQueue() {
		// 遍历
		if(isEmpty()) {
			System.out.println("队列为空");
		}else {
			for(int i=0;i<arr.length;i++) {
				System.out.print(arr[i]+" ");
			}
		}
	}
	
	// 显示队列的头数据
	public int headQueue() {
		if(isEmpty()) {
			throw new RuntimeException("队列为空！");
		}
		return arr[front+1];
	}	
}

2、环形队列

1.目前数组使用一次之后就不能再使用了，没有达到复用的效果。
2.将数组使用算法，改进成为一个环形队列   取模%

循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是”空”还是”满”。
解决这个问题的方法至少有三种：
① 另设一布尔变量以区别队列的空和满；
② 少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满

class CircleQueue {
	private int maxSize;// 表示数组的最大容量
	private int front;// 队列头
	private int rear;// 队列尾
	private int[] arr;// 用于存放数据，模拟队列

	public CircleQueue(int maxSize) {
		this.maxSize = maxSize;
		this.arr = new int[maxSize];
		// this.front = 0;// 指向队列头部
		// this.rear = 0;// 指向队列尾部的后一个位置
	}

	public boolean isFull() {
		return (rear + 1) % maxSize == front;
	}

	public boolean isEmpty() {
		return rear == front;
	}

	// 添加数据到队列，入队列
	public void addQueue(int num) {
		// 判断队列是否已满
		if (isFull()) {
			System.out.println("队列已满！");
			return;
		} else {
			arr[rear] = num;
			rear = (rear + 1) % maxSize; // 让rear后移
		}
	}

	// 获取队列数据，出队列
	public int getQueue() {
		// 判断队列是否为空
		if (isEmpty()) {
			throw new RuntimeException("队列为空！");// 抛出异常
		}
		// 1.将front对应的值保存
		int value = arr[front];
		// 2.front后移
		front = (front + 1) % maxSize;
		// 3.返回保存的front对应的值
		return value;
	}

	// 当前队列的有效数据个数
	public int size() {
		return (rear - front + maxSize) % maxSize;
	}

	// 显示队列所有数据
	public void showQueue() {
		// 遍历
		if (isEmpty()) {
			System.out.println("队列为空");
		} else {// 从front开始遍历
			for (int i = front; i < front + size(); i++) {
				System.out.print(arr[i % maxSize] + " ");
			}
		}
	}

	// 显示队列的头数据
	public int headQueue() {
		if (isEmpty()) {
			throw new RuntimeException("队列为空！");
		}
		return arr[front];
	}
}