尚硅谷java数据结构与算法 韩顺平 数组实现队列问题

尚硅谷java数据结构与算法 韩顺平 数组实现队列问题

 day2学习打卡：数组实现循环队列

package queue;

import java.util.Scanner;
//这里没有使用循环队列的思想所以造成了数组空间的浪费（数组空间不能复用）
public class ArrayQueueDemo {
      public static void main(String[] args) {
			//测试
    	  //创建一个队列
    	  ArrayQueue arrayQueue = new ArrayQueue(3);
    	  char key = ' ';//接收用户输入
    	  Scanner scanner = new Scanner(System.in);
    	  boolean loop = true;//循环执行标志
    	  while(loop) {
    		  System.out.println("s(show):显示队列");
    		  System.out.println("e(exit):退出程序");
    		  System.out.println("a(add):添加数据到队列");
    		  System.out.println("g(get):从队列中取出数据");
    		  System.out.println("h(head):查看队列头的数据");
    		  System.out.println();
    		  System.out.println("请输入以上任意一个字符开始。。。");
    		  key = scanner.next().charAt(0);//接收一个字符
    		  switch (key) {
			case 's'://展示队列的所有数据
				arrayQueue.showQueue();
				break;
            case 'e':
				scanner.close();
				loop = false;
				break;
            case 'a'://添加数据到队列
	            System.out.println("请输入要添加的数");
	            int value = scanner.nextInt();
	            arrayQueue.addQueue(value);
	            break;
            case 'g'://取数据
	             try {//通过try catach捕获方法里抛出的异常信息 并打印定义的异常内容
	            	 int res = arrayQueue.getQueue();
					System.out.printf("取出的数据是%dn",res);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
	            break;
            case 'h':
	              try {
					int res = arrayQueue.headQueue();
					System.out.printf("队列的头数据是%dn",res);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
	            break;

			default:
				break;
			}
    		  System.out.println("退出。。。");
    		  System.out.println("--------------------");
    	  }
   }
}



//使用数组模拟队列-编写一个ArrayQueue类
class ArrayQueue {
	private int maxSize;//表示数组的最大容量
	private int front;// 队列头 指向首元素前一个位置
	private int rear;// 队列尾
	private int[] arr;//该数组用于存放数据 模拟队列
	
	public ArrayQueue(int arrMaxSize) {
		this.maxSize = arrMaxSize;
		arr = new int[maxSize];
		front = -1;//指向队列头部，分析出front是指向队列头的前一个位置
		rear = -1;//指向队列尾部，指向队列尾的数据（即就是队列的最后一个数据）
	}
	
	//判断队列是否满
	public boolean isFull() {
		return rear == maxSize-1;
	}
	
	//判断队列是否为空
	public boolean isEmpty(){
		return rear == front;
	}
	
	//添加数据到队列
	public void addQueue(int n) {
		if(isFull()) {
			System.out.println("队列满，不能加数据。。");
			return;//结束语句
		}
		rear++;
		arr[rear] = n;
	}
	
	//获取队列的数据 出队列
	public int getQueue() {
		//判读队列是否空
		if(isEmpty()) {
			//通过抛异常处理
			throw new RuntimeException("队列空，不能取数据");
		}
		front++;//front后移 因为本身front就指向队首前一个位置
		return arr[front];
	}
	
	
	//展示队列的所有数据
	public void showQueue() {
		//遍历
		if(isEmpty()) {
			System.out.println("队内没有数据");
			return;
		}
		for (int i = 0; i < maxSize; i++) {
			System.out.printf("arr[%d] = %dn",i,arr[i]);
		}
		
	}
	
	//显示队列的头数据 但是不取出
	public int headQueue() {
		if(isEmpty()) {
			throw new RuntimeException("队列空，不能取数据");
		}
		return arr[front + 1];
	}
	
	
	
	
	
	
}

循环队列：

package queue;

import java.util.Scanner;

public class CircleArrayQueueDemo {

	public static void main(String[] args) {
		// 测试
		System.out.println("------测试数组完成环形队列代码------");
		// 创建一个环形队列
		CircleArray arrayQueue = new CircleArray(4);// 实际上有效位置只有3个
		char key = ' ';// 接收用户输入
		Scanner scanner = new Scanner(System.in);
		boolean loop = true;// 循环执行标志
		while (loop) {
			System.out.println("s(show):显示队列");
			System.out.println("e(exit):退出程序");
			System.out.println("a(add):添加数据到队列");
			System.out.println("g(get):从队列中取出数据");
			System.out.println("h(head):查看队列头的数据");
			System.out.println();
			System.out.println("请输入以上任意一个字符开始。。。");
			key = scanner.next().charAt(0);// 接收一个字符
			switch (key) {
			case 's':// 展示队列的所有数据
				arrayQueue.showQueue();
				break;
			case 'e':
				scanner.close();
				loop = false;
				break;
			case 'a':// 添加数据到队列
				System.out.println("请输入要添加的数");
				int value = scanner.nextInt();
				arrayQueue.addQueue(value);
				break;
			case 'g':// 取数据
				try {// 通过try catach捕获方法里抛出的异常信息 并打印定义的异常内容
					int res = arrayQueue.getQueue();
					System.out.printf("取出的数据是%dn", res);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case 'h':
				try {
					int res = arrayQueue.headQueue();
					System.out.printf("队列的头数据是%dn", res);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;

			default:
				break;
			}
			System.out.println("退出。。。");
			System.out.println("--------------------");
		}
	}

}

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

	public CircleArray(int arrMaxSize) {
		this.maxSize = arrMaxSize;
		arr = new int[maxSize];
		front = 0;
		rear = 0;
	}

	// 判断队列是否满
	public boolean isFull() {
		return (rear + 1) % maxSize == front;
	}

	// 判断队列是否为空
	public boolean isEmpty() {
		return rear == front;
	}

	// 添加数据到队列
	public void addQueue(int n) {
		if (isFull()) {
			System.out.println("队列满，不能加数据。。");
			return;// 结束语句
		}
		// 直接将数据加入就行了
		arr[rear] = n;
		// rear后移但是这里必须取模
		rear = (rear + 1) % maxSize;
	}

	// 获取队列的数据 出队列
	public int getQueue() {
		// 判读队列是否空
		if (isEmpty()) {
			// 通过抛异常处理
			throw new RuntimeException("队列空，不能取数据");
		}
		// 这里需要分析出front是指向队列的第一个元素
		// 先将font对应值保留到一个临时变量
		// font后移
		// 将临时保存的变量返回
		int value = arr[front];
		front = (front + 1) % maxSize;
		return value;
	}

	// 展示队列的所有数据
	public void showQueue() {
		// 遍历
		if (isEmpty()) {
			System.out.println("队内没有数据");
			return;
		}
		// 思路：从front开始遍历 ，遍历多少个元素 front + size()
		for (int i = front; i < front + size(); i++) {
			System.out.printf("arr[%d] = %dn", i % maxSize, arr[i]);
		}

	}

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

	// 显示队列的头数据 但是不取出
	public int headQueue() {
		if (isEmpty()) {
			throw new RuntimeException("队列空，不能取数据");
		}
		return arr[front];
	}

}