#define MaxSize 100				//定義棧中元素的最大個數(shù)
typedef struct
{
	SElemtype *base;			//棧底指針
	SElemtype *top;				//棧頂指針 
	int stacksize				//棧可用的最大容量 
}SqStack;

順序棧的初始化

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

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

實現(xiàn)原理

為順序棧動態(tài)分配一個最大容量為MAXSIZE的數(shù)組
棧頂指針top初始為base，表示棧為空
stacksize置為棧的最大容量MaxSize

?? 代碼演示

Status InitStack(SqStack &S)
{//構(gòu)造一個空棧S
	S. base=new SElemType[MaxSize];		//為順序棧動態(tài)分配一個最大容量為MAxsini
	if(!S. base) exit(OVERFLOW);		//存儲分配失敗
	S. top=S. base;						//top初始為base，空棧
	S. stacksize=MaxSize;				//stacksize置為棧的最大容量MaxSize
	return OK;
}

順序棧的入棧

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

A：入棧操作是將新元素進入棧

??實現(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：出棧操作是將棧頂元素刪除

??實現(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：當棧非空時，此操作返回當前棧頂元素的值，棧頂指針保持不變。

??實現(xiàn)原理

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

?? 代碼演示

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

鏈棧

采用鏈式存儲的棧稱為鏈棧。鏈棧的優(yōu)點是便于多個棧共享存儲空間和提高其效率，且不存在棧滿上溢的情況。通常采用單鏈表實現(xiàn)。

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

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

采用鏈式存儲，便于結(jié)點的插入與刪除。鏈棧的操作與鏈表類似，入棧和出棧的操作都在鏈表的表頭進行。

隊列

隊列的定義

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

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

隊列有兩種存儲表示，分別為順序表示與鏈式表示

隊列的順序表達與實現(xiàn)

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

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

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

#define   MAXSIZE    100		//隊列容量
typedef   struct 
{   
	ElemType *base;             //存儲空間
	int front,rear;            	//隊首，隊尾
}SqQueue ;

假溢出

?

圖（1）所示為隊列的初始狀況。此時有【front == rear == 0】成立。該條件可以作為隊列判空的條件。

但是【rear == MAXSIZE】不能作為隊列滿的條件。為什么呢？

圖（4）隊列中只有一個元素，仍滿足該條件。這時入隊出現(xiàn)上溢出。但是這種溢出并不是真正的溢出，在隊列中依然存在可以存放元素的空位置，所以是一種假溢出。

如何解決循環(huán)鏈表的這一缺點呢？ ?

循環(huán)隊列

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

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

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

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

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

??實現(xiàn)原理

為隊列動態(tài)分配一個最大容量為MAXSIZE的數(shù)組空間
base指向數(shù)組空間的首地址
頭指針與尾指針置為零，表示隊列為空

?? 代碼演示

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

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

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

A：入隊操作是指在隊尾插入一個新的元素

??實現(xiàn)原理

判斷隊列是否滿
滿了返回ERROR
將新元素插入隊尾
隊尾指針加一

?? 代碼演示

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)隊列的出隊

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

A：出隊操作是刪除隊頭元素

??實現(xiàn)原理

判斷隊列是否為空
為空返回ERROR
保留隊頭元素
隊頭指針加一

?? 代碼演示

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：什么是鏈隊列？

A：隊列的鏈式表示稱為鏈隊列。它實際上是一個同時帶有隊頭指針和隊尾指針的單鏈表，頭指針指向?qū)︻^結(jié)點，尾指針指向隊尾結(jié)點。

隊列的鏈式存儲如圖：

隊列的鏈式存儲類型可描述為：

typedef struct Qnode
{       
	ElemType data;
    struct QNode * next;
}Qnode,*QueuePtr;                  //結(jié)點
typedef struct 
{ 
	QueuePtr  front;
	QueuePtr rear;
}LinkQueue;                       //鏈隊

鏈棧的初始化

Q：什么是鏈隊列的初始化？

A：鏈棧的初始化操作就是構(gòu)建一個只有頭結(jié)點的空隊。

??實現(xiàn)原理

生成新結(jié)點作為頭結(jié)點
隊頭指針和隊尾指針指向該結(jié)點
頭指針的指針域置空

?? 代碼演示

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

鏈棧的入隊

??實現(xiàn)原理

為入隊元素分配結(jié)點空間，用指針p指向
將新結(jié)點數(shù)據(jù)域置為e
將新結(jié)點插入到隊尾
修改隊尾指針為p

?? 代碼演示

Status EnQueue(LinkQueue &Q,ElemType e)
{
	p=new QNode;		//為入隊元素分配結(jié)點空間，用指針p指向
	p->data=e;	        //將新結(jié)點數(shù)據(jù)域置為e
	p->next=NULL;		
	Q.rear->next=p;     //將新結(jié)點插入到隊尾
	Q.rear=p;			//修改隊尾指針為p
	return OK;
}

鏈棧的出隊

??實現(xiàn)原理

判斷是否為空，為空返回ERROR
保留頭元素空間，以備釋放
修改頭指針的指針域，指向下一結(jié)點
判斷出隊元素是否是最后一個元素，若是，將隊尾指針重新賦值，指向頭結(jié)點
釋放原隊頭元素的空間

?? 代碼演示

Status DeQueue(LinkQueue &Q,ElemType &e)
{
	if(Q.front==Q.rear)			//若隊列為空，返回ERROR
		return ERROR;
	QNode *p=Q.front->next;		//保留頭元素空間，以備釋放
	Q.front->next=p->next;		//修改頭指針的指針域，指向下一結(jié)點
    if(Q.rear==p)				//判斷出隊元素是否是最后一個元素，若是，將隊尾指針重新賦值，指向頭結(jié)點
		Q.rear=Q.front; 
	delete p;					//釋放原隊頭元素的空間
	return OK;
}

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

您可能感興趣的文章: