C語(yǔ)言棧與隊(duì)列面試題詳解

第C語(yǔ)言棧與隊(duì)列面試題詳解MyQueue*myQueueCreate(){

MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));//申請(qǐng)隊(duì)列類型

assert(obj);

StackInit(obj-pushST);//初始化pushST

StackInit(obj-popST);//初始化popST

returnobj;

voidmyQueuePush(MyQueue*obj,intx){

assert(obj);

StackPush(obj-pushST,x);//不管有沒(méi)有數(shù)據(jù)，都插入

intmyQueuePop(MyQueue*obj){

assert(obj);

if(StackEmpty(obj-popST))//如果popST數(shù)據(jù)為空，要從pushST里導(dǎo)入數(shù)據(jù)才能刪除

while(!StackEmpty(obj-pushST))//pushST數(shù)據(jù)不為空，就一直向popST里導(dǎo)入數(shù)據(jù)

StackPush(obj-popST,StackTop(obj-pushST));//把pushST棧頂數(shù)據(jù)導(dǎo)到popST里

StackPop(obj-pushST);//導(dǎo)完后把pushST棧頂元素刪掉，方便后續(xù)繼續(xù)導(dǎo)

intfront=StackTop(obj-popST);//記錄popST棧頂元素

StackPop(obj-popST);//刪除popST棧頂元素，實(shí)現(xiàn)隊(duì)列先進(jìn)先出

returnfront;//返回棧頂數(shù)據(jù)

//取隊(duì)頭數(shù)據(jù)

intmyQueuePeek(MyQueue*obj){

assert(obj);

//如果popST數(shù)據(jù)為空，要從pushST里導(dǎo)入數(shù)據(jù)才能取到隊(duì)頭數(shù)據(jù)

if(StackEmpty(obj-popST))

while(!StackEmpty(obj-pushST))//pushST數(shù)據(jù)不為空，就一直向popST里導(dǎo)入數(shù)據(jù)

StackPush(obj-popST,StackTop(obj-pushST));//把pushST棧頂數(shù)據(jù)導(dǎo)到popST里

StackPop(obj-pushST);//導(dǎo)完后把pushST棧頂元素刪掉，方便后續(xù)繼續(xù)導(dǎo)

returnStackTop(obj-popST);//直接返回棧頂元素

boolmyQueueEmpty(MyQueue*obj){

returnStackEmpty(obj-pushST)StackEmpty(obj-popST);

voidmyQueueFree(MyQueue*obj){

assert(obj);

StackDestory(obj-pushST);

StackDestory(obj-popST);

free(obj);

}

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

鏈接直達(dá)：

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

題目：

思路：

此題可以用數(shù)組實(shí)現(xiàn)，也可以用鏈表實(shí)現(xiàn)，但其實(shí)是用數(shù)組更加方便些。

數(shù)組：

假設(shè)隊(duì)頭front和隊(duì)尾tail都指向第一個(gè)數(shù)據(jù)，在隊(duì)尾插入數(shù)據(jù)，tail隨著數(shù)據(jù)的插入跟著移動(dòng)，tail始終為最后一個(gè)數(shù)據(jù)的下一個(gè)位置。刪除數(shù)據(jù)只需要將隊(duì)頭front往后挪即可，不需要按照之前隊(duì)列的pop一樣刪完還挪動(dòng)數(shù)據(jù)，因?yàn)槭茄h(huán)鏈表，且數(shù)據(jù)是可以重復(fù)利用的。

這樣分析下來(lái)再加上畫(huà)圖看似沒(méi)有什么缺陷，但是存在兩個(gè)問(wèn)題？

什么情況下數(shù)組為空？什么情況下數(shù)組滿了？

問(wèn)題1：

當(dāng)tail=front時(shí)數(shù)組為空，看似沒(méi)什么問(wèn)題，但相等又要分兩種情況。先畫(huà)個(gè)圖：

由上圖得知，在情況一下，數(shù)組里確實(shí)是一個(gè)數(shù)據(jù)也沒(méi)有，并且tail也是等于front的，滿足數(shù)組為空的條件，但是在情況二下，數(shù)組的數(shù)據(jù)全滿，此時(shí)的tail和front同樣是相等的，這里數(shù)組不為空了，而是全滿，由此可見(jiàn)，是存在問(wèn)題的。

解決方案：

這里我們可以多開(kāi)一個(gè)空間，不存放數(shù)據(jù)，只是用來(lái)分別數(shù)組為空或滿。原理如下：當(dāng)數(shù)組長(zhǎng)度為4時(shí)，也就是說(shuō)實(shí)際能存放3個(gè)有效數(shù)據(jù)，另外一個(gè)空間用來(lái)判斷空或滿，此時(shí)判斷空或滿的條件如下：

front==tail時(shí)是空tail下一個(gè)位置是front時(shí)，就是滿

代碼如下：

typedefstruct{

int*a;//用數(shù)組模擬環(huán)形隊(duì)列

intfront;//隊(duì)頭

inttail;//隊(duì)尾

intk;//表示存的數(shù)據(jù)長(zhǎng)度為k

}MyCircularQueue;

boolmyCircularQueueIsFull(MyCircularQueue*obj);//前置聲明

boolmyCircularQueueIsEmpty(MyCircularQueue*obj);//前置聲明

MyCircularQueue*myCircularQueueCreate(intk){

MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//創(chuàng)建環(huán)形鏈表結(jié)構(gòu)

assert(obj);

obj-a=(int*)malloc(sizeof(int)*(k+1));//多開(kāi)一個(gè)空間，便于后續(xù)區(qū)分空或滿

obj-front=obj-tail=0;

obj-k=k;//隊(duì)列存儲(chǔ)有效數(shù)據(jù)長(zhǎng)度為k

returnobj;

boolmyCircularQueueEnQueue(MyCircularQueue*obj,intvalue){

if(myCircularQueueIsFull(obj))

returnfalse;//隊(duì)列已滿，不能插入數(shù)據(jù)

obj-a[obj-tail]=value;//賦值

if(obj-tail==obj-k)

obj-tail=0;//當(dāng)tail走到尾端

else

obj-tail++;

returntrue;

boolmyCircularQueueDeQueue(MyCircularQueue*obj){

if(myCircularQueueIsEmpty(obj))

returnfalse;//隊(duì)列為空，不能刪除

if(obj-front==obj-k)

obj-front=0;//當(dāng)front走到尾端

else

obj-front++;

returntrue;

intmyCircularQueueFront(MyCircularQueue*obj){

if(myCircularQueueIsEmpty(obj))

return-1;//隊(duì)列為空，取不了

returnobj-a[obj-front];//返回隊(duì)頭

intmyCircularQueueRear(MyCircularQueue*obj){

if(myCircularQueueIsEmpty(obj))

return-1;//隊(duì)列為空，取不了

if(obj-tail==0)

returnobj-a[obj-//tail為0，隊(duì)尾在長(zhǎng)度的最后一個(gè)位置

else

returnobj-a[obj-tail-1];

boolmyCircularQueueIsEmpty(MyCircularQueue*obj){

returnobj-front==obj-tail;//front==tail時(shí)為空

boolmyCircularQueueIsFull(MyCircularQueue*obj){

if(obj-tail==obj-kobj-front==0)

retur