LeetCode刷題記錄

• 🌐 我的博客主頁：iiiiiankor
• 🎯 如果你覺得我的內容對你有幫助，不妨點個贊👍、留個評論?，或者收藏?，讓我們一起進步！
• 📝 專欄系列：LeetCode 刷題日志
• 🌱 文章內容來自我的學習與實踐經驗，如果你有任何想法或問題，歡迎隨時在評論區交流討論。讓我們一起探索更多的可能！🚀

🚀LeetCode622.設計循環隊列

鏈接：LeetCode622.設計循環隊列

一、🌟題目描述🌟

二、🎨分析🎨

• 題目理解：
  這是讓我們實現的是一個 大小固定的循環隊列
  正常的大小固定的隊列如果滿了就不能插入了
  而這里所說的循環隊列 是隊尾和隊頭連在一起的
  所以我們首先想到的就是 利用鏈表實現循環隊列

鏈表實現分析

如下圖：
剛開始head和tail都指向一個頭！

這種結構下

• 插入數據只需要把數據放到tail節點，然后tail向后走
  如圖：push 1 2 3
  
• pop數據 只需要讓head走向下一個，數據清除或者不清楚無所謂，反正可以被替換，
  如圖：pop pop
  
  注意節點不需要釋放！
  而如果繼續插入數據：push 4 5 6 7
  
  可以看到此時已經滿了！
  但是，大家看一下我們設計的這個有沒有什么缺陷呢？
  ！對！ 我們可以看到！隊列什么時候滿呢？
  head==tail的時候滿
  那么什么時候為空呢？
  head==tail的時候為空！
  所以！ 這里判斷空和滿是有問題的！

那么解決方法是什么呢？

1. 給一個size記錄隊列的大小，循環隊列的節點數為k，每一次push的時候size++，pop時size–當head==tail 時，如果size為k說明已經滿了，如果size為0 則說明為空
2. 給一個flag 剛開始flag為0表示隊列為空，如果head==tail了 flag置為1，表示已經滿了，當再pop的時候，就把flag改成0表示未滿
3. 比較官方的做法：
   我們直接開辟k+1個鏈表節點，其中有一個節點不存儲有效數據
   判滿的條件就是 tail的下一個為head

如圖：push 4 5 6 7
只能插入4 5 6 到7的時候 tail->next==head 所以已經滿了，無法插入！

通常來說 結構就是這樣的：

但是這時候這個隊列還有別的問題嗎？
我們要實現 push pop 判空 判滿 獲取隊頭數據 獲取隊尾數據 等等…
我們可以發現，如果想要獲取隊尾數據 是比較麻煩的！！
因為我們的tail是下一個要push的位置而不是真正的隊尾
所以 我們如果想要解決，必須找到tail的前一個

• 方法1： 雙向鏈表
• 方法2：記錄尾的同時還要記錄尾的前一個

顯然 都是麻煩事！ 所以利用鏈表是不方便實現的

所以我們選擇用數組實現

三、💥題解💥

我們利用數組實現
先簡單分析一下：

對于一個數組，我們要實現循環隊列，那么

因為隊列是循環的，所以什么時候隊列是滿的呢？
這就和我們鏈表部分分析的一樣了，有三種方法！

1. flag標識
2. size記錄隊列大小
3. 多開辟一個空間 ?

我們采取對數組多開辟一個空間的方法：開辟(k+1)個空間

---

下面是具體接口實現：
?代碼中都有詳細注釋哦！！?

定義隊列結構

typedef struct {int* a;//動態開辟數組int head;//隊頭int tail;//隊尾int k;//隊的大小,因為后面傳參的時候不會再傳 k 所以我們定義在結構體里面
} MyCircularQueue;

