Java数组模拟队列
- 2020 年 4 月 11 日
- 笔记
队列
先进先出
什么意思呢？
我的理解：队列就是一个数组（不包含链表），然后我们给它施加一个存数据和取数据的规则
当只允许从一端存数据，从另一端取数据的数组，就是队列，我们要做的就是给这个数组施加我们制定的规则
不理解就上图
图解步骤：
【图（a）】有一个长度为5的数组，定义头部标志和尾部标志
【图（b）】按顺序插入e1,e2,e3数据，插入数据从尾部插入，此时头部标志不变，插入一个数据，尾部标志就加1
【图（c）】取元素就只能从头部取，每取一个数据，头部标志就加一
【图（d）】这样就形成了先进先出的规则
再不理解多思考，多敲两遍代码，或者讲一遍给别人听
代码实现
public class ArrayQueue { //最大长度 int maxSize; //定义一个数组，存储数据 private int[] queue; //定义对头和队尾标志 private int front; private int rear; //初始化一个数组 public void init(int maxSize){ front = -1; rear = -1; this.maxSize = maxSize; this.queue = new int[maxSize]; } //判断对满 public boolean isFull(){ return rear == maxSize-1; } //判断队空 public boolean isEnpty(){ return front == rear; } //加入数据，只能从队头加入 public void add(int num){ if(isFull()){ System.out.println("队列满了,插入失败"); return; } //要理清楚先后顺序 rear++; queue[rear] = num; } //取数据，只能从队尾取 public int get(){ if(isEnpty()){ System.out.println("队列为空"); //数组初始化之后默认值就是0 return 0; } front++; return queue[front]; } //查看队头元素 public int showFront(){ if(isEnpty()){ System.out.println("队列为空"); //数组初始化之后默认值就是0 return 0; } return queue[front+1]; } //遍历所有数 public void showAll(){ if(isEnpty()){ System.out.println("队列为空"); //数组初始化之后默认值就是0 return; } System.out.println("显示队列：======"); for(int i = front+1; i <= rear; i++){ System.out.println(queue[i]); } System.out.println("==============="); } } 【代码改进】
使用这个队列，你会觉得很难受，因为你定义了它的长度，它的长度就不能改变了，我们可以设计一个长度可以增加的队列
【设计思路】
当rear==maxSize,即数组满了的时候，我们新建一个数组，比原数组长一倍，然后将原数组的值赋值到新数组
【代码实现】
我们只要修改add方法的代码
public void add(int num){ if(isFull()){ //新建一个长度为原来两倍的数组 int[] newQueue = new int[maxSize*2]; //原数组赋值到新数组 for(int i = front+1; i <= rear; i++){ newQueue[i] = queue[i]; } rear++; queue[rear] = num; return; } rear++; queue[rear] = num; } 【思考】
其实代码还有很多改进空间
1.比如这里我们写死了只能使用int类型的数组，那么我们能不能将类型像参数一样，在初始化队列的时候再确认呢？这里可以用到泛型知识
2.再比如取数据的时候，当这个数不存在的时候我们返回的是默认值0，能不能不返回0，也能使代码正常结束呢，这里可以用到异常知识
数据结构的改进
我们会发现，如果使用这种结构来创建队列，当取出数据后，front前面的空间就不能进行操作了，造成了大量的空间浪费，这个时候我们可以
将顺序队列假象成一个环
