2.队列
2021-06-29 本文已影响0人
大旺旺的弟弟小旺旺
举个例子:饭堂打饭,后来的人只能站到队尾,前面的人走了之后,后面的人补上,
介绍
队列是一个方向进一个方向出的数据结构,可以使用数组和链表来实现。先进先出。
一般的实现过程:
- 数组思路:创建一个数组,一个头一个尾部,加入数据尾前进一个,走一个,头加一个。如果使用数据,数据存储到数组大小的时候,就无法存储了。现在我们先写一个数组实现,一会优化。
代码实现
public class Duilie {
private int maxsize = 10;
private int front = -1; //tou
private int rear = -1; //尾
private int arr[];
public Duilie(){
arr = new int[maxsize];
}
public boolean isFull(){
rear = maxsize - 1;
}
public void addData(int num){
if (isFull())return;
rear++;
arr[rear] = num;
}
public int outData(){
if (isEmpty()){
return -1;
}
front++;
return arr[front];
}
public boolean isEmpty(){
if (rear == front)return true;
return false;
}
}
就是简单的对数组进行操作,增加之前查看是不是满了,取数据之前是不是为空。
优化
上面的代码如果最后到达了结尾,显示满了,队头的数据出去了,空间却得不到使用,所以属于循环数组。
public class XunhuanDuilie {
private int maxsize = 10;
private int front = 0; //tou
private int rear = 0; //尾
private int arr[];
public XunhuanDuilie(){
arr = new int[maxsize];
}
public boolean isFull(){
return (rear+1)%maxsize == front;
}
public void addData(int num){
if (isFull())return;
rear = rear % maxsize;
arr[rear] = num;
rear++;
}
public int outData(){
if (isEmpty()){
return -1;
}
front%=maxsize;
return arr[front];
front++;
}
public boolean isEmpty(){
if (rear == front)return true;
return false;
}
将开始的位置都设置为0,还是如何找出下标,如何判断满和空,这个只要合理即可。