队列 - 先进先出 - 线性结构
可使用 数组、链表进行实现
1.1 简单数组队列 - 只能存满一次
特点：
1、 队首出队(front改变)、队尾入队(rear改变)；
2、 front==rear→队列为空；
3、 rear==数组最大下标→队列为满；
4、 ***rear：**记录上次入队的位置；**front：*记录上次出队的位置；
代码实现 - 只能存满一次
class SimpleArrayQueue {
int capacity; // 队列能存储的最大容量
int front; // 存储上一次 从数组中 移出的 元素位置 -- 出队时改变
int rear; // 存储 上一次 元素被增添在数组内的位置 -- 入队时改变
int[] array; // 数组队列的容器
SimpleArrayQueue(int capacity) {
this.capacity = capacity;
}
// 如果 上一次出队的位置 跟 上一次入队的位置 相同 -- 说明无元素在队内
public boolean isEmpty() {
if(rear == front) {
return true;
}
return false;
}
// 如果 rear指示上次入队的数组位置，数组最大下标为( 容量-1 )，如果两者相等，说明队已经满，不可在入队
public boolean isFull() {
if( rear == capacity - 1) {
return true;
}
return false;
}
// 入队，先验证上次入队的位置是否等于最大数组小标，在rear进行指针下移动，入队新元素
public void enQueue(int element) {
if(isFull()) {
System.out.println("队列已经满");
return;
}
array[++rear] = element;
}
// 出队，先验证是否上次入队、出队位置重合，不重合，在进行front指针下移，出队指针下移位置的元素
public int deQueue() {
if(isEmpty()) {
throw new RuntimeException("队列中没有元素");
}
return array[++front];
}
}
1.2 环形数组队列
1.2.1 代码实现#
隐喻：好比如front就是你要追的女孩子，rear就是你，front不喜欢你，你在怎么追，永远都会跟她有一步之遥，除非女孩子一步步的靠近你
代码实现 – rear不能追上front，导致永远会预留一个位置
class CircularQueue {
int capacity;
int front = 0;
int rear = 0;
int[] array;
CircularQueue(int capacity) {
this.capacity = capacity;
array = new int[capacity];
}
// 查看 如果元素增加，rear指针是否与front重合，如果重合则不能添加
// 为了保证 isEmpty() 具有空队的 判断
boolean isFull() {
return (rear + 1) % capacity == front;
}
// 一旦front追上rear， 则说明是空队
boolean isEmpty() {
return rear == front;
}
void add(int a) {
if (isFull()) {
System.out.println("已满");
return;
}
array[rear] = a; // 元素入队成功
rear = (rear + 1) % capacity; //计算出下一个元素的入队位置
}
int get() {
if (isEmpty()) {
System.out.println("无元素可取");
throw new RuntimeException();
}
int result = array[front]; // 元素出队成功
array[front] = 0; // 元素值为0，表明那个位置是空的位置;
front = (front + 1) % capacity; // 计算下一个元素的出队位置
return result;
}
void show() {
System.out.println(Arrays.toString(array));
}
}
1.2.2 测试代码#
public static void main(String[] args) {
CircularQueue cq = new CircularQueue(3);
cq.add(1);
cq.add(2); // 队满
cq.show();
cq.add(3); // 不可添加
cq.show(); // 数组依然只有 1、2两元素
System.out.println("--------------------");
System.out.println(cq.get()); // 出队
cq.show(); // 只剩元素1
cq.add(3); // 添加成功
cq.show(); // 展示入队后的情况
cq.add(4); // 数组满 - 不可入队
}
运行结果
