第C++數(shù)據(jù)結(jié)構(gòu)深入探究棧與隊(duì)列目錄1.棧1.1棧的概念1.2棧的實(shí)現(xiàn)2.隊(duì)列2.1隊(duì)列的概念2.2隊(duì)列的實(shí)現(xiàn)3.棧和隊(duì)列面試題3.1括號(hào)匹配問(wèn)題3.2用隊(duì)列實(shí)現(xiàn)棧3.3用棧實(shí)現(xiàn)隊(duì)列3.4設(shè)計(jì)循環(huán)隊(duì)列

1.棧

1.1棧的概念

棧：一種特殊的線性表，其只允許在固定的一端進(jìn)行插入和刪除元素操作。進(jìn)行數(shù)據(jù)插入和刪除操作的一端稱(chēng)為棧頂，另一端稱(chēng)為棧底。棧中的數(shù)據(jù)元素遵守后進(jìn)先出LIFO（LastInFirstOut）的原則。

壓棧：棧的插入操作叫做進(jìn)棧/壓棧/入棧，入數(shù)據(jù)在棧頂。

出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂。

1.2棧的實(shí)現(xiàn)

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

Stack.h

#pragmaonce

#includestdio.h

#includeassert.h

#includestdlib.h

typedefintbool;

#defineTRUE1;

#defineFALSE0;

typedefintSTDataType;

structStack

STDataType*a;

inttop;//棧頂

intcapacity;//容量，方便增容

//typedefstructStackST;

typedefstructStackStack;

//初始化

voidStackInit(Stack*pst);

voidStackDestroy(Stack*pst);

voidStackPush(Stack*pst,STDataTypex);

voidStackPop(Stack*pst);

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

STDataTypeStackTop(Stack*pst);

//判斷棧是否為空,空返回1非空返回0

//intStackEmpty(Stack*pst);

boolStackEmpty(Stack*pst);

//棧中數(shù)據(jù)個(gè)數(shù)

intStackSize(Stack*pst);

Stack.c

#include"Stack.h"

//初始化

voidStackInit(Stack*pst)

assert(pst);

/*pst-a=NULL;

pst-top=0;

pst-capacity=0;*/

//開(kāi)始就申請(qǐng)空間，好處在于空間不夠時(shí)直接容量*2即可(如果剛開(kāi)始是0就要單獨(dú)處理)

pst-a=malloc(sizeof(STDataType)*4);

pst-top=0;

pst-capacity=4;

voidStackDestroy(Stack*pst)

assert(pst);

free(pst-

pst-a=NULL;

pst-capacity=pst-top=0;

voidStackPush(Stack*pst,STDataTypex)

assert(pst);

//從top為0的位置開(kāi)始放

//如果滿了就增容

if(pst-top==pst-capacity)

STDataType*tmp=(STDataType*)realloc(pst-a,sizeof(STDataType)*pst-capacity*2);

if(tmp==NULL)

//如果開(kāi)辟空間失敗

printf("reallocfail\n");

exit(-1);//結(jié)束整個(gè)程序(-1表示異常退出)

pst-a=tmp;

pst-capacity*=2;

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

pst-a[pst-top]=x;

pst-top++;

voidStackPop(Stack*pst)

assert(pst);//不能是空指針

assert(!StackEmpty(pst));//棧內(nèi)還有元素才能出戰(zhàn)

pst-top--;

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

STDataTypeStackTop(Stack*pst)

assert(pst);

assert(!StackEmpty(pst));

returnpst-a[pst-top-1];

//判斷棧是否為空,空返回1非空返回0

boolStackEmpty(Stack*pst)

assert(pst);

returnpst-top==0;

intStackSize(Stack*pst)

assert(pst);

returnpst-

}

test.c

#include"Stack.h"

//對(duì)棧操作的測(cè)試

voidTestStack()

Stackst;

StackInit(st);

StackPush(st,1);

StackPush(st,2);

StackPush(st,3);

StackPush(st,4);

//棧遍歷數(shù)據(jù)

while(!StackEmpty(st))

printf("%d",StackTop(st));

StackPop(st);

//4321

StackDestroy(st);

intmain()

TestStack();

return0;

}

2.隊(duì)列

2.1隊(duì)列的概念

隊(duì)列：只允許在一端進(jìn)行插入數(shù)據(jù)操作，在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表，隊(duì)列具有先進(jìn)先出FIFO(FirstInFirstOut)

入隊(duì)列：進(jìn)行插入操作的一端稱(chēng)為隊(duì)尾

出隊(duì)列：進(jìn)行刪除操作的一端稱(chēng)為隊(duì)頭

2.2隊(duì)列的實(shí)現(xiàn)

Queue.h

#pragmaonce

#includestdio.h

#includeassert.h

#includestdlib.h

#includestdbool.h

typedefintQDataType;

//隊(duì)列中的一個(gè)結(jié)點(diǎn)

typedefstructQueueNode

structQueueNode*next;

QDataTypedata;

}QueueNode;

//隊(duì)列(由于需要兩個(gè)指針，所以用結(jié)構(gòu)體定義)

