普通順序隊列存在的問題

在普通順序隊列中,入隊的操作就是先將尾指針rear右移一個單位，然后將元素值賦值給rear單位。出隊時，則是頭指針front后移一個單位。像這樣進(jìn)行了一定數(shù)量的入隊和出隊操作后，可能會出現(xiàn)這樣的情況：

尾指針rear已指到數(shù)組的最后有一個元素，即rear==MaxLen-1，此時若再數(shù)組的前面部分可能還有很多閑置空間，即這種溢出并非是真的沒有可用的存儲空間，故稱這種溢出現(xiàn)象為“假溢出”。顯然，必須要解決這一塊假溢出的問題，否則順序隊列就沒有太多使用價值。

循環(huán)隊列

循環(huán)隊列的存儲結(jié)構(gòu)，頭、尾指針都和普通順序隊列相同。不同的只是將隊列視為“環(huán)狀結(jié)構(gòu)”，即data[0]為緊接著data[MaxLen-1]的單元，為相鄰的元素，首位成為一個環(huán)。結(jié)構(gòu)如下：

隊列為空的條件：rear==front；

隊列為滿的條件：(rear+1)%maxSize==front

實現(xiàn)：

public class MyDlQueue {

private Object data[];

private int rear;

private int front;

private int maxSize = 10;

// 初始化隊列

public MyDlQueue(int maxSize) {

if (maxSize >= 0) {

this.maxSize = maxSize;

rear = front = 0;

data = new Object[maxSize];

} else {

throw new RuntimeException("初始化隊列大小不能小于0");

}

}

// 判空

public boolean empty() {

return rear == front ? true : false;

}

// 判滿

public boolean full() {

//maxsize加1是因為①處的rear指向隊尾的后一個

return ((rear + 1) % (maxSize + 1)) == front ? true : false;

}

// 入隊

public boolean add(Object obj) {

if (full()) {

throw new RuntimeException("隊滿");

} else {

rear = rear % maxSize; //防止數(shù)組越界

data[rear] = obj;

rear = (rear + 1) % (maxSize + 1); //①

return true;

}

}

// 出隊

public Object poll() {

if (empty()) {

throw new RuntimeException("隊空");

} else {

Object value = data[front];

data[front] = null;

front = (front + 1) % maxSize;

return value;

}

}

// 獲取隊首元素

public Object peek() {

if (empty()) {

throw new RuntimeException("隊空");

} else {

return data[front];

}

}

// 返回隊列長度

public int length() {

return rear - front;

}

public static void main(String[] args) {

MyDlQueue queue = new MyDlQueue(5);

queue.add(1);

queue.add(2);

queue.add(3);

queue.add(4);

queue.add(5);

System.out.println(queue.length());

System.out.println(queue.empty());

System.out.println(queue.peek());

System.out.println(queue.poll());

queue.add("aaa");

for (Object obj : queue.data) {

System.out.print(obj + " ");

}

}

}

總結(jié)

以上是生活随笔為你收集整理的循环队列的java结构_Java数据结构——循环队列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。