隊列：先進先出，后勁后出
應(yīng)用場景：排隊取號
代碼：
public class ArrayQueueDemo {
public static void main(String[] args) {
ArrayQueue queue = new ArrayQueue(3);
Scanner s = new Scanner(System.in);
boolean loop = true;
while(loop){
System.out.println("請輸入以下指令");
System.out.println("a既棺，添加隊列");
System.out.println("g璃吧，取出隊列");
System.out.println("s，顯示隊列頭");
System.out.println("w蝌衔，顯示隊列所有");
System.out.println("e，退出程序");
char key = s.next().charAt(0);
switch(key){
case 'a':
System.out.println("請輸入數(shù)字");
int i = s.nextInt();
queue.add(i);
break;
case 'g':
try {
System.out.println(queue.get());
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case 's':
try {
System.out.println(queue.showHead());
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case 'w':
queue.showAll();
break;
case 'e':
s.close();
loop = false;
System.out.println("已退出程序");
break;
default:
break;
}
}
}
/**
* 模擬數(shù)組隊列類
*/
static class ArrayQueue{
private int maxLen;//最大長度
private int front;//頭,指向隊列頭的前一個位置
private int reat;//尾部蝌蹂，指向隊列尾部
private int[] arr;//數(shù)組隊列
public ArrayQueue(int maxLen) {
this.maxLen = maxLen;
front = -1;
reat = -1;
arr = new int[maxLen];
}
private boolean isFull(){
return reat == arr.length-1;
}
private boolean isEmpty(){
return front==reat;
}
public boolean add(int i){
if(isFull()){
System.out.println("隊列已滿");
return false;
}
reat++;
arr[reat] = i;
return false;
}
public int get(){
if(isEmpty()){
throw new RuntimeException("隊列為空");
}
front++;
return arr[front];
}
public int showHead(){
if(isEmpty()){
throw new RuntimeException("隊列為空");
}
return arr[front + 1];
}
public void showAll(){
if(isEmpty()){
System.out.println("隊列為空");
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.printf("arr[%d] = %d\n",i,arr[i]);
}
}
}
}
這樣隊列不能復(fù)用噩斟，滿了之后加不了。
環(huán)形隊列
預(yù)留一個位置讓它循環(huán)孤个；
代碼：
public class ArrayQueueDemo2 {
public static void main(String[] args) {
/**
* 留了一個空位剃允，容量是4，但是有效的容量是3，最后一個位置留著
*/
ArrayQueue2 queue = new ArrayQueue2(4);
Scanner s = new Scanner(System.in);
boolean loop = true;
while(loop){
System.out.println("請輸入以下指令");
System.out.println("a斥废，添加隊列");
System.out.println("g椒楣，取出隊列");
System.out.println("s，顯示隊列頭");
System.out.println("w牡肉，顯示隊列所有");
System.out.println("e捧灰，退出程序");
char key = s.next().charAt(0);
switch(key){
case 'a':
System.out.println("請輸入數(shù)字");
int i = s.nextInt();
queue.add(i);
break;
case 'g':
try {
System.out.println(queue.get());
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case 's':
try {
System.out.println(queue.showHead());
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case 'w':
queue.showAll();
break;
case 'e':
s.close();
loop = false;
System.out.println("已退出程序");
break;
default:
break;
}
}
}
}
/**
* 模擬數(shù)組隊列類
*/
class ArrayQueue2{
private int maxSize;//最大長度
private int front;//頭,指向隊列頭 front的初始值為0
private int reat;//尾部，指向隊列尾部最后一個元素的后一個位置统锤，因為希望空出一個位置 reat的初始值為0
/**
* 隊列滿時： （reat+1)%maxSize = front /maxSize=3
* 隊列為空： reat = front
* 隊列中的有效數(shù)據(jù)個數(shù)： (reat+maxSize - front)%maxSize
*/
private int[] arr;//數(shù)組隊列
public ArrayQueue2(int maxLen) {
this.maxSize = maxLen;
front = 0;
reat = 0;
arr = new int[maxLen];
}
/**
* maxSize = 3 reat = 0 reat = 3
* @return
*/
private boolean isFull(){
return (reat+1)%maxSize == front;
}
private boolean isEmpty(){
return reat==front;
}
public boolean add(int i){
if(isFull()){
System.out.println("隊列已滿");
return false;
}
arr[reat] = i;
reat = (reat + 1)%maxSize;
System.out.println(reat);
System.out.println(front);
return false;
}
public int get(){
if(isEmpty()){
throw new RuntimeException("隊列為空");
}
int val = arr[front];
front = (front+1)%maxSize;
return val;
}
public int showHead(){
if(isEmpty()){
throw new RuntimeException("隊列為空");
}
return arr[front];
}
public void showAll(){
if(isEmpty()){
System.out.println("隊列為空");
return;
}
int count = (reat+maxSize-front)%maxSize;
for (int i = front; i < front+count; i++) {
System.out.printf("arr[%d] = %d\n",i%maxSize,arr[i%maxSize]);
}
}
}
