一、?隊(duì)列(Queue)
1.1 概念
隊(duì)列：只允許在一端進(jìn)行插入數(shù)據(jù)操作，在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表，隊(duì)列具有先進(jìn)先出FIFO(First In First Out) 入隊(duì)列：進(jìn)行插入操作的一端稱(chēng)為隊(duì)尾（Tail/Rear） 出隊(duì)列：進(jìn)行刪除操作的一端稱(chēng)為隊(duì)頭（Head/Front）
隊(duì)列和棧的區(qū)別：隊(duì)列是先進(jìn)先出（隊(duì)尾進(jìn)，隊(duì)頭出），棧是先進(jìn)后出
1.2 隊(duì)列的使用
在Java中，Queue是個(gè)接口，底層是通過(guò)鏈表實(shí)現(xiàn)的
| 方法 | 功能 |
| boolean offer(E e) | 入隊(duì)列 |
| E poll() | 出隊(duì)列 |
| peek() | 獲取隊(duì)頭元素 |
| int size() | 獲取隊(duì)列中有效元素個(gè)數(shù) |
| boolean isEmpty() | 檢測(cè)隊(duì)列是否為空 |
注意：Queue是個(gè)接口，在實(shí)例化時(shí)必須實(shí)例化LinkedList的對(duì)象，因?yàn)長(zhǎng)inkedList實(shí)現(xiàn)了Queue接口? ?Queue<Integer> q = new LinkedList<>();
?Queue 的方法有以下六種，每?jī)煞N都是一樣的功能（添| 刪 |查），但是還是存在一定的差異
差異：
（1）add，remove，element都是Collection的通用方法
????????offer，poll，peek是隊(duì)列專(zhuān)有的方法
（2）Collection實(shí)現(xiàn)的通用方法中 有些情況會(huì)報(bào)異常
? ? ? ? 而隊(duì)列專(zhuān)有的方法中 不會(huì)報(bào)異常?
? ? ? ? eg：如果想在一個(gè)滿(mǎn)的隊(duì)列中加入一個(gè)新項(xiàng)，調(diào)用 add() 方法就會(huì)拋出一個(gè) unchecked 異常，而調(diào)用 offer() 方法會(huì)返回 false
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
q.offer(1);
q.offer(2);
q.offer(3);
q.offer(4);
q.offer(5); // 從隊(duì)尾入隊(duì)列
System.out.println(q.size());
System.out.println(q.peek()); // 獲取隊(duì)頭元素
q.poll();
System.out.println(q.poll()); // 從隊(duì)頭出隊(duì)列，并將刪除的元素返回
if(q.isEmpty()){
System.out.println("隊(duì)列空");
} else {
System.out.println(q.size());
}
}1.3 隊(duì)列模擬實(shí)現(xiàn)
隊(duì)列中既然可以存儲(chǔ)元素，那底層肯定要有能夠保存元素的空間，通過(guò)前面線性表的學(xué)習(xí)了解到常見(jiàn)的空間類(lèi)型有兩種：順序結(jié)構(gòu) 和 鏈?zhǔn)浇Y(jié)構(gòu)。同學(xué)們思考下：隊(duì)列的實(shí)現(xiàn)使用順序結(jié)構(gòu)還是鏈?zhǔn)浇Y(jié)構(gòu)好？
（1）單鏈表模擬實(shí)現(xiàn)：為了保證時(shí)間復(fù)雜度為O（1）
肯定不能從隊(duì)頭進(jìn)，隊(duì)尾出，這樣刪尾節(jié)點(diǎn)時(shí)間復(fù)雜度就為O（N）
所以采用從隊(duì)尾進(jìn)，隊(duì)頭出，但是這個(gè)時(shí)候就需要last指針來(lái)指向隊(duì)尾 ，這樣的尾插，頭刪才滿(mǎn)足條件
（2） 雙向鏈表模擬實(shí)現(xiàn)：無(wú)論從隊(duì)頭進(jìn)，隊(duì)尾出，還是從隊(duì)尾進(jìn)，隊(duì)頭出，都是可以的
雙向鏈表就是神一般的存在 LinkedList：可以當(dāng)作雙向鏈表，棧，隊(duì)列
?（3）數(shù)組模擬實(shí)現(xiàn)：可以用來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，如果實(shí)現(xiàn)普通隊(duì)列，就會(huì)存在刪除元素的前面（front指針的前面）無(wú)法再進(jìn)行添加元素
下面這個(gè)代碼是由雙向鏈表(尾插，頭刪）實(shí)現(xiàn)隊(duì)列：
import java.security.PublicKey;
//雙向鏈表(尾插，頭刪）實(shí)現(xiàn)隊(duì)列
public class MyQueue {
static class ListNode {
public int val;
public ListNode prev;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;
public ListNode last;
//入隊(duì)
public void offer(int val) {
ListNode node = new ListNode(val);
//尾插
if(head == null) {
head = last = node;
} else {
last.next = node;
node.prev = last;
last = node;
}
}
//出隊(duì)
public int poll() {
//空隊(duì)列
if(head == null) {
return -1;
}
//一個(gè)節(jié)點(diǎn)
int val = -1;
if (head.next == null) {
val = head.val;
head = null;
last = null;
return val;
}
val = head.val;
head = head.next;
head.prev = null;
return val;
}
//判斷是否為空
public boolean empty() {
return head == null;
}
public int peek() {
if (head == null) {
return -1;
}
return head.val;
}
}
1.4 循環(huán)隊(duì)列
實(shí)際中我們有時(shí)還會(huì)使用一種隊(duì)列叫循環(huán)隊(duì)列（是一個(gè)圖而不是一個(gè)線性結(jié)構(gòu)，但由于其名稱(chēng)叫循環(huán)隊(duì)列而不叫有向圖）。如操作系統(tǒng)課程講解生產(chǎn)者消費(fèi)者模型時(shí)可以就會(huì)使用循環(huán)隊(duì)列。環(huán)形隊(duì)列通常使用數(shù)組實(shí)現(xiàn)
?數(shù)組下標(biāo)循環(huán)的小技巧
1. 下標(biāo)最后再往后(offset 小于 array.length): index = (index + offset) % array.length
?2. 下標(biāo)最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length
如何區(qū)分空與滿(mǎn)
1. 通過(guò)添加 size 計(jì)數(shù)的方式來(lái)判斷（這個(gè)較簡(jiǎn)單）
2. 保留一個(gè)位置，浪費(fèi)空間來(lái)表示滿(mǎn)（這個(gè)用的較多）
3. 使用標(biāo)記boolean flg （開(kāi)始前在同一位置標(biāo)記為false，再次相遇標(biāo)記為true）（這個(gè)也比較簡(jiǎn)單）
設(shè)計(jì)循環(huán)隊(duì)列
class MyCircularQueue {
public int[] elem;
public int front;
public int rear;
public MyCircularQueue(int k) {
elem = new int[k + 1];// 浪費(fèi)一個(gè)空間，也就是需要多開(kāi)一個(gè)元素的空間
}
// 入隊(duì)操作
public boolean enQueue(int value) {
if (isFull()) {
return false;
}
elem[rear] = value;
rear = (rear + 1) % elem.length;// 注意點(diǎn)1：不可直接rear+1
return true;
}
// 刪除隊(duì)頭元素（空不空 + front移動(dòng)）
public boolean deQueue() {
if (isEmpty()) {
return false;
}
front = (front + 1) % elem.length; // 注意點(diǎn)2：不可直接front+1
return true;
}
// 得到隊(duì)頭元素 不刪除
public int Front() {
if (isEmpty()) {
return -1;
}
return elem[front];
}
// 得到隊(duì)尾元素 不刪除
public int Rear() {
if (isEmpty()) {
return -1;
}
// rear=0說(shuō)明剛剛走過(guò)一圈以上，那么隊(duì)尾就為elem.length-1
// rear!=0說(shuō)明還沒(méi)到跨越的位置，直接-1即可
int index = (rear == 0) ? elem.length - 1 : rear - 1;
return elem[index];
}
// 判空 front和rear都在起始點(diǎn)
public boolean isEmpty() {
return front == rear;
}
public boolean isFull() {
return (rear + 1) % elem.length == front;
}
}1.5 雙端隊(duì)列 (Deque)
雙端隊(duì)列（deque）是指允許兩端都可以進(jìn)行入隊(duì)和出隊(duì)操作的隊(duì)列，deque 是 “double ended queue” 的簡(jiǎn)稱(chēng)。那就說(shuō)明元素可以從隊(duì)頭出隊(duì)和入隊(duì)，也可以從隊(duì)尾出隊(duì)和入隊(duì)
?Deque是一個(gè)接口，使用時(shí)必須創(chuàng)建LinkedList的對(duì)象（所以他可以當(dāng)作雙向鏈表|棧使用）
在實(shí)際工程中，使用Deque接口是比較多的，棧和隊(duì)列均可以使用該接口
Deque<Integer> stack = new ArrayDeque<>(); //雙端隊(duì)列的線性實(shí)現(xiàn)
Deque<Integer> queue = new LinkedList<>();? //雙端隊(duì)列的鏈?zhǔn)綄?shí)現(xiàn)
?Stack這個(gè)類(lèi)不是唯一的，可以是棧，LinkedList ，也可以是ArrayDeque
二、面試題
1. 用隊(duì)列實(shí)現(xiàn)棧
?思考：一個(gè)普通的隊(duì)列能否實(shí)現(xiàn)一個(gè)棧？? 肯定是不可以的，一個(gè)是先進(jìn)先出 ，一個(gè)是先進(jìn)后出
思路：
（1）當(dāng)兩個(gè)隊(duì)列都是空的時(shí)候 放到第一個(gè)隊(duì)列
（2）再次" 入棧 “ 的時(shí)候，放到不為空的隊(duì)列
（3）“出?！钡臅r(shí)候，出不為空的隊(duì)列 ，出size -1 個(gè)元素 ，剩下的元素就是要出棧的元素
class MyStack {
private Queue<Integer> qu1;
private Queue<Integer> qu2;
public MyStack() {
qu1 = new LinkedList();
qu2 = new LinkedList();
}
public void push(int x) {
//當(dāng)兩個(gè)隊(duì)列都是空的時(shí)候放到第一個(gè)隊(duì)列
if(empty()) {
qu1.offer(x);
return;
}
//入棧，放到不為空的隊(duì)列
if(!qu1.isEmpty()) {
qu1.offer(x);
} else {
qu2.offer(x);
}
}
public int pop() {
if(empty()) {
return -1;
}
//找到不為空的隊(duì)列 ，出size-1個(gè)元素
if(!qu1.isEmpty()) {
int size = qu1.size();
for(int i =0;i<size-1;i++) { //這里不能寫(xiě)成i<qu1.size(),因?yàn)閝u1.size()一直在變
//出size-1個(gè)元素都放到另一個(gè)隊(duì)列
qu2.offer(qu1.poll());
}
//最后出本隊(duì)列的最后一個(gè)元素
return qu1.poll();
} else {
int size = qu2.size();
for(int i =0;i<size-1;i++) {
qu1.offer(qu2.poll());
}
return qu2.poll();
}
}
public int top() {
if(empty()) {
return -1;
}
//找到不為空的隊(duì)列 ，出size個(gè)元素
if(!qu1.isEmpty()) {
int size = qu1.size();
int tmp = -1;
for(int i =0;i<size;i++) {
//出size個(gè)元素都放到另一個(gè)隊(duì)列,并用tmp記錄下這個(gè)數(shù)
tmp = qu1.poll();
qu2.offer(tmp);
}
//返回最后出本隊(duì)列的元素
return tmp;
} else {
int size = qu2.size();
int tmp = -1;
for(int i =0;i<size;i++) {
tmp = qu2.poll();
qu1.offer(tmp);
}
return tmp;
}
}
//兩個(gè)隊(duì)列都是空代表?xiàng)榭? public boolean empty() {
return qu1.isEmpty() && qu2.isEmpty();
}
}2. 用棧實(shí)現(xiàn)隊(duì)列
思路：
（1）“入隊(duì)”:把數(shù)據(jù)放到第一個(gè)棧當(dāng)中
（2）“出隊(duì)”：出?s2 這個(gè)棧當(dāng)中棧頂?shù)脑丶纯?，如?s2 為空，把 s1 里面所有元素全部放到 s2文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-768133.html
（3）當(dāng)兩個(gè)棧都為空 說(shuō)明模擬的隊(duì)列為空?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-768133.html
class MyQueue {
private Stack<Integer> s1;
private Stack<Integer> s2;
public MyQueue() {
s1 = new Stack<>();
s2 = new Stack<>();
}
public void push(int x) {
s1.push(x);
}
public int pop() {
if(empty()) {
return -1;
}
if(s2.isEmpty()) {
//s2為空，把s1中所有的元素放入s2中
while(!s1.isEmpty()) {
s2.push(s1.pop());
}
}
return s2.pop();
}
public int peek() {
if(empty()) {
return -1;
}
if(s2.isEmpty()) {
//s2為空，把s1中所有的元素放入s2中
while(!s1.isEmpty()) {
s2.push(s1.pop());
}
}
return s2.peek();
}
public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
}到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】隊(duì)列的使用|模擬實(shí)現(xiàn)|循環(huán)隊(duì)列|雙端隊(duì)列|面試題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