typedefstructQueue

QueueNode*head;//頭指針

QueueNode*tail;//尾指針

}Queue;

//初始化

voidQueueInit(Queue*pq);

voidQueueDestroy(Queue*pq);

voidQueuePush(Queue*pq,QDataTypex);

voidQueuePop(Queue*pq);

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

QDataTypeQueueFront(Queue*pq);

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

QDataTypeQueueBack(Queue*pq);

boolQueueEmpty(Queue*pq);

//計(jì)算隊(duì)列元素個(gè)數(shù)

intQueueSize(Queue*pq);

Queue.c

#include"Queue.h"

//初始化

voidQueueInit(Queue*pq)

assert(pq);

//不帶哨兵位

pq-head=pq-tail=NULL;

voidQueueDestroy(Queue*pq)

assert(pq);

QueueNode*cur=pq-head;

while(cur)

QueueNode*next=cur-next;

free(cur);

cur=next;

pq-head=pq-tail=NULL;

boolQueueEmpty(Queue*pq)

assert(pq);

returnpq-head==NULL;//等于空就為真,不為空就是假

voidQueuePush(Queue*pq,QDataTypex)

assert(pq);

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

if(newnode==NULL)//申請(qǐng)空間失敗

printf("mallocfail\n");

exit(-1);

newnode-data=x;

newnode-next=NULL;

if(pq-tail==NULL)

pq-head=pq-tail=newnode;

else

pq-tail-next=newnode;

pq-tail=newnode;

voidQueuePop(Queue*pq)

assert(pq);

assert(!QueueEmpty(pq));//空隊(duì)列也不能調(diào)用出隊(duì)操作

if(pq-head-next==NULL)//只有一個(gè)結(jié)點(diǎn)的情況(如果不單獨(dú)考慮，那當(dāng)只有一個(gè)結(jié)點(diǎn)時(shí)，tail會(huì)仍然指向曾經(jīng)的隊(duì)尾)

free(pq-head);

pq-head=pq-tail=NULL;

else

QueueNode*next=pq-head-next;

free(pq-head);

pq-head=next;

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

QDataTypeQueueFront(Queue*pq)

assert(pq);

assert(!QueueEmpty(pq));

returnpq-head-data;

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

QDataTypeQueueBack(Queue*pq)

assert(pq);

assert(!QueueEmpty(pq));

returnpq-tail-data;

intQueueSize(Queue*pq)

intsize=0;

QueueNode*cur=pq-head;

while(cur)

size++;

cur=cur-next;

returnsize;

}

test.c

#include"Queue.h"

//對(duì)隊(duì)列操作的測(cè)試

voidTestQueue()

Queueq;

QueueInit(

QueuePush(q,1);

QueuePush(q,2);

QueuePush(q,3);

QueuePush(q,4);

printf("%d\n",QueueSize(q));//4

while(!QueueEmpty(q))

printf("%d",QueueFront(q));

QueuePop(

//1234

QueueDestroy(

intmain()

TestQueue();

return0;

}

3.棧和隊(duì)列面試題

3.1括號(hào)匹配問(wèn)題

boolisValid(char*s)

Stackst;

StackInit(st);

while(*s)

//左括號(hào)入棧，右括號(hào)找最近的左括號(hào)匹配

if(*s=='['||*s=='('||*s=='{')

StackPush(st,*s);

s++;

else

if(StackEmpty(st))//只有后括號(hào)的情況

StackDestroy(st);

returnfalse;

chartop=StackTop(st);

//不匹配的情況

if((top=='['*s!=']')

||(top=='('*s!=')')

||(top=='{'*s!='}'))

StackDestroy(st);

returnfalse;

else//匹配的情況

StackPop(st);

s++;

//如果最后棧內(nèi)為空才說(shuō)明是匹配的(防止最后棧內(nèi)還剩下前括號(hào)的情況)

boolret=StackEmpty(st);

StackDestroy(st);

returnret;

//特別注意:在return之前需要先把棧銷(xiāo)毀掉

}

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

//思路:

//入棧:向不為空的隊(duì)列入數(shù)據(jù),始終保持另一個(gè)隊(duì)列為空

//出棧:前size-1個(gè)數(shù)據(jù)導(dǎo)入空隊(duì)列，刪除最后一個(gè)

typedefstruct

Queueq1;

Queueq2;

}MyStack;

//*為什么下面代碼傳參都要傳obj-q1/q2？

//因?yàn)閼?yīng)該傳入函數(shù)中的是隊(duì)列的指針

MyStack*myStackCreate()

MyStack*pst=(MyStack*)malloc(sizeof(MyStack));