Create(創建隊列）

我們以k=5為例

	首先創建一個隊列結構然后開辟出隊列中大小為`k+1`的數組然后把結構中的head和tail初始化為0

如圖：

判斷是否為空

前面我們對鏈表實現的分析的時候
我們已經分析過了
當`head`==`tail`的時候，為空
只是這里的`head`和`tail`變成了下標而不是節點

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//判斷是不是為空 只需要判斷tail是不是等于headreturn obj->head==obj->tail;}

判斷是不是滿了

這里是稍微有點麻煩的

首先我們要知道，判斷滿的條件是tail的下一個等于head
但是這是數組 ！not 鏈表
如果是環形鏈表，他會自動實現很自然的循環
但是鏈表不一樣
鏈表會走到一個邊界，所以我們需要考慮tail的下一個是誰？
我們定義一個next來標識下一個
一般的tail的下一個就是tail+1 ，如下圖

但是存在特殊情況：如果tail已經是最后一個位置了，那么這時候其實他的下一個就是返回開頭0

找到下一個？
1.  定義一個next=tail+1如果tail==k+1那么next就為02.  利用取模我們知道一共有k+1個空間所以下標的返回時 0~ k這時候 next=(tail+1)%(k+1)不管next是不是超過了數組的返回，結果都是正確的

代碼：

bool myCircularQueueIsFull(MyCircularQueue* obj) {//判斷是不是滿了//一般是判斷tail的下一個是不是 head//需要考慮tail的下一個是什么？int next=obj->tail+1;if(next==obj->k+1){next=0;}//next=(obj->tail+1)%(k+1);if(next==obj->head)return true;elsereturn false;
}

獲取隊頭元素

隊頭其實就是`head`
所以只需要訪問數組中的`head`位置處的元素就可以了

但是需要注意：如果隊列為空，返回-1

int myCircularQueueFront(MyCircularQueue* obj) {//如果隊列為空 返回-1if(myCircularQueueIsEmpty(obj)){return -1;}//隊頭就是 headreturn obj->a[obj->head];
}

獲取隊尾元素

我們可以看到tail表示的是下一個Push的位置
而如果我們想獲得隊尾元素
應該是獲得tail的前一個元素

所以我們定義一個prev來找到tail的前一個元素

但是也會有特殊情況

如果是這種情況，也就是 tail已經折回去了
tail為0 prev應該為5
怎么找到prev呢？
注意 如果我們讓tail+k+1 ，tail就變成了6
這時候tail-1是不是就等于prev了?
tail為0實際上就說明了tail已經走到數組最后一個位置的后一個了

---

細細剖析理解一下這里：


而我們再看正確的情況是不是滿足呢？

顯然 滿足的！

這樣 我們就有兩種情況控制邊界情況
1. if判斷
2. 利用取模
具體看個人喜歡用那種，小編這里就用第一種啦（比較直觀）

int myCircularQueueRear(MyCircularQueue* obj) {//首先判斷是否為空if(myCircularQueueIsEmpty(obj)){return -1;}//如果不為空//找到tail的前一個int prev=obj->tail-1;if(obj->tail==0)prev=obj->k;return obj->a[prev];
}

push接口

我們開始以k=5為例，即開辟了一個大小為6的數組

正常情況下，我們push只需要把tail位置放入元素，然后tail++就可以了
（向后走一步）
如圖 我們把一個空的隊列 push 1 2 3 4
操作過程：

但是會存在特殊情況
如圖：

這時候怎么push呢？tail已經走到末尾了！

1. 直接控制：正常走的話tail+1，tail就變成了6
   所以 如果tail==k+1 那么我們讓tail=0就可以了！
2. 利用取模
   因為數組的總空間就是k+1
   所以如果我們tail等于6了，說明tail應該走到0
   所以讓tail%=（k+1），也就是 6%6==0

還有一個問題就是
什么時候push失敗呢？

當滿的時候會push 失敗！

push代碼：

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//首先判斷是不是滿了//如果滿了 push失敗--返回falseif(myCircularQueueIsFull(obj)){return false;}//如果不滿 直接插入就可以了obj->a[obj->tail]=value;//然后tail需要移動！obj->tail++;//如果移動之后tail走到末尾了 tail返回到數組的最開始if(obj->tail==obj->k+1){obj->tail=0;}return true;
}

