C語(yǔ)言循環(huán)隊(duì)列與用隊(duì)列實(shí)現(xiàn)棧問(wèn)題解析
循環(huán)隊(duì)列
循環(huán)隊(duì)列： 循環(huán)隊(duì)列是一種線性數(shù)據(jù)結(jié)構(gòu)，其操作表現(xiàn)基于 FIFO（先進(jìn)先出）原則并且隊(duì)尾被連接在隊(duì)首之后以形成一個(gè)循環(huán)循環(huán)隊(duì)列的好處：可以重新利用隊(duì)列的空間。我們可以利用這個(gè)隊(duì)列之前用過(guò)的空間。在一個(gè)普通隊(duì)列里，一旦一個(gè)隊(duì)列滿(mǎn)了，我們就不能插入下一個(gè)元素，即使在隊(duì)列前面仍有空間。但是使用循環(huán)隊(duì)列，我們能使用這些空間去存儲(chǔ)新的值。
題目描述
設(shè)計(jì)你的循環(huán)隊(duì)列實(shí)現(xiàn)。
你的實(shí)現(xiàn)應(yīng)該支持如下操作：
MyCircularQueue(k): 構(gòu)造器，設(shè)置隊(duì)列長(zhǎng)度為 k 。
Front: 從隊(duì)首獲取元素。如果隊(duì)列為空，返回 -1 。
Rear: 獲取隊(duì)尾元素。如果隊(duì)列為空，返回 -1 。
enQueue(value): 向循環(huán)隊(duì)列插入一個(gè)元素。如果成功插入則返回真。
deQueue(): 從循環(huán)隊(duì)列中刪除一個(gè)元素。如果成功刪除則返回真。
isEmpty(): 檢查循環(huán)隊(duì)列是否為空。
isFull(): 檢查循環(huán)隊(duì)列是否已滿(mǎn)。
題目鏈接
思路分析
循環(huán)隊(duì)列和普通隊(duì)列對(duì)比。
循環(huán)隊(duì)列：入隊(duì)需要尾插。出隊(duì)需要頭刪，刪除并不是真正的刪除，只需要使頭指針往后移動(dòng)就可以了，因?yàn)橐貜?fù)利用其空間。真正意義上只需要尾插罷了。尾插的話(huà)鏈表和順序表時(shí)間復(fù)雜度相同。綜上所述：所以循環(huán)隊(duì)列用順序表或者鏈表實(shí)現(xiàn)都可以，差異不大。要真正的誰(shuí)更優(yōu)，因?yàn)轫樞虮砦锢砜臻g是連續(xù)的，CPU緩存命中率高。所以順序表更好一點(diǎn)。
普通隊(duì)列：入隊(duì)需要尾插，出隊(duì)需要頭刪，頭刪需要真正的刪除，但是順序表頭刪后還需要覆蓋，效率低，所以用單鏈表實(shí)現(xiàn)。
思路 ：
1.創(chuàng)建循環(huán)隊(duì)列結(jié)構(gòu)體，包含一個(gè)順序表a，頭指針和尾指針head和tail，隊(duì)列的長(zhǎng)度k。
2.要為隊(duì)列多開(kāi)一個(gè)空間，這樣可以正確判斷隊(duì)列是否為空，或者是否滿(mǎn)了。紅色的空間是多開(kāi)的一個(gè)空間。
3.循環(huán)隊(duì)列的關(guān)鍵在于判斷隊(duì)列是否為空或者隊(duì)列是否滿(mǎn)了。為空：只有當(dāng)tail == head才為空。
滿(mǎn)了：分兩種情況。情況1.當(dāng)tail == 隊(duì)列長(zhǎng)度(k) && head == 0時(shí)
情況2：當(dāng)tail+1 == head時(shí)
代碼實(shí)現(xiàn)
代碼寫(xiě)好后。經(jīng)過(guò)我數(shù)十次的調(diào)試，bug終于調(diào)完。
說(shuō)一說(shuō)我遇到的bug：
1.第一次提交發(fā)現(xiàn)循環(huán)隊(duì)列的創(chuàng)建失敗。原因是沒(méi)有對(duì)循環(huán)隊(duì)列的結(jié)構(gòu)體進(jìn)行初始化。
2.在獲取尾部元素的時(shí)候報(bào)錯(cuò)。漏掉了一個(gè)特殊情況，就是假如尾部的元素在第一個(gè)怎么辦？這時(shí)候tail-1就變?yōu)?1了。數(shù)組產(chǎn)生了越界。這時(shí)候報(bào)的錯(cuò)誤是一堆看不懂的內(nèi)存錯(cuò)誤，讓人摸不著頭腦。
3.在入隊(duì)的時(shí)候發(fā)生錯(cuò)誤。邏輯錯(cuò)誤。要牢記tail指向的是即將入隊(duì)的空間。應(yīng)該先入隊(duì)，tail再++。
typedef struct
{
int* a;
int head;
int tail;
int k;
} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj) ;
bool myCircularQueueIsFull(MyCircularQueue* obj) ;
MyCircularQueue* myCircularQueueCreate(int k)
{
//給結(jié)構(gòu)體指針變量開(kāi)辟空間，否則為野指針。
MyCircularQueue* new =(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
int* b = (int*)malloc(sizeof(int)*(k+1));
new->a = b;
new->head = 0;
new->tail = 0;
new->k = k;
return new;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
assert(obj);
if(myCircularQueueIsFull(obj))
{
return false;
}
obj->a[obj->tail] = value;
if(obj->tail == obj->k)
{
obj->tail = 0;
}
else
{
obj->tail++;
}
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
assert(obj);
if(myCircularQueueIsEmpty(obj))
{
return false;
}
if(obj->head == obj->k)
{
obj->head = 0;
}
else
{
obj->head++;
}
return true;
}
int myCircularQueueFront(MyCircularQueue* obj)
{
assert(obj);
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->a[obj->head];
}
int myCircularQueueRear(MyCircularQueue* obj)
{
assert(obj);
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
if(obj->tail == 0)
{
return obj->a[obj->k];
}
return obj->a[obj->tail-1];
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
assert(obj);
return obj->head == obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
assert(obj);
if(obj->head==0 && obj->tail == obj->k)
{
return true;
}
else
{
return obj->head == obj->tail+1;
}
}
void myCircularQueueFree(MyCircularQueue* obj)
{
assert(obj);
free(obj->a);
free(obj);
}
用隊(duì)列實(shí)現(xiàn)棧
用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧的基本功能。用C語(yǔ)言做，需要先創(chuàng)建兩個(gè)隊(duì)列。
題目描述
請(qǐng)你僅使用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop 和 empty）。
題目鏈接
思路分析
此題和C語(yǔ)言循環(huán)隊(duì)列與用隊(duì)列實(shí)現(xiàn)棧問(wèn)題解析。差不多。
思路：
1.壓棧就是誰(shuí)不為空就往誰(shuí)里面進(jìn)行入隊(duì)。
2.出棧就是先把不為空的一個(gè)隊(duì)列里面的前k-1個(gè)元素入隊(duì)到為空那個(gè)隊(duì)列。然后再把不為空那個(gè)隊(duì)列的元素pop掉。
代碼實(shí)現(xiàn)
我遇到的bug
1.判斷到底哪個(gè)隊(duì)列是空隊(duì)列，可以用假設(shè)法。假設(shè)其中一個(gè)為空，另一個(gè)不為空，然后再做調(diào)整。這樣后續(xù)就方便了。
//假設(shè)后調(diào)整
Queue* emptyQ = &obj->q1;
Queue* nonEmptyQ = &obj->q2;
if(!QueueEmpty(&obj->q1))
{
emptyQ = &obj->q2;
nonEmptyQ = &obj->q1;
}
2.移動(dòng)前k-1個(gè)元素到另一個(gè)隊(duì)列不能用遍歷。遍歷會(huì)麻煩，且每一次出隊(duì)，頭指針會(huì)自動(dòng)移動(dòng)。所以直接用算出隊(duì)列的長(zhǎng)度解決移動(dòng)前k-1元素。
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
//size_t size;
}Queue;
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
bool QueueEmpty(Queue* pq);
size_t QueueSize(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
void QueueDestory(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
assert(newnode);
newnode->data = x;
newnode->next = NULL;
if (pq->tail == NULL)
{
assert(pq->head == NULL);
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head && pq->tail);
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
size_t QueueSize(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
size_t size = 0;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head);
return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->tail);
return pq->tail->data;
}
//創(chuàng)建兩個(gè)隊(duì)列
typedef struct
{
Queue q1;
Queue q2;
} MyStack;
//初始化兩個(gè)隊(duì)列
MyStack* myStackCreate()
{
MyStack* new = (MyStack*)malloc(sizeof(MyStack));
assert(new);
QueueInit(&new->q1);
QueueInit(&new->q2);
return new;
}
//誰(shuí)不為空就在誰(shuí)里面入隊(duì)
void myStackPush(MyStack* obj, int x)
{
assert(obj);
if(!QueueEmpty(&obj->q2))
{
QueuePush(&obj->q2, x);
}
else
{
QueuePush(&obj->q1, x);
}
}
int myStackPop(MyStack* obj)
{
assert(obj);
//假設(shè)后調(diào)整
Queue* emptyQ = &obj->q1;
Queue* nonEmptyQ = &obj->q2;
if(!QueueEmpty(&obj->q1))
{
emptyQ = &obj->q2;
nonEmptyQ = &obj->q1;
}
while(QueueSize(nonEmptyQ) > 1)
{
int front = QueueFront(nonEmptyQ);
QueuePush(emptyQ, front);
QueuePop(nonEmptyQ);
}
int top = QueueFront(nonEmptyQ);
QueuePop(nonEmptyQ);
return top;
}
int myStackTop(MyStack* obj)
{
assert(obj);
int ret = 0;
if(!QueueEmpty(&obj->q1))
{
ret = QueueBack(&obj->q1);
}
else
{
ret = QueueBack(&obj->q2);
}
return ret;
}
bool myStackEmpty(MyStack* obj)
{
assert(obj);
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj)
{
assert(obj);
QueueDestory(&obj->q1);
QueueDestory(&obj->q2);
free(obj);
}
到此這篇關(guān)于C語(yǔ)言循環(huán)隊(duì)列與用隊(duì)列實(shí)現(xiàn)棧問(wèn)題解析的文章就介紹到這了,更多相關(guān)C語(yǔ)言 循環(huán)隊(duì)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C語(yǔ)言執(zhí)行程序時(shí)遇到的常見(jiàn)問(wèn)題及解決
這篇文章主要介紹了C語(yǔ)言執(zhí)行程序時(shí)遇到的常見(jiàn)問(wèn)題及解決方案，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-03-03
這篇文章主要為大家詳細(xì)介紹了C++多態(tài)與虛函數(shù)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2022-07-07
C++?boost?thread庫(kù)用法詳細(xì)講解
Boost是為C++語(yǔ)言標(biāo)準(zhǔn)庫(kù)提供擴(kuò)展的一些C++程序庫(kù)的總稱(chēng)。Boost庫(kù)是一個(gè)可移植、提供源代碼的C++庫(kù)，作為標(biāo)準(zhǔn)庫(kù)的后備，是C++標(biāo)準(zhǔn)化進(jìn)程的開(kāi)發(fā)引擎之一，是為C++語(yǔ)言標(biāo)準(zhǔn)庫(kù)提供擴(kuò)展的一些C++程序庫(kù)的總稱(chēng)2022-11-11
C++?STL中五個(gè)常用算法使用教程及實(shí)例講解
本文主要介紹了C++?STL算法中常見(jiàn)的五個(gè)算法的使用教程并附上了案例詳解,對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-11-11
C++中使用哈希表(unordered_map)的一些常用操作方法
C++標(biāo)準(zhǔn)庫(kù)中使用的unordered_map底層實(shí)現(xiàn)是哈希表,下面這篇文章主要給大家介紹了關(guān)于C++中使用哈希表(unordered_map)的一些常用操作方法,需要的朋友可以參考下2022-03-03
本篇文章是對(duì)《C和指針》這本書(shū)的學(xué)習(xí)做了筆記介紹。需要的朋友參考下2013-05-05
詳解C語(yǔ)言中return返回函數(shù)局部變量的問(wèn)題
本文主要介紹了C語(yǔ)言中return返回函數(shù)局部變量的問(wèn)題，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-08-08
這篇文章主要介紹了C++各種輸出數(shù)據(jù)類(lèi)型,在C++中，可以使用cout對(duì)象和插入運(yùn)算符<<輸出各種數(shù)據(jù)類(lèi)型，包括整數(shù)類(lèi)型、浮點(diǎn)數(shù)類(lèi)型、字符類(lèi)型、字符串類(lèi)型和布爾類(lèi)型，需要的朋友可以參考下2023-06-06
類(lèi)是創(chuàng)建對(duì)象的模板，一個(gè)類(lèi)可以創(chuàng)建多個(gè)對(duì)象，每個(gè)對(duì)象都是類(lèi)類(lèi)型的一個(gè)變量；創(chuàng)建對(duì)象的過(guò)程也叫類(lèi)的實(shí)例化。每個(gè)對(duì)象都是類(lèi)的一個(gè)具體實(shí)例（Instance），擁有類(lèi)的成員變量和成員函數(shù)2021-08-08
C++實(shí)現(xiàn)LeetCode(121.買(mǎi)賣(mài)股票的最佳時(shí)間)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(121.買(mǎi)賣(mài)股票的最佳時(shí)間),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07