队列是一种先进先出（FIFO—first in first out）线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。
-
进行插入操作的端称为队尾；
-
进行删除操作的端称为队头；
-
队列中没有元素时，称为空队列；
-
队列的数据元素又称为队列元素；
-
在队列中插入一个队列元素称为入队；
-
从队列中删除一个队列元素称为出队；
因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。
2、图解 二、队列 1、数组实现队列public class ArrayQueue {
private int maxSize;
private int head;
private int end;
private int[] array;
public ArrayQueue(int maxSize) {
this.maxSize = maxSize;
this.head = -1;
this.end = -1;
this.array = new int[maxSize];
}
public boolean isFull() {
return end == maxSize - 1;
}
public boolean isEmpty() {
return head == end;
}
public void add(int n) {
if (isFull()) {
throw new RuntimeException("队列已满，添加失败");
}
end++;
array[end] = n;
}
public int get() {
if (isEmpty()) {
throw new RuntimeException("队列为空，取数据失败");
}
head++;
return array[head];
}
public void show() {
if (isEmpty()) {
System.out.println("队列为空");
return;
}
for (int i = head + 1; i <= end; i++) {
System.out.println(array[i]);
}
}
public void clear() {
head = -1;
end = -1;
array = new int[maxSize];
}
}
2、测试
import java.util.Scanner;
public class ArrayQueueDemo {
public static void main(String[] args) {
ArrayQueue arrayQueue = new ArrayQueue(3);
char key = ' ';
Scanner scanner = new Scanner(System.in);
boolean loop = true;
while (loop) {
System.out.println("s(show):显示队列");
System.out.println("c(clear):清空队列");
System.out.println("a(add):添加元素");
System.out.println("g(get):取出元素");
System.out.println("e(exit):退出程序");
System.out.println("请输入选项：");
key = scanner.next().charAt(0);
switch (key) {
case 's':
arrayQueue.show();
break;
case 'c':
arrayQueue.clear();
break;
case 'a':
System.out.println("请输入添加的元素");
try {
arrayQueue.add(scanner.nextInt());
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'g':
try {
System.out.println("取出:"+arrayQueue.get());
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'e':
loop = false;
break;
default:
System.out.println("输入有误，请重新输入...");
break;
}
System.out.println("-------------------------");
}
}
}
三、环形队列
1、数组实现
public class ArrayAnnularQueue {
private int maxSize;
private int head;
private int end;
private int[] array;
public ArrayAnnularQueue(int maxSize) {
this.maxSize = maxSize;
this.array = new int[maxSize];
}
public boolean isFull() {
return (end + 1) % maxSize == head;
}
public boolean isEmpty() {
return head == end;
}
public void add(int n) {
if (isFull()) {
throw new RuntimeException("队列已满，添加失败");
}
array[end] = n;
end = (end + 1) % maxSize;
}
public int get() {
if (isEmpty()) {
throw new RuntimeException("队列为空，取数据失败");
}
int value = array[head];
head = (head + 1) % maxSize;
return value;
}
public void show() {
if (isEmpty()) {
System.out.println("队列为空");
return;
}
for (int i = head; i < head + size(); i++) {
System.out.printf("arr[%d] = %d n",i%maxSize,array[i % maxSize]);
}
}
public int size(){
return (end + maxSize - head) % maxSize;
}
public void clear() {
head = 0;
end = 0;
array = new int[maxSize];
}
}
2、测试
package com.dashu.linear_structure.queue.annular;
import com.dashu.linear_structure.queue.ArrayQueue;
import java.util.Scanner;
public class ArrayAnnularQueueDemo {
public static void main(String[] args) {
ArrayAnnularQueue arrayAnnularQueue = new ArrayAnnularQueue(3);
char key = ' ';
Scanner scanner = new Scanner(System.in);
boolean loop = true;
while (loop) {
System.out.println("s(show):显示队列");
System.out.println("c(clear):清空队列");
System.out.println("a(add):添加元素");
System.out.println("g(get):取出元素");
System.out.println("e(exit):退出程序");
System.out.println("请输入选项：");
key = scanner.next().charAt(0);
switch (key) {
case 's':
arrayAnnularQueue.show();
break;
case 'c':
arrayAnnularQueue.clear();
break;
case 'a':
System.out.println("请输入添加的元素");
try {
arrayAnnularQueue.add(scanner.nextInt());
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'g':
try {
System.out.println("取出:"+arrayAnnularQueue.get());
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'e':
loop = false;
break;
default:
System.out.println("输入有误，请重新输入...");
break;
}
System.out.println("-------------------------");
}
}
}