pop接口

我們來看一個例子

如果操作為 pop pop
那么 head就需要往前走兩步，從而實現刪除的效果

但是如果繼續pop
操作： pop pop

可以看到，此時隊列已經空了！
此時繼續pop就返回false（失敗）

正常情況下pop只需要讓head向后走，就可以了
因為前面的數據可以隨意被覆蓋就相當于被刪了

但是也會有特殊情況，即當head走到邊界

此時如果繼續pop head++就變成了6
但是head應該返回到數組的頭部0
所以 解決方法依舊有兩個：

1. 如果head==k+1
   那么 head變成0
2. 取模：如果head++之后變成6
   那么head=head%（k+1）

代碼：

bool myCircularQueueDeQueue(MyCircularQueue* obj) {//如果 隊列已經空空了 就返回falseif(myCircularQueueIsEmpty(obj)){return false;}//如果隊列不為空obj->head++;if(obj->head==obj->k+1){obj->head=0;}return true;
}

銷毀

銷毀就很簡單了
只需要把結構銷毀就可以了

注意：銷毀結構之前，需要把結構中malloc的動態數組釋放
否則容易造成內存泄漏！！

void myCircularQueueFree(MyCircularQueue* obj) {//首先釋放數組空間free(obj->a);//然后釋放隊列free(obj);
}

總結：這道題還是比較麻煩的！
很多細節：比如邊界 需要我們考慮全面！
下面是總代碼供參考！

??總代碼??

//使用數組實現typedef struct {int* a;//動態開辟數組int head;//隊頭int tail;//隊尾int k;//隊的大小,因為后面傳參的時候不會再傳k 所以我們定義在結構體里面
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->a=(int*)malloc(sizeof(int)*(k+1));obj->k=k;obj->head=obj->tail=0;return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//判斷是不是為空 只需要判斷tail是不是等于headreturn obj->head==obj->tail;}bool myCircularQueueIsFull(MyCircularQueue* obj) {//判斷是不是滿了//一般是判斷tail的下一個是不是 head//需要考慮tail的下一個是什么？int next=obj->tail+1;if(next==obj->k+1){next=0;}//next=(obj->tail+1)%(k+1);if(next==obj->head)return true;elsereturn false;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//首先判斷是不是滿了//如果滿了 push失敗--返回falseif(myCircularQueueIsFull(obj)){return false;}//如果不滿 直接插入就可以了obj->a[obj->tail]=value;//然后tail需要移動！obj->tail++;//如果移動之后tail走到末尾了 tail返回到數組的最開始if(obj->tail==obj->k+1){obj->tail=0;}return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {//如果 隊列已經空空了 就返回falseif(myCircularQueueIsEmpty(obj)){return false;}//如果隊列不為空obj->head++;if(obj->head==obj->k+1){obj->head=0;}return true;
}int myCircularQueueFront(MyCircularQueue* obj) {//如果隊列為空 返回-1if(myCircularQueueIsEmpty(obj)){return -1;}//隊頭就是 headreturn obj->a[obj->head];
}int myCircularQueueRear(MyCircularQueue* obj) {//首先判斷是否為空if(myCircularQueueIsEmpty(obj)){return -1;}//如果不為空//找到tail的前一個int prev=obj->tail-1;if(obj->tail==0)prev=obj->k;return obj->a[prev];
}void myCircularQueueFree(MyCircularQueue* obj) {//首先釋放數組空間free(obj->a);//然后釋放隊列free(obj);
}

💥💥最后貼一個題 💥💥

這個題適合 LeetCode622.循環隊列中的邊界問題相關的
看一下你學廢了嗎

5.現有一循環隊列，其隊頭指針為front，隊尾指針為rear；循環隊列長度為N。
其隊內有效長度為？(假設隊頭不存放數據)
A (rear - front + N) % N + 1
B (rear - front + N) % N
C ear - front) % (N + 1)
D (rear - front + N) % (N - 1)

?感謝閱讀~ ?
??碼字不易，給個贊吧~??