上文詳細(xì)的講解了順序表與鏈表的實(shí)現(xiàn)，相信大家在順序表與鏈表的指基礎(chǔ)上，很容易就能學(xué)會站和隊(duì)列，廢話不多說，我們馬上開始！

棧

棧的定義

棧是一種線性表，但限定這種線性表只能在某一端進(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)的存儲方式分別為順序棧和鏈棧。

順序棧

順序棧的定義

Q：什么是順序棧？

A：采用順序存儲的棧成為順序棧。它利用一組地址連續(xù)的存儲單位存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)附設(shè)一個(gè)指針（top）來指示當(dāng)前棧頂?shù)奈恢谩?/p>

棧的順序存儲類型可描述為

#define MaxSize 100				//定義棧中元素的最大個(gè)數(shù)
typedef struct
{
	SElemtype *base;			//棧底指針
	SElemtype *top;				//棧頂指針 
	int stacksize				//?？捎玫淖畲笕萘?
}SqStack; 

順序棧的初始化

Q：什么是順序棧的初始化？

A：順序棧的初始化操作就是為順序棧動(dòng)態(tài)分配一個(gè)最大容量為 MaxSize 的數(shù)組空間。

實(shí)現(xiàn)原理

1. 為順序棧動(dòng)態(tài)分配一個(gè)最大容量為MAXSIZE的數(shù)組
2. 棧頂指針top初始為base，表示棧為空
3. 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);		//存儲分配失敗
	S. top=S. base;						//top初始為base，空棧
	S. stacksize=MaxSize;				//stacksize置為棧的最大容量MaxSize
	return OK;
}

順序棧的入棧

Q：什么是順序棧的入棧？

A：入棧操作是將新元素進(jìn)入棧

??實(shí)現(xiàn)原理

1. 判斷棧是否滿了，若滿了返回ERROR
2. 將新元素壓入棧，棧頂指針加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)原理

1. 判斷棧是否空，若空則返回ERROR
2. 棧頂指針減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)原理

1. 判斷棧是否空
2. 返回棧頂元素的值，棧頂指針不變

?? 代碼演示

SElemType GetTop (SqStack S)
{//返回s的棧頂元素，不修改棧頂指針
	if(S.top!=S.base) 		        //棧非空
	    return*(S.top-1);			//返回棧頂元素的值，棧頂指針不變
)

鏈棧

采用鏈?zhǔn)酱鎯Φ臈７Q為鏈棧。鏈棧的優(yōu)點(diǎn)是便于多個(gè)棧共享存儲空間和提高其效率，且不存在棧滿上溢的情況。通常采用單鏈表實(shí)現(xiàn)。

棧的順序存儲類型可描述為

typedef struct Linknode
{
	ElemType data;				//數(shù)據(jù)域
	struct Linknode *next;		//指針域
} *LiStack; 

采用鏈?zhǔn)酱鎯?，便于結(jié)點(diǎn)的插入與刪除。鏈棧的操作與鏈表類似，入棧和出棧的操作都在鏈表的表頭進(jìn)行。

隊(duì)列

隊(duì)列的定義

隊(duì)列是一種線性表，但限定這種線性表只能在表的一端進(jìn)行插入，在另一端進(jìn)行刪除。允許刪除的一端為隊(duì)頭，又稱為隊(duì)首，允許插入的一端為隊(duì)尾

隊(duì)列與生活中的排隊(duì)一樣，最早排隊(duì)的最先離開，隊(duì)列的操作特性可以明顯地概括為先進(jìn)先出

隊(duì)列有兩種存儲表示，分別為順序表示與鏈?zhǔn)奖硎?/p>

隊(duì)列的順序表達(dá)與實(shí)現(xiàn)

隊(duì)列順序存儲結(jié)構(gòu)

和順序棧相類似，在隊(duì)列的順序存儲結(jié)構(gòu)中，除了用一組地址連續(xù)的存儲單元依次列頭到隊(duì)列尾的元素之外。還需附設(shè)兩個(gè)整型變量【front】和【rear】分別指示隊(duì)列頭元素及隊(duì)間的位置（后面分別稱為頭指針和尾指針）。

