【数据结构】实现栈的各种算法

关于栈

栈是一种常用的数据结构，使用栈可以对我们的编程带来很大的帮助，但前提是我们要了解栈的本质是什么。首先，我们要知道栈的特点是先进后出（或者说是后进先出），举个列子，就像餐厅里叠得很高的碗，当我们往碗层里放碗时，我们是放到碗层的最上方，而当我们拿碗时，我们也是从碗层的最上方拿碗。我们可以把栈设想成这个碗层，而这个过程在我们栈的数据结构里，放碗就对应于进栈的过程，而拿碗就相当于出栈的过程。

栈根据不同的存储方式可以分为两类。一类是顺序存储结构的顺序栈，另一类是链式存储结构的链栈。

一、顺序栈

1.定义

typedef struct{
	ElemType *elem;  //栈的存储数组，elem为数组名，*elem即栈的栈底元素
	int top;         //记录站顶元素的下一个位置，简称<strong>栈顶位标</strong>
	int size;        //当前分配的存储容量
	int increment;   //扩容时，增加的存储容量
}SqStack;

2.常用的接口

Status InitStack_Sq(SqStack &S,int size,int inc); //初始化顺序栈

Status DestroyStack_Sq(SqStack &S); //销毁顺序栈S

Status StackEmpty_Sq(SqStack S); //判断栈是否为空，若空返回TRUE，否则FALSE

void ClearStack_Sq(SqStack &S); //清空栈S

Status Push_Sq(SqStack &S,ElemType e); //元素e压入栈S

Status Pop_Sq(SqStack &S,ElemType e); //栈S的栈顶元素出栈，并用e返回

Status GetTop_Sq(SqStack S,ElemType &e); //取栈S的栈顶元素，并用e返回

3.接口的实现

/*初始化一个栈*/
Status InitStack_Sq(SqStack &S,int inc){
    S.elem = (ElemType*)malloc(size*sizeof(ElemType));
    if(NULL==S.elem) return OVERFLOW;
    S.top = 0;
    S.size = size;
    S.increment = inc;
    return OK;
}

/*进栈操作*/
Status Push_Sq(SqStack &S,ElemType e){
    ElemType *newbase;  //栈的空间不足时，使用newbase指向一个空间更大的数组
    if(S.top>=S.size){  //当栈满时
        newbase = (ElemType *)realloc(S.elem,(S.size+S.increment)*sizeof(ElemType));
        if(NULL==newbase) return OVERFLOW;
        S.elem = newbase;
        S.size = S.size + S.increment;
    }
    S.elem[S.top++] = e;
    return OK;
}

/*出栈操作*/
Status Pop_Sq(SqStack &S,ElemType e){
	if(S.top==0){
		return ERROR;
	}
	e = S.elem[--S.top];
	return OK;
}

/*栈的销毁*/
Status DestroyStack_Sq(SqStack &S){
	if(S.top!=0){               
               free(S.elem);
		//释放掉内存只是把申请的内存返还给系统
                //还需要把指针设置为空
                S.top = 0;
		S.elem = NULL;
		return OK;
	}else return ERROR;
}

/*判断栈是否为空*/
Status StackEmpty_Sq(SqStack S){
 if(S.top==0&&S.elem==NULL){
  return TRUE;
 }else return FALSE;
}

/*栈的清空*/
void ClearStack_Sq(SqStack &S){
	//只要S.top设置为0即可
	S.top = 0; 
}

/*取栈顶元素*/
Status GetTop_Sq(SqStack S,ElemType &e){
	if(S.top==0)	return ERROR;
	else{
		e = S.elem[S.top-1];
	}
	return OK;
}

二、链栈

1.定义

typedef struct LSNode{
	ElemType data;         //数据域 
	struct LSNode *next;   //指针域 
}LSNode,*LStack;          //结点和链栈类型

Status InitStack_LS(LStack &S); //初始化链栈S

Status DestroyStack_LS(LStack &S); //销毁链栈S

Status StackEmpty_LS(LStack S); //判断空栈，若栈S空则返回TRUE，否则FALSE

Status Push_LS(LStack &S,ElemType e); //元素e的压入栈S

Status Pop_LS(LStack &S,ElemType e); //栈S的栈顶元素出栈，并用e返回

Status GetTop_LS(LStack S,ElemType &e); //取栈S的栈顶元素，并用e返回

3.接口的实现

/*初始化一个链栈*/
Status InitStack_LS(LStack &S){
	S = NULL; 
} 

/*进栈操作*/
Status Push_LS(LStack &S,ElemType e){
	LSNode *t;
	t = (LSNode*)malloc(sizeof(LSNode));
	if(NULL==t) return OVERFLOW;
	t->data = e;
	t->next = S;
	S = t;
	return OK;
}

/*出栈操作*/
Status Pop_LS(LStack &S,ElemType e){
	LSNode *t;
	if(S==NULL) return ERROR;
	t = S;
	e = t->data;
	S = S->next;
	free(t);
	return OK;	
	
}

/*获得栈顶元素*/
Status GetTop_LS(LStack S,ElemType &e){
	if(NULL==S) return ERROR;
	else{
		e = S->data;
		return OK;
	}	
}

/*销毁一个栈*/
Status DestroyStack_LS(LStack &S){
	LSNode *p,*q;
	p = S;
	q = S;
	while(p!=NULL){
		q = q->next;
		free(p);
		p = q;
	}
	S = NULL;
	return OK;
}

/*判断栈是否为空*/
Status StackEmpty_LS(LStack S){
	if(NULL==S) return TRUE;
	else return FALSE;
}

以上接口的实现均是本人参考书本和网上资料，自己敲打出来的，错误肯定会有，所以希望有错误的地方大神们可以指出来，我会纠正的，至于其他一些接口，我会在需要或者想到的时候再补充，也欢迎大家帮我完善补充，对大家以后的学习都有帮助。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!