您好,登錄后才能下訂單哦!
今天小編給大家分享一下C語言棧與隊(duì)列如何定義的相關(guān)知識(shí)點(diǎn),內(nèi)容詳細(xì),邏輯清晰,相信大部分人都還太了解這方面的知識(shí),所以分享這篇文章給大家參考一下,希望大家閱讀完這篇文章后有所收獲,下面我們一起來了解一下吧。
棧是一種線性表,但限定這種線性表只能在某一端進(jìn)行插入和刪除操作
假設(shè)棧 【s = (a1,a2,……,an) 】,a1為棧底元素,an為棧頂元素。由于棧只能在棧頂進(jìn)行插入和刪除操作,所以進(jìn)棧次序依次為【a1,a2,……,an】,出棧次序?yàn)椤綼n,……,a2,a1】
由此可見:棧的操作特性可以明顯地概括為后進(jìn)先出
棧類似于線性表,它也有兩種對應(yīng)的存儲(chǔ)方式分別為順序棧和鏈棧。
Q:什么是順序棧?
A:采用順序存儲(chǔ)的棧成為順序棧。它利用一組地址連續(xù)的存儲(chǔ)單位存放自棧底到棧頂?shù)臄?shù)據(jù)元素,同時(shí)附設(shè)一個(gè)指針(top)來指示當(dāng)前棧頂?shù)奈恢谩?/p>
棧的順序存儲(chǔ)類型可描述為
#define MaxSize 100 //定義棧中元素的最大個(gè)數(shù) typedef struct { SElemtype *base; //棧底指針 SElemtype *top; //棧頂指針 int stacksize //??捎玫淖畲笕萘?nbsp; }SqStack;
Q:什么是順序棧的初始化?
A:順序棧的初始化操作就是為順序棧動(dòng)態(tài)分配一個(gè)最大容量為 MaxSize 的數(shù)組空間。
實(shí)現(xiàn)原理
為順序棧動(dòng)態(tài)分配一個(gè)最大容量為MAXSIZE的數(shù)組
棧頂指針top初始為base,表示棧為空
stacksize置為棧的最大容量MaxSize
代碼演示
Status InitStack(SqStack &S) {//構(gòu)造一個(gè)空棧S S. base=new SElemType[MaxSize]; //為順序棧動(dòng)態(tài)分配一個(gè)最大容量為MAxsini if(!S. base) exit(OVERFLOW); //存儲(chǔ)分配失敗 S. top=S. base; //top初始為base,空棧 S. stacksize=MaxSize; //stacksize置為棧的最大容量MaxSize return OK; }
Q:什么是順序棧的入棧?
A:入棧操作是將新元素進(jìn)入棧
實(shí)現(xiàn)原理
判斷棧是否滿了,若滿了返回ERROR
將新元素壓入棧,棧頂指針加1
代碼演示
Status Push(SqStack &S,SElemType e) {//插入元素e為新的棧頂元素 if(S.top-S.base==S:stacksize) return ERROR;//棧滿 *S. top++=e; //元素e壓入棧頂,棧頂指針加1 return OK; }
Q:什么是順序棧的出棧?
A:出棧操作是將棧頂元素刪除
實(shí)現(xiàn)原理
判斷棧是否空,若空則返回ERROR
棧頂指針減1,棧頂元素出棧
代碼演示
Status Pop(SqStack &S,SElemType &e) (//刪除S的棧頂元素,用e返回其值 if(S.top==S.base) return ERROR;//棧頂 指針減1,將棧頂元素賦給e //棧頂指針減1,將棧頂元素賦給e e=*--S.top; return OK; )
Q:如何取順序棧的棧頂元素?
A:當(dāng)棧非空時(shí),此操作返回當(dāng)前棧頂元素的值,棧頂指針保持不變。
實(shí)現(xiàn)原理
判斷棧是否空
返回棧頂元素的值,棧頂指針不變
代碼演示
SElemType GetTop (SqStack S) {//返回s的棧頂元素,不修改棧頂指針 if(S.top!=S.base) //棧非空 return*(S.top-1); //返回棧頂元素的值,棧頂指針不變 )
采用鏈?zhǔn)酱鎯?chǔ)的棧稱為鏈棧。鏈棧的優(yōu)點(diǎn)是便于多個(gè)棧共享存儲(chǔ)空間和提高其效率,且不存在棧滿上溢的情況。通常采用單鏈表實(shí)現(xiàn)。
棧的順序存儲(chǔ)類型可描述為
typedef struct Linknode { ElemType data; //數(shù)據(jù)域 struct Linknode *next; //指針域 } *LiStack;
采用鏈?zhǔn)酱鎯?chǔ),便于結(jié)點(diǎn)的插入與刪除。鏈棧的操作與鏈表類似,入棧和出棧的操作都在鏈表的表頭進(jìn)行。
隊(duì)列是一種線性表,但限定這種線性表只能在表的一端進(jìn)行插入,在另一端進(jìn)行刪除。允許刪除的一端為隊(duì)頭,又稱為隊(duì)首,允許插入的一端為隊(duì)尾
隊(duì)列與生活中的排隊(duì)一樣,最早排隊(duì)的最先離開,隊(duì)列的操作特性可以明顯地概括為先進(jìn)先出
隊(duì)列有兩種存儲(chǔ)表示,分別為順序表示與鏈?zhǔn)奖硎?/p>
和順序棧相類似,在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中,除了用一組地址連續(xù)的存儲(chǔ)單元依次列頭到隊(duì)列尾的元素之外。還需附設(shè)兩個(gè)整型變量【front】和【rear】分別指示隊(duì)列頭元素及隊(duì)間的位置(后面分別稱為頭指針和尾指針)。
隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)表示如下:
#define MAXSIZE 100 //隊(duì)列容量 typedef struct { ElemType *base; //存儲(chǔ)空間 int front,rear; //隊(duì)首,隊(duì)尾 }SqQueue ;
圖(1)所示為隊(duì)列的初始狀況。此時(shí)有【front == rear == 0】 成立。該條件可以作為隊(duì)列判空的條件。
但是【rear == MAXSIZE】不能作為隊(duì)列滿的條件。為什么呢?
圖(4)隊(duì)列中只有一個(gè)元素,仍滿足該條件。這時(shí)入隊(duì)出現(xiàn)上溢出。但是這種溢出并不是真正的溢出,在隊(duì)列中依然存在可以存放元素的空位置,所以是一種假溢出。
如何解決循環(huán)鏈表的這一缺點(diǎn)呢?
Q:什么是循環(huán)隊(duì)列?
A:將順序隊(duì)列臆造成一個(gè)環(huán)狀的空間,即把存儲(chǔ)隊(duì)列元素的表從邏輯上視為一個(gè)環(huán),稱為循環(huán)隊(duì)列。
Q:什么是循環(huán)隊(duì)列的初始化?
A:循環(huán)隊(duì)列的初始化就是動(dòng)態(tài)分配一個(gè)預(yù)定義大小為 MAXSIZE 的數(shù)組空間
????實(shí)現(xiàn)原理
為隊(duì)列動(dòng)態(tài)分配一個(gè)最大容量為MAXSIZE的數(shù)組空間
base指向數(shù)組空間的首地址
頭指針與尾指針置為零,表示隊(duì)列為空
???? 代碼演示
Status InitQueue ( SqQueue &Q ) { Q.base=new ElemType[MAXSIZE]; if(!Q.base) return OVERFLOW; Q.front=Q.rear=0; return OK; }
Q:什么是循環(huán)隊(duì)列的入隊(duì)?
A:入隊(duì)操作是指在隊(duì)尾插入一個(gè)新的元素
????實(shí)現(xiàn)原理
判斷隊(duì)列是否滿
滿了返回ERROR
將新元素插入隊(duì)尾
隊(duì)尾指針加一
???? 代碼演示
Status EnQueue(SqQueue &Q,ElemType e) { if((Q.rear+1)%MAXSIZE==Q.front) //判滿 return ERROR; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXSIZE; return OK; }
Q:什么是循環(huán)隊(duì)列的出隊(duì)?
A:出隊(duì)操作是刪除隊(duì)頭元素
????實(shí)現(xiàn)原理
判斷隊(duì)列是否為空
為空返回ERROR
保留隊(duì)頭元素
隊(duì)頭指針加一
???? 代碼演示
Status DeQueue(SqQueue &Q, ElemType &e) { if( Q.rear==Q.front ) return ERROR; //判空 e = Q.base[Q.front]; Q.front = (Q.front+1)%MAXSIZE; return OK; }
Q:什么是鏈隊(duì)列?
A:隊(duì)列的鏈?zhǔn)奖硎痉Q為鏈隊(duì)列。它實(shí)際上是一個(gè)同時(shí)帶有隊(duì)頭指針和隊(duì)尾指針的單鏈表,頭指針指向?qū)︻^結(jié)點(diǎn),尾指針指向隊(duì)尾結(jié)點(diǎn)。
隊(duì)列的鏈?zhǔn)酱鎯?chǔ)如圖:
隊(duì)列的鏈?zhǔn)酱鎯?chǔ)類型可描述為:
typedef struct Qnode { ElemType data; struct QNode * next; }Qnode,*QueuePtr; //結(jié)點(diǎn) typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue; //鏈隊(duì)
Q:什么是鏈隊(duì)列的初始化?
A:鏈棧的初始化操作就是構(gòu)建一個(gè)只有頭結(jié)點(diǎn)的空隊(duì)。
實(shí)現(xiàn)原理
生成新結(jié)點(diǎn)作為頭結(jié)點(diǎn)
隊(duì)頭指針和隊(duì)尾指針指向該結(jié)點(diǎn)
頭指針的指針域置空
代碼演示
Status InitQueue(LinkQueue &Q) { Q.front=Q.rear=new QNode; p->next=NULL; return OK; }
實(shí)現(xiàn)原理
為入隊(duì)元素分配結(jié)點(diǎn)空間,用指針p指向
將新結(jié)點(diǎn)數(shù)據(jù)域置為e
將新結(jié)點(diǎn)插入到隊(duì)尾
修改隊(duì)尾指針為p
???? 代碼演示
Status EnQueue(LinkQueue &Q,ElemType e) { p=new QNode; //為入隊(duì)元素分配結(jié)點(diǎn)空間,用指針p指向 p->data=e; //將新結(jié)點(diǎn)數(shù)據(jù)域置為e p->next=NULL; Q.rear->next=p; //將新結(jié)點(diǎn)插入到隊(duì)尾 Q.rear=p; //修改隊(duì)尾指針為p return OK; }
實(shí)現(xiàn)原理
判斷是否為空,為空返回ERROR
保留頭元素空間,以備釋放
修改頭指針的指針域,指向下一結(jié)點(diǎn)
判斷出隊(duì)元素是否是最后一個(gè)元素,若是,將隊(duì)尾指針重新賦值,指向頭結(jié)點(diǎn)
釋放原隊(duì)頭元素的空間
代碼演示
Status DeQueue(LinkQueue &Q,ElemType &e) { if(Q.front==Q.rear) //若隊(duì)列為空,返回ERROR return ERROR; QNode *p=Q.front->next; //保留頭元素空間,以備釋放 Q.front->next=p->next; //修改頭指針的指針域,指向下一結(jié)點(diǎn) if(Q.rear==p) //判斷出隊(duì)元素是否是最后一個(gè)元素,若是,將隊(duì)尾指針重新賦值,指向頭結(jié)點(diǎn) Q.rear=Q.front; delete p; //釋放原隊(duì)頭元素的空間 return OK; }
以上就是“C語言棧與隊(duì)列如何定義”這篇文章的所有內(nèi)容,感謝各位的閱讀!相信大家閱讀完這篇文章都有很大的收獲,小編每天都會(huì)為大家更新不同的知識(shí),如果還想學(xué)習(xí)更多的知識(shí),請關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。