柚子快報(bào)邀請(qǐng)碼778899分享：【數(shù)據(jù)結(jié)構(gòu)（六）】隊(duì)列
柚子快報(bào)邀請(qǐng)碼778899分享：【數(shù)據(jù)結(jié)構(gòu)（六）】隊(duì)列
?博主主頁(yè): 33的博客? ??文章專(zhuān)欄分類(lèi):數(shù)據(jù)結(jié)構(gòu)?? ?我的代碼倉(cāng)庫(kù): 33的代碼倉(cāng)庫(kù)? ???關(guān)注我?guī)銓W(xué)更多數(shù)據(jù)結(jié)構(gòu)知識(shí)
目錄
1.前言2.概念3.隊(duì)列的使用4.循環(huán)隊(duì)列5.雙端隊(duì)列6.經(jīng)典習(xí)題6.1隊(duì)列實(shí)現(xiàn)棧6.2棧實(shí)現(xiàn)隊(duì)列
7.總結(jié)
1.前言
同學(xué)們排隊(duì)等過(guò)車(chē)吧，最先去排隊(duì)的人就是第一個(gè)出隊(duì)上車(chē)的人。這就是日常生活中的隊(duì)列。在數(shù)據(jù)結(jié)構(gòu)中，隊(duì)列也是這樣的，最先進(jìn)隊(duì)的人最先出隊(duì)，那我們就通過(guò)這篇文章來(lái)了解隊(duì)列的詳細(xì)知識(shí)點(diǎn)吧。
2.概念
隊(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）
3.隊(duì)列的使用
在Java中，Queue是個(gè)接口，底層是通過(guò)鏈表實(shí)現(xiàn)的。 注意 Queue是個(gè)接口，在實(shí)例化時(shí)必須實(shí)例化LinkedList的對(duì)象，因?yàn)長(zhǎng)inkedList實(shí)現(xiàn)了Queue接口。
public static void main(String[] args) {
Queue
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());
}
}
4.循環(huán)隊(duì)列
實(shí)際中我們有時(shí)還會(huì)使用一種隊(duì)列叫循環(huán)隊(duì)列。如操作系統(tǒng)課程講解生產(chǎn)者消費(fèi)者模型時(shí)可以就會(huì)使用循環(huán)隊(duì)列。環(huán)形隊(duì)列通常使用數(shù)組實(shí)現(xiàn)。 設(shè)計(jì)循環(huán)隊(duì)列： 設(shè)計(jì)思路
1.首先要?jiǎng)?chuàng)建一個(gè)數(shù)組，我們?cè)俣x兩個(gè)參數(shù)來(lái)確定環(huán)形數(shù)組的下個(gè)元素存放的下標(biāo)end和第一個(gè)元素下標(biāo)first。 2.當(dāng)添加元素時(shí)，直接添加到end位置，end+1，但如果如上圖，走到7的位置，那么end能直接+1嗎？肯定是不行的，那么我們就可以把下一個(gè)下標(biāo)定義為(end+1)%queue.length。 3.那么我們?cè)撊绾闻袧M(mǎn)和判空呢？我們通常認(rèn)為如果end下標(biāo)等于first下標(biāo)就認(rèn)為空，如果end是下一個(gè)元素的下標(biāo)等于first元素下標(biāo)，那么就認(rèn)為隊(duì)列滿(mǎn)，這樣判斷我們就會(huì)浪費(fèi)一個(gè)空間來(lái)，所以設(shè)置數(shù)組大小的時(shí)候?yàn)镵+1
public class MyCircularQueue {
int[] queue;
int first=0;
int end=0;
MyCircularQueue(int k){
queue=new int[k+1];
}
public int Front(){
if(isEmpty()){
return -1;
}
return queue[first];
}
public int Rear(){
if (isEmpty()) {
return -1;
}
if (end==0){
return queue[queue.length-1];
}else {
return queue[end-1];
}
}
public Boolean enQueue( int value){
if(isFull()){
return false;
}
queue[end]=value;
end=(end+1)%queue.length;
return true;
}
public Boolean deQueue(){
if(isEmpty()){
return false;
}
first=(first+1)%queue.length;
return true;
}
public Boolean isEmpty(){
if(first==end){
return true;
}else {return false;}
}
public Boolean isFull(){
if((end+1)%queue.length==first){
return true;
} else {
return false;
}
}
}
5.雙端隊(duì)列
***雙端隊(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或者ArrayList的對(duì)象。 在實(shí)際工程中，使用Deque接口是比較多的，棧和隊(duì)列均可以使用該接口。
Deque
Deque
6.經(jīng)典習(xí)題
6.1隊(duì)列實(shí)現(xiàn)棧
使用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)后入先出（LIFO）的棧：OJ鏈接 解題思路
插入元素的時(shí)候，哪一個(gè)隊(duì)列不為空就插入哪一個(gè)隊(duì)列 刪除元素的時(shí)候，先把size-1個(gè)元素移到另外一個(gè)隊(duì)列，再刪除最會(huì)一個(gè)元素 易錯(cuò)點(diǎn)，不能定義stack.size()來(lái)表示從一個(gè)隊(duì)列進(jìn)入另一個(gè)隊(duì)列的元素，因?yàn)閟ize是一直在變的。
public class MyStack {
public Queue
public Queue
public int size=0;
public MyStack() {
sq1=new LinkedList<>();
sq2=new LinkedList<>();;
}
public void push(int x) {
if(!sq1.isEmpty()){
sq1.offer(x);
}
if(!sq2.isEmpty()){
sq2.offer(x);
}
if(sq1.isEmpty()&&sq2.isEmpty()){
sq1.offer(x);
}
size++;
}
public int pop() {
if(!sq1.isEmpty()){
for (int i=0;i int x= sq1.poll(); sq2.offer(x); } size--; return sq1.poll(); } else if(!sq2.isEmpty()){ for (int i=0;i int x= sq2.poll(); sq1.offer(x); } } size--; return sq2.poll(); } public int top() { int x=-1; if(!sq1.isEmpty()){ for (int i=0;i x= sq1.poll(); sq2.offer(x); } } else if(!sq2.isEmpty()){ for (int i=0;i x= sq2.poll(); sq1.offer(x); } } return x; } public boolean empty() { return sq1.isEmpty()&&sq2.isEmpty(); } } 6.2棧實(shí)現(xiàn)隊(duì)列 請(qǐng)你僅使用兩個(gè)棧實(shí)現(xiàn)先入先出隊(duì)列：OJ鏈接 解題思路 定義兩個(gè)棧s1，和s2，每次入隊(duì)列存入s1中，每次出隊(duì)列存入s2中。 當(dāng)要出隊(duì)列時(shí)，就把s1的元素依次出隊(duì)，進(jìn)入s2當(dāng)中，s2再出隊(duì)列 易錯(cuò)點(diǎn)，不能定義stack.size()來(lái)表示從s1進(jìn)入s2的元素，因?yàn)閟1的size是一直在變的。 class MyQueue { Stack Stack public MyQueue() { stack1=new Stack<>(); stack2=new Stack<>(); } public void push(int x) { stack1.push(x); } public int pop() { if(stack2.isEmpty()){ while(!stack1.isEmpty()){ stack2.push(stack1.pop()); } } return stack2.pop(); } public int peek() { if(stack2.isEmpty()){ while(!stack1.isEmpty()){ stack2.push(stack1.pop()); } } return stack2.peek(); } public boolean empty() { return stack2.isEmpty()&&stack1.isEmpty(); } } 7.總結(jié) 本篇文章主要介紹了隊(duì)列的使用，循環(huán)隊(duì)列，雙端隊(duì)列，以及如何用隊(duì)列實(shí)現(xiàn)棧，用棧實(shí)現(xiàn)隊(duì)列。 下期預(yù)告：二叉樹(shù) 柚子快報(bào)邀請(qǐng)碼778899分享：【數(shù)據(jù)結(jié)構(gòu)（六）】隊(duì)列 相關(guān)文章
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點(diǎn)和立場(chǎng)。
轉(zhuǎn)載請(qǐng)注明，如有侵權(quán)，聯(lián)系刪除。
CasasBahia跨境家居
