上节我们简单的了解了什么是稀疏数组以及通过一个案例来简单分析它，关于它的更多详情请移驾数据结构入门教程-稀疏数组，这节我们来看看队列，队列我们并不陌生，接下来我们来看看队列简单的使用
什么是队列
首先队列是一个有序的列表，我们可以用数组和链表的方式来实现它。
队列遵循先入先出的原则，也就是说，先入队列的数据，会被首先取出
使用场景
这个场景可能很多人不陌生，我们去银行办理业务时,首先需要排号等待，这个场景是不是很熟悉，这个场景我们可以用队列来描述，所以银行的叫号系统利用的就是队列的特性，既然我们知道了队列的实现有两种方式，接下来我们分别来看看：
利用数组特性模拟队列
首先我们通过这个图来分析下，图如下：
队列图.png
上图为数组特性的队列，我们简单的分析下给队列中添加数据的过程：
- 来分析之前先来介绍下图中所指的几个参数：
- maxSize:代表当前队列的最大容量
- front:代表当前队列的头部的指针
- rear：代表当前队列尾部的指针
当我们队列中没有数据时，就会看到如图中front=rear=-1的场景，那么知道了这三个参数的意义之后，我们来看看向队列中添加数据过程的思路分析：
- 首先是尾部指针往后移动即：rear+1，前提条件是（当前队列没有满。是可以存数据的）
- 若尾部指针rear小于队列的最大下标maxSize-1时，则是可以存储数据到该队列中，这也给了我们一个信息，如果我们在存数据前要预先知道当前队列是否已满，可以利于该特点来判断。接下来我们利用代码来实现该过程：
代码实现过程
这里在强调一点，我们的front指针表示队列最前面的数据（不含当前数据）的位置，rear尾部指针是队列最后数据（含有当前数据）的位置。
- 首先我们需要申明一个队列，这其中包括队列自身的属性，代码如下：
static class ArrayQueue{
private int maxSize; //表示数组的最大容量
private int front; //队列的头指针
private int rear; //队列尾指针
private int[] array; //存放数据的数组（真正模拟的队列的数组）
//队列的构造器
public ArrayQueue(int arrMaxSize){
maxSize = arrMaxSize;
front = -1;//指向队列头部数据的前一个位置
rear = -1;//指向队列尾部的最后一个数据的位置
array = new int[maxSize];
}
上述代码是对队列的申明和初始化的过程，代码很简单，接着看
- 如果当前队列已满，是不能存数据的，因此需要我们来编写该方法，代码如下：
//2.判断队列是否已满
public boolean isFull(){
return rear == maxSize -1;
}
这里也不啰嗦了，前面分析已经很清楚了，接着看
- 队列为null的判断方法，代码如下：
//3.判断队列是否为null
public boolean isEmpty(){
return rear == front;
}
- 我们最核心的方法来了，添加操作，代码如下：
//4.添加数据到队列中
public void addQueue(int data){
//判断队列是否已满
if (isFull()){
System.out.println("队列已满，无法添加...");
return;
}
//首先让队列尾指针往后移动
rear ++;
array[rear] =data;
}
代码每一步的注释 很明确，也很简单，这就是我们的添加操作，是不是很easy，有添加过程，那么就会有查看队列数据的方法，接着看：
- 获取队列中的数据，代码如下：
//5.出队列
public int getQueue(){
//判断队列是否为null
if (isEmpty()){
throw new RuntimeException("队列为null,emmmmm");
}
front ++; //让队列头部往后移动一位（front是队列头部第一个数据位置的前一位）
return array[front];
}
当然获取队列中的数据时 ，头部指针是需要往后移动的，这个是很清楚的过程，我们在来写一个打印队列中数据的方法吧。
- 显示队列的所有数据
public void printQueue(){
//判断
if (isEmpty()){
System.out.println("队列为null");
return;
}
for (int i =0; i<array.length;i++){
System.out.printf("array[i]=%d\n",array[i]);
}
}
- 在来看一个显示头部的数据
public int peek(){
if (isEmpty()){
throw new RuntimeException("队列为null");
}
return array[front+1];
}
}
关于队列的常见方法我们写完了，我们来测试一把，我们写的方法
- 测试代码如下：
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):查看队列头的数据");
key = scanner.next().charAt(0);//接收一个字符
switch (key){
case 's':
arrayQueue.printQueue();
break;
case 'a':
System.out.println("请输入一个数字：");
int value = scanner.nextInt();
arrayQueue.addQueue(value);
break;
case 'g':
try {
int data = arrayQueue.getQueue();
System.out.println(data);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case 'h':
try {
int data = arrayQueue.peek();
System.out.println(data);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case 'e':
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程序退出~");
}
运行结果如下图：
测试.png
感兴趣的自己可以写写测测，但我们会发现一个问题，我们用数组特性来模拟队列时，队列中的数据是无法重复使用的 ，这也是数组实现的一个弊端，既然有弊端，那么就一定有对应的解决办法，我们可以通过环形队列的方式来完善这弊端，关于环形队列的实现，我们后面来说...
网友评论