C語言示例代碼講解棧與隊列

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

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

Status Push(SqStack	&S,SElemType e)
{//插入元素e為新的棧頂元素
	if(S.top-S.base==S:stacksize) return ERROR;//棧滿 
	*S. top++=e;							   //元素e壓入棧頂，棧頂指針加1
	return OK;
}

Status Pop(SqStack &S,SElemType &e)
(//刪除S的棧頂元素，用e返回其值
	if(S.top==S.base) return ERROR;//棧頂
	指針減1，將棧頂元素賦給e	   //棧頂指針減1，將棧頂元素賦給e 
	e=*--S.top;
	return OK;
)

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

typedef struct Linknode
{
	ElemType data;				//數據域
	struct Linknode *next;		//指針域
} *LiStack; 

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

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

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;
}

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;
}

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

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

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

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