- 队列是一个有序列表，遵循 先入先出原则；可以用数组/链表实现。
(例如： 银行叫号)
顺序队列
数组模拟 顺序队列：
- maxSize队列最大容量，头部front，尾部rear，arr[]存数据
- 思路：【显示队列，添加push，取出pop，查看队首】
- front = rear，队列空
- rear=maxSize-1，队列满
- rear指向队列最后【含】，front指向队首【不含】
会出现“假溢出”现象。
点击查看代码
class Queue{
private int maxSize;
private int front; //对首 指向第一个数的前一个
private int rear; //队尾
private int[] arr;
public Queue(int maxSize){
this.maxSize = maxSize;
this.arr = new int[maxSize];
this.front = -1;
this.rear = -1;
}
public void show(){
if (front==rear){
System.out.println("空队列~");
}else{
for (int i=rear;i>front;i--) {
System.out.print(arr[i]+" ");
}
}
}
public void add(int value){
if (rear==maxSize-1){
System.out.println("队列满，无法加入!");
}else {
rear++;
arr[rear] = value;
System.out.println("添加完成");
}
}
//弹出 队首元素
public int pop(){
if (front==rear){
System.out.println("队列空，无法pop");
return -1;
}else {
front++;
return arr[front];
}
}
//查看队列头元素
public void head(){
if (front==rear){
System.out.println("空队列");
}else {
System.out.println(arr[front+1]);
}
}
}
环形队列
- 核心思想：取模 ，超出maxSize就回到最前面
- front=0 指向首部，rear=0 指向尾部元素的后一个
- 数组需要预留一个位置出来，用于判断是否 满 -->队列长度= arr.length-1
- 取模运算 %
- 入队：(rear+1)%maxSize
- 出队：(front+1)%maxSize
- 空：front=rear
- 满：(rear+1)%maxSize = front 再往后移一位就到达队首位置
- 剩余Size：(rear-front+maxSize)%maxSize 用于遍历队列
点击查看代码
class CircularQueue{
private int maxSize;
private int front;
private int rear;
private int[] arr;
public CircularQueue(int maxSize){
this.maxSize = maxSize;
this.arr = new int[maxSize];
this.front = 0;
this.rear = 0;
}
public boolean isEmpty(){
return front==rear;
}
public boolean isFull(){
return (rear+1)%maxSize == front;
}
public int size(){
return (rear-front+maxSize)%maxSize;
}
public void show(){
//剩余size: [(r-f)+maxSize]%maxSize
if (!isEmpty()){
System.out.println("从队首开始遍历~");
for (int i = front; i < front+size(); i++) {
System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
}
}else {
System.out.println("队列为空,无法遍历!");
}
}
public void add(int value){
if (!isFull()){
arr[rear] = value;
rear = (rear+1)%maxSize;
}else {
System.out.println("队列满~,无法入队");
}
}
public int pop(){
if (!isEmpty()){
int value = arr[front];
front = (front+1)%maxSize;
return value;
}else {
System.out.println("队列空,无法出队");
return -1;
}
}
public void head(){
if (!isEmpty()){
System.out.println(arr[front]);
}else {
System.out.println("队列空,无法获取队首");
}
}
}