模拟思路队列是一个有序列表，可以用数组或是链表来实现。
遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出
队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量
因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变，
如图所示
当我们将数据存入队列时需要有两个步骤：
-
添加元素时，将尾指针往后移：rear+1
-
当 front == rear 时，队列为空
-
若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear所指的数组元素中，否则无法存入数据。rear == maxSize - 1时，队列满
-
出队时，front+1，只要出队front会变化
注意：front指向的是队列首元素的前一个位置
代码实现：package com.sky.queue.array_;
public class NormalQueue {
public static void main(String[] args) {
ArrayQueue queue = new ArrayQueue(9);
queue.addElement(1);
queue.addElement(2);
queue.addElement(3);
queue.addElement(4);
System.out.println(queue.getElement());
queue.show();
}
}
class ArrayQueue{
// 队列最大长度
int maxSize;
// 数组队列
int[] arr;
// 指向队列首元素
int front;
// 指向队列尾元素
int rear;
// 初始化队列只需要指定队列的最大长度
public ArrayQueue(int maxSize){
this.maxSize = maxSize;
arr = new int[this.maxSize];
// front指向首元素的前一个位置
front = -1;
rear = -1;
}
// 判断队列是否为空
boolean isEmpty(){
return front == rear;
}
// 判断队列是否满了
boolean isFull(){
return front == maxSize -1;
}
// 进队列
public void addElement(int element){
if (isFull()){
System.out.println("已经填满了，不能再塞了!");
}
rear ++;
arr[rear] = element;
}
// 获取出队列元素
public int getElement(){
if (isEmpty()){
System.out.println("队列为空，无法出来！");
}
front++;
System.out.print("出队列的元素是：");
return arr[front];
}
// 打印队列
public void show(){
if (isEmpty()){
System.out.println("空队列你想看啥！");
return;
}
System.out.println("遍历元素");
for (int start = front+1; start <= rear; start++) {
System.out.print(arr[start]+" ");
}
}
}
环形队列
定义
思路：队列是一个有序列表，可以用数组或是链表来实现。
遵循先入先出的原则。即：先存入队列的数据，要先取出，后存入的要后取出。
- front变量指向队首元素，初值为0
- rear变量指向队尾元素的下一个元素，初值为0。规定空出一个位置
- 队列为空的判定条件：front == rear
- 队列为满的判定条件：(rear + 1) % maxSize == front
- 队列中有效元素的个数：(rear - front + maxSize) % maxSize
- 入队和出队时，都需要让标记对maxSize取模
package com.sky.queue.circle;
public class CircleQueue {
public static void main(String[] args) {
ArrayQueue arrayQueue = new ArrayQueue(4);
arrayQueue.addElement(1);
arrayQueue.addElement(2);
// arrayQueue.addElement(3);
// arrayQueue.addElement(4);
// arrayQueue.addElement(5);
arrayQueue.show();
System.out.println(arrayQueue.getElement());
arrayQueue.addElement(3);
arrayQueue.addElement(4);
arrayQueue.show();
}
}
class ArrayQueue{
// 队列的长度
int maxSize;
// 数组保存队列
int[] arr;
// 队首元素索引
int front;
// 队尾元素的下一个索引
int rear;
// 初始化队列
public ArrayQueue(int maxSize){
this.maxSize = maxSize;
arr = new int[maxSize];
front = 0;
rear = 0;
}
// 判断是否为空
public boolean isEmpty(){
return front == rear;
}
// 判断是否满了
public boolean isFull(){
return (rear+1)%maxSize == front;
}
// 进队列
public void addElement(int num){
if (isFull()){
System.out.println("队列已经满了，不要再进来了！");
return;
}
//先放入元素，在后移队尾标记
arr[rear] = num;
rear = (rear+1)%maxSize;
// rear++;
// rear = (rear+1)%maxSize;
// rear++;
}
// 获取出队列元素
public int getElement(){
if (isEmpty()){
throw new RuntimeException("空的队列，别取了！");
}
System.out.println("出列元素：");
int num = arr[front];
front = (front + 1) % maxSize;
return num;
}
// 遍历队列中的元素
public void show(){
if (isEmpty()){
System.out.println("空的队列，别看了！");
return;
}
System.out.println("遍历队列中的元素:");
int start = front;
while (start!=rear){
System.out.print(arr[start]+" ");
start = (start+1)%maxSize;
}
System.out.println("n");
}
}
暑期编程PK赛
得CSDN机械键盘等精美礼品！
