数组实现队列【一】
程序员文章站
2024-03-18 08:06:52
...
【一】思路
队列的思想为-----先进先出
- 初始化:定义头指针尾指针,队列最大长度,头指针指向队列第一个数据的前一个位置;尾指针指向最后一个元素,默认值都为-1;
- 判断队列是否为空,当尾指针与头指针相等时,队列为空;
- 判断队列是否已满,当尾指针与队列最大长度-1相等,队列已满;
- 添加数据:当添加元素的时候,需要从队列尾部添加,所以尾指针向后加一;
- 取出数据:当取出元素的时候,需要从队列头部取出,所以头部指针加一。
【二】代码实现
class Queue{
private int maxSize;
private int front;
private int rear;
private int[] queue;
public Queue(int maxSize){
this.maxSize=maxSize;
front=-1;
rear=-1;
queue=new int[maxSize];
}
//队列是否为空
public boolean isEmpty() {
return front==rear;
}
//队列是否已满
public boolean isFull() {
return rear==maxSize-1;
}
//添加值
public void addValue(int n) {
if(isFull()) {
System.out.println("队列已满,不能添加值");
return;
}
queue[++rear]=n;
}
//取出值
public int getValue() {
if(isEmpty()) {
throw new RuntimeException("队列为空,不能取值");
}
front++;
return queue[front];
}
//显示队列的头数据
public int headQueue() {
if(isEmpty()) {
throw new RuntimeException("队列为空");
}
return queue[front+1];
}
//遍历队列
public void showQueue() {
if(isEmpty()) {
System.out.println("队列为空");
return;
}
for(int i=0;i<maxSize;i++) {
System.out.printf("arr[%d]=%d\n",i,queue[i]);
}
}
}
【三】分析
数组实现的队列浪得掉了一定的空间,当有元素出队列,front指针之前的位置都没有用到,所以这种实现方式存在弊端。
改进:环形数组实现队列数组实现队列【二】
上一篇: 实现二分查找的方法
下一篇: Java QueueDemo