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