C語(yǔ)言超詳細(xì)講解棧與隊(duì)列實(shí)現(xiàn)實(shí)例

第C語(yǔ)言超詳細(xì)講解棧與隊(duì)列實(shí)現(xiàn)實(shí)例3.2測(cè)試結(jié)果

4.思考-2

為什么隊(duì)列用鏈表模擬比數(shù)組模擬更加合適？

棧的實(shí)現(xiàn)一般可以使用數(shù)組或者鏈表實(shí)現(xiàn)，相對(duì)而言數(shù)組的結(jié)構(gòu)實(shí)現(xiàn)更優(yōu)一些。因?yàn)閿?shù)組在尾上插入數(shù)據(jù)的代價(jià)小。

5.隊(duì)列的基本操作實(shí)現(xiàn)

5.1初始化隊(duì)列

voidQueueInit(Queue*pq)

assert(pq);

pq-_head=pq-_tail=NULL;

}

5.2隊(duì)尾入隊(duì)列

voidQueuePush(Queue*pq,QueueDatex)

assert(pq);

QueueNode*newnode=(QueueNode*)malloc(sizeof(QueueNode));

if(NULL==newnode)

printf("mallocfailed\n");

exit(-1);

newnode-next=NULL;

newnode-val=x;

if(NULL==pq-_tail)

pq-_head=pq-_tail=newnode;

else

pq-_tail-next=newnode;

pq-_tail=newnode;

}

5.3隊(duì)頭出隊(duì)列

voidQueuePop(Queue*pq)

assert(pq);

assert(!QueueIsEmpty(pq));

if(NULL==pq-_head-next)

free(pq-_head);

pq-_head=pq-_tail=NULL;

else

QueueNode*next=pq-_head-next;

free(pq-_head);

pq-_head=next;

}

代碼分析：

5.4隊(duì)列中有效元素的個(gè)數(shù)

intQueueSize(Queue*pq)

assert(pq);

intcount=0;

QueueNode*cur=pq-_head;

while(cur)

++count;

cur=cur-next;

returncount;

5.5判斷隊(duì)列是否為空

boolQueueIsEmpty(Queue*pq)

assert(pq);

returnpq-_head==NULL;

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

QueueDateQueueFront(Queue*pq)

assert(pq);

assert(!QueueIsEmpty(pq));

returnpq-_head-

5.7獲取隊(duì)尾的數(shù)據(jù)

QueueDateQueueBack(Queue*pq)

assert(pq);

assert(!QueueIsEmpty(pq));

returnpq-_tail-

5.8銷毀隊(duì)列

voidQueueDestory(Queue*pq)

assert(pq);

while(pq-_head)

if(pq-_head==pq-_tail)

free(pq-_head);

pq-_head=pq-_tail=NULL;

else

QueueNode*next=pq-_head-next;

free(pq-_head);

pq-_head=next;

注意：和隊(duì)頭出隊(duì)列一樣分析。

6.測(cè)試

6.1測(cè)試

voidtest1()

//插入數(shù)據(jù)

Queueq;

QueueI