隊(duì)列的順序存儲結(jié)構(gòu)表示如下：

#define   MAXSIZE    100		//隊(duì)列容量
typedef   struct 
{   
	ElemType *base;             //存儲空間
	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)呢？ ?

循環(huán)隊(duì)列

Q：什么是循環(huán)隊(duì)列？

A：將順序隊(duì)列臆造成一個(gè)環(huán)狀的空間，即把存儲隊(duì)列元素的表從邏輯上視為一個(gè)環(huán)，稱為循環(huán)隊(duì)列。

循環(huán)隊(duì)列的初始化

Q：什么是循環(huán)隊(duì)列的初始化？

A：循環(huán)隊(duì)列的初始化就是動(dòng)態(tài)分配一個(gè)預(yù)定義大小為 MAXSIZE 的數(shù)組空間

??實(shí)現(xiàn)原理

1. 為隊(duì)列動(dòng)態(tài)分配一個(gè)最大容量為MAXSIZE的數(shù)組空間
2. base指向數(shù)組空間的首地址
3. 頭指針與尾指針置為零，表示隊(duì)列為空

?? 代碼演示

Status InitQueue ( SqQueue  &Q )
{
	Q.base=new  ElemType[MAXSIZE];
	if(!Q.base)	return OVERFLOW;
	Q.front=Q.rear=0;
	return OK;
} 

循環(huán)隊(duì)列的入隊(duì)

Q：什么是循環(huán)隊(duì)列的入隊(duì)？

A：入隊(duì)操作是指在隊(duì)尾插入一個(gè)新的元素

??實(shí)現(xiàn)原理

1. 判斷隊(duì)列是否滿
2. 滿了返回ERROR
3. 將新元素插入隊(duì)尾
4. 隊(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;
}

循環(huán)隊(duì)列的出隊(duì)

Q：什么是循環(huán)隊(duì)列的出隊(duì)？

A：出隊(duì)操作是刪除隊(duì)頭元素

??實(shí)現(xiàn)原理

1. 判斷隊(duì)列是否為空
2. 為空返回ERROR
3. 保留隊(duì)頭元素
4. 隊(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;
}

鏈隊(duì)列

Q：什么是鏈隊(duì)列？

A：隊(duì)列的鏈?zhǔn)奖硎痉Q為鏈隊(duì)列。它實(shí)際上是一個(gè)同時(shí)帶有隊(duì)頭指針和隊(duì)尾指針的單鏈表，頭指針指向?qū)︻^結(jié)點(diǎn)，尾指針指向隊(duì)尾結(jié)點(diǎn)。

隊(duì)列的鏈?zhǔn)酱鎯θ鐖D：

隊(duì)列的鏈?zhǔn)酱鎯︻愋涂擅枋鰹椋?/p>

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)原理

1. 生成新結(jié)點(diǎn)作為頭結(jié)點(diǎn)
2. 隊(duì)頭指針和隊(duì)尾指針指向該結(jié)點(diǎn)
3. 頭指針的指針域置空

?? 代碼演示

Status InitQueue(LinkQueue &Q)
{	
	Q.front=Q.rear=new QNode;
	p->next=NULL;
	return OK;
} 

鏈棧的入隊(duì)

??實(shí)現(xiàn)原理

1. 為入隊(duì)元素分配結(jié)點(diǎn)空間，用指針p指向
2. 將新結(jié)點(diǎn)數(shù)據(jù)域置為e
3. 將新結(jié)點(diǎn)插入到隊(duì)尾
4. 修改隊(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;
}

鏈棧的出隊(duì)

??實(shí)現(xiàn)原理

1. 判斷是否為空，為空返回ERROR
2. 保留頭元素空間，以備釋放
3. 修改頭指針的指針域，指向下一結(jié)點(diǎn)
4. 判斷出隊(duì)元素是否是最后一個(gè)元素，若是，將隊(duì)尾指針重新賦值，指向頭結(jié)點(diǎn)
5. 釋放原隊(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;
}

到此這篇關(guān)于C語言示例代碼講解棧與隊(duì)列的文章就介紹到這了,更多相關(guān)C語言棧與隊(duì)列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論