队列:
数组队列(一次性存取,因为指针上移之后就没有下移过了):
class ArrayQueue{
private int maxSize;
private int front;
private int rear;
private int[] arr;
public ArrayQueue(int arrMaxSize){
maxSize=arrMaxSize;
front=-1;
rear=-1;
arr=new int[maxSize];
}
public boolean isFull(){
return rear==maxSize-1;
}
public boolean isEmpty(){
return rear==front;
}
public void addQueue(int n){
if (isFull()){
System.out.println("很遗憾,队列已满~");
}
rear++;
arr[rear]=n;
}
public int getQueue(){
if (isEmpty()){
throw new RuntimeException("没有数据可以取出~");
}else {
front++;
return arr[front];
}
}
public void showQueue(){
if (isEmpty()){
System.out.println("队列为空~");
}else {
for (int i=0;i<arr.length;i++) {
System.out.printf("arr[%d]\t%d\n",i,arr[i]);
}
}
}
public int getFront(){
if (isEmpty()){
throw new RuntimeException("没有数据可以取出~");
}else {
return arr[front+1];
}
}
存在问题:数组只有一次性就不能复用了
环形数组队列:
class CircleArray {
private int maxSize;
private int front;
private int rear;
private int[] arr;
public CircleArray(int arrMaxSize) {
maxSize = arrMaxSize;
front = 0;
rear = 0;
arr = new int[maxSize];
}
public boolean isFull() {
return (rear + 1) % maxSize == front;//取模是因为防止负数,就相当于取绝对值的意思
}
public boolean isEmpty() {
return rear == front;
}
public void addQueue(int n) {
if (isFull()) {
System.out.println("很遗憾,队列已满~");
}
arr[rear] = n;
rear = (rear + 1) % maxSize;
}
public int getQueue() {
if (isEmpty()) {
throw new RuntimeException("没有数据可以取出~");
} else {
int value=arr[front];
front=(front+1)%maxSize;
return value;
}
}
public void showQueue() {
if (isEmpty()) {
System.out.println("队列为空~");
} else {
for (int i = front; i < front+size(); i++) {
System.out.printf("arr[%d]\t%d\n", i%maxSize, arr[i%maxSize]);
}
}
}
public int getFront() {
if (isEmpty()) {
throw new RuntimeException("没有数据可以取出~");
} else {
return arr[front];
}
}
public int size(){
return (rear+maxSize-front)%maxSize;
}
}
maxsize是总的数组长度,但是实际上存放的数据是maxsize-1,要留一个位置来实现取模循环,比如maxsize=4,只能存三个数,到第三个数存放完毕的时候,rear=3,front=0,此时队列已满,然后出列一个数front=1;此时队列不满,然后插入一个数据rear就等于0了,此时队列又满了,就是通过 4运算来实现的循环。(可以画一个简单的草图易于理解)