QueueInit(pst-

QueueInit(pst-

returnpst;

voidmyStackPush(MyStack*obj,intx)

//往不為空的隊(duì)列里入數(shù)據(jù)

if(!QueueEmpty(obj-q1))

QueuePush(obj-q1,x);

else

QueuePush(obj-q2,x);

intmyStackPop(MyStack*obj)

//假設(shè)q1為空q2不為空

Queue*pEmpty=obj-

Queue*pNonEmpty=obj-

if(!QueueEmpty(obj-q1))

pEmpty=obj-

pNonEmpty=obj-

//取出前size-1個(gè)插入空隊(duì)列

while(QueueSize(pNonEmpty)1)

QueuePush(pEmpty,QueueFront(pNonEmpty));

QueuePop(pNonEmpty);

//"干掉"最后一個(gè)

intfront=QueueBack(pNonEmpty);

QueuePop(pNonEmpty);

returnfront;

intmyStackTop(MyStack*obj)

if(!QueueEmpty(obj-q1))

returnQueueBack(obj-

else

returnQueueBack(obj-

boolmyStackEmpty(MyStack*obj)

returnQueueEmpty(obj-q1)QueueEmpty(obj-

voidmyStackFree(MyStack*obj)

//先釋放兩個(gè)隊(duì)列，再釋放malloc出來(lái)的結(jié)構(gòu)體

QueueDestroy(obj-

QueueDestroy(obj-

free(obj);

}

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

typedefstruct

StackpushST;

StackpopST;

}MyQueue;

MyQueue*myQueueCreate()

MyQueue*q=(MyQueue*)malloc(sizeof(MyQueue));

StackInit(q-pushST);

StackInit(q-popST);

returnq;

voidmyQueuePush(MyQueue*obj,intx)

//不管棧內(nèi)有沒(méi)有數(shù)據(jù)，只要是入隊(duì)操作就向Push棧入數(shù)據(jù)即可

StackPush(obj-pushST,x);

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

intmyQueuePeek(MyQueue*obj)

//如果pop棧為空,先把push棧數(shù)據(jù)導(dǎo)入pop棧

if(StackEmpty(obj-popST))

while(!StackEmpty(obj-pushST))

StackPush(obj-popST,StackTop(obj-pushST));

StackPop(obj-pushST);

returnStackTop(obj-popST);

intmyQueuePop(MyQueue*obj)

//如果pop棧為空,先把push棧數(shù)據(jù)導(dǎo)入pop棧

/*if(StackEmpty(obj-popST))

while(!StackEmpty(obj-pushST))

StackPush(obj-popST,StackTop(obj-pushST));

StackPop(obj-pushST);

//復(fù)用

inttop=myQueuePeek(obj);//易錯(cuò)點(diǎn):不能寫(xiě)obj-popST,因?yàn)樵搨魅腙?duì)列的指針

StackPop(obj-popST);

returntop;

boolmyQueueEmpty(MyQueue*obj)

//push棧和pop棧同時(shí)為空,隊(duì)列才為空

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

voidmyQueueFree(MyQueue*obj)

StackDestroy(obj-pushST);

StackDestroy(obj-popST);

free(obj);

}

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

題目描述：

設(shè)計(jì)你的循環(huán)隊(duì)列實(shí)現(xiàn)。循環(huán)隊(duì)列是一種線性數(shù)據(jù)結(jié)構(gòu)，其操作表現(xiàn)基于FIFO（先進(jìn)先出）原則并且隊(duì)尾被連接在隊(duì)首之后以形成一個(gè)循環(huán)。它也被稱(chēng)為環(huán)形緩沖器。

循環(huán)隊(duì)列的一個(gè)好處是我們可以利用這個(gè)隊(duì)列之前用過(guò)的空間。在一個(gè)普通隊(duì)列里，一旦一個(gè)隊(duì)列滿了，我們就不能插入下一個(gè)元素，即使在隊(duì)列前面仍有空間。但是使用循環(huán)隊(duì)列，我們能使用這些空間去存儲(chǔ)新的值。

你的實(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ì)列是否已滿。

//循環(huán)隊(duì)列是邏輯上的循環(huán)(數(shù)組、鏈表都可以實(shí)現(xiàn),本題使用數(shù)組)

//永遠(yuǎn)空出一個(gè)位置不存儲(chǔ)數(shù)據(jù)(目的是區(qū)分空和滿)

//當(dāng)front=tail說(shuō)明循環(huán)隊(duì)列空

//當(dāng)tail+1=front說(shuō)明循環(huán)隊(duì)列滿

typedefstruct

int*a;//數(shù)組

intk;//循環(huán)隊(duì)列最多能存多少個(gè)數(shù)據(jù)

intfront;//頭指針

inttail;//尾指針(隊(duì)尾數(shù)據(jù)的下一個(gè)位置)

}MyCircularQueue;

MyCircularQueue*myCircularQueueCreate(intk)

MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));

obj-a=(int*)malloc(sizeof(int)*(k+1));//需要多開(kāi)一個(gè)空間

obj-front=0;

obj-tail=0;

obj-k=k;

returnobj;

boolmyCircularQueueIsEmpty(MyCircularQueue*obj)

returnobj-front==obj-tail;

boolmyCircularQueueIsFull(MyCircularQueue*obj)

inttailNext=obj-tail+1;

if(tailNext==obj-k+1)

//如果tail已經(jīng)走到尾(不存放數(shù)據(jù)的位置),此時(shí)認(rèn)為tailNext回到了數(shù)組首元素位置

tailNext=0;

returntailNe