第C語(yǔ)言循環(huán)隊(duì)列與用隊(duì)列實(shí)現(xiàn)棧問(wèn)題解析目錄循環(huán)隊(duì)列題目描述題目鏈接思路分析代碼實(shí)現(xiàn)用隊(duì)列實(shí)現(xiàn)棧題目描述題目鏈接思路分析代碼實(shí)現(xià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ì)列滿了，我們就不能插入下一個(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ì)列是否已滿。

題目鏈接

設(shè)計(jì)循環(huán)隊(duì)列

思路分析

循環(huán)隊(duì)列和普通隊(duì)列對(duì)比。

循環(huán)隊(duì)列：入隊(duì)需要尾插。出隊(duì)需要頭刪，刪除并不是真正的刪除，只需要使頭指針往后移動(dòng)就可以了，因?yàn)橐貜?fù)利用其空間。真正意義上只需要尾插罷了。尾插的話鏈表和順序表時(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ì)列是否為空，或者是否滿了。紅色的空間是多開(kāi)的一個(gè)空間。

3.循環(huán)隊(duì)列的關(guān)鍵在于判斷隊(duì)列是否為空或者隊(duì)列是否滿了。為空：只有當(dāng)tail==head才為空。

滿了：分兩種情況。情況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再++。

typedefstruct

int*a;

inthead;

inttail;

intk;

}MyCircularQueue;

boolmyCircularQueueIsEmpty(MyCircularQueue*obj);

boolmyCircularQueueIsFull(MyCircularQueue*obj);

MyCircularQueue*myCircularQueueCreate(intk)

//給結(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;

returnnew;

boolmyCircularQueueEnQueue(MyCircularQueue*obj,intvalue)

assert(obj);

if(myCircularQueueIsFull(obj))

returnfalse;

obj-a[obj-tail]=value;

if(obj-tail==obj-k)

obj-tail=0;

else

obj-tail++;

returntrue;

boolmyCircularQueueDeQueue(MyCircularQueue*obj)

assert(obj);

if(myCircularQueueIsEmpty(obj))

returnfalse;

if(obj-head==obj-k)

obj-head=0;

else

obj-head++;

returntrue;

intmyCircularQueueFront(MyCircularQueue*obj)

assert(obj);

if(myCircularQueueIsEmpty(obj))

return-1;

returnobj-a[obj-head];

intmyCircularQueueRear(MyCircularQueue*obj)

assert(obj);

if(myCircularQueueIsEmpty(obj))

return-1;

if(obj-tail==0)

returnobj-a[obj-

returnobj-a[obj-tail-1];

boolmyCircularQueueIsEmpty(MyCircularQueue*obj)

assert(obj);

returnobj-head==obj-tail;

boolmyCircularQueueIsFull(MyCircularQueue*obj)

assert(obj);

if(obj-head==0obj-tail==obj-k)

returntrue;

else

returnobj-head==obj-tail+1;

voidmyCircularQueueFree(MyCircularQueue*obj)

assert(obj);

free(obj-

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）。

用隊(duì)列實(shí)現(xiàn)棧

此題和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掉。

我遇到的bug

1.判斷到底哪個(gè)隊(duì)列是空隊(duì)列，可以用假設(shè)法。假設(shè)其中一個(gè)為空，另一個(gè)不為空，然后再做調(diào)整。這樣后續(xù)就方便了。

//假設(shè)后調(diào)整

Queue*emptyQ=obj-

Queue*nonEmptyQ=obj-

if(!QueueEmpty(obj-q1))

emptyQ=obj-

nonEmptyQ=obj-

2.移動(dòng)前k-1個(gè)元素到另一個(gè)隊(duì)列不能用遍歷。遍歷會(huì)麻煩，且每一次出隊(duì)，頭指針會(huì)自動(dòng)移動(dòng)。所以直接用算出隊(duì)列的長(zhǎng)度解決移動(dòng)前k-1元素。

typedefintQDataType;

typedefstructQueueNode

QDataTypedata;

structQueueNode*next;

}QNode;

typedefstructQueue

QNode*head;

QNode*tail;

//size_tsize;

}Queue;

voidQueueInit(Queue*pq);

voidQueueDestory(Queue*pq);

voidQueuePush(Queue*pq,QDataTypex);

voidQueuePop(Queue*pq);

boolQueueEmpty(Queue*pq);

size_tQueueSize(Queue*pq);

QDataTypeQueueFront(Queue*pq);

QDataTypeQueueBack(Queue*pq);

voidQueueInit(Queue*pq)

assert(pq);

pq-head=pq-tail=NULL;

voidQueueDestory(Queue*pq)

assert(pq);

QNode*cur=pq-head;

while(cur)

QNode*next=cur-next;

free(cur);

cur=next;

pq-head=pq-tail=NULL;

voidQueuePush(Queue*pq,QDataTypex)

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;

voidQueuePop(Queue*pq)

assert(pq