C語言棧與隊列面試題詳解

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

MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));//申請隊列類型

assert(obj);

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

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

returnobj;

voidmyQueuePush(MyQueue*obj,intx){

assert(obj);

StackPush(obj-pushST,x);//不管有沒有數(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棧頂元素，實現(xiàn)隊列先進(jìn)先出

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

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

intmyQueuePeek(MyQueue*obj){

assert(obj);

//如果popST數(shù)據(jù)為空，要從pushST里導(dǎo)入數(shù)據(jù)才能取到隊頭數(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è)計循環(huán)隊列

鏈接直達(dá)：

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

題目：

思路：

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

數(shù)組：

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

這樣分析下來再加上畫圖看似沒有什么缺陷，但是存在兩個問題？

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

問題1：

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

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

解決方案：

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

front==tail時是空tail下一個位置是front時，就是滿

代碼如下：

typedefstruct{

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

intfront;//隊頭

inttail;//隊尾

intk;//表示存的數(shù)據(jù)長度為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));//多開一個空間，便于后續(xù)區(qū)分空或滿

obj-front=obj-tail=0;

obj-k=k;//隊列存儲有效數(shù)據(jù)長度為k

returnobj;

boolmyCircularQueueEnQueue(MyCircularQueue*obj,intvalue){

if(myCircularQueueIsFull(obj))

returnfalse;//隊列已滿，不能插入數(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;//隊列為空，不能刪除

if(obj-front==obj-k)

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

else

obj-front++;

returntrue;

intmyCircularQueueFront(MyCircularQueue*obj){

if(myCircularQueueIsEmpty(obj))

return-1;//隊列為空，取不了

returnobj-a[obj-front];//返回隊頭

intmyCircularQueueRear(MyCircularQueue*obj){

if(myCircularQueueIsEmpty(obj))

return-1;//隊列為空，取不了

if(obj-tail==0)

returnobj-a[obj-//tail為0，隊尾在長度的最后一個位置

else

returnobj-a[obj-tail-1];

boolmyCircularQueueIsEmpty(MyCircularQueue*obj){

returnobj-front==obj-tail;//front==tail時為空

boolmyCircularQueueIsFull(MyCircularQueue*obj){

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

retur