【数据结构】【栈】算法汇总

一、顺序栈的操作

1.准备工作

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct{SElemType*base;SElemType*top;int stacksize;
}SqStack;

2.栈的初始化

Status InitStack(SqStack &S){S.base=(SElemType*)malloc(MAXSIZE*sizeof(SElemType));if(!S.base) exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;
}

3.判断栈是否为空

status StackEmpty(Sqstack S){if(S.top=S.base)return TRUE;elsereturn FALSE;
}

4.求栈的长度

int StackLength(SqStack S){return S.top-S.base;
}

5.清空栈

Status ClearStack(SqStack S){if(S.base) S.top=S.base;return OK
}

6.销毁顺序栈

Status DestroyStack(SqStack &S){if(S.base){delete S.base;S.stacksize=0;S.base=S.top=NULL;}return OK;
}

7.顺序栈入栈

Status Push(SqStack &S,SElemType e){if(S.top-S.base>=S.stacksize){newbase=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!newbase) exit(overflow);S.base=newbase;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;return ok;
}

8.顺序栈的出栈

Status Pop(SqStack &S,SElemType &e){if(S.top==S.base)return ERROR;e=*--S.top;return OK;
}

9.取栈顶元素

Status GetTop(SqStack S,ElemType &e){if(S.base==S.top) return ERROR;E=*(S.top-1);return OK;
}

二、双向栈

1.准备工作

typedef struct{SElemType*base;int top1;int top2;
}sqdustack;

2.初始化

status initsqdustack(sqdustack &tws){tws.base=(Selemtype*)malloc(maxsize*sizeof(Selemtype));if(!tws.base) exit(OVERFLOW);tws.top1=0;tws.top2=maxsize-1;return ok;
}

3.入栈

Status push-sqdustack(sqdustack&tws,int i,selemtype x){if(tws.top1>tws.top2) return error;if(i==0) tws.base[tws.top1++]=x;else tws.base[tws.top2--]=x;return ok;
}

4.出栈

Status pop-sqdustack(sqdustack &tws,int i,selemtype &x){if(i==0){if(tws.top1==0) return error;x=tws.base[--tws.top1];}else{if(tes.top2==maxsize-1) return error;x=tws.base[++tws.top2];}return ok;
}

三、链栈

1.准备工作

typedef struct StackNode{ElemType data;struct SNode*next;
}SNode,*LinkStack;
LinkStack S;

2.初始化

void InitStack(LinkStack &S){S=NULL;return ok;
}

3.判断链栈是否为空

Status StackEmpty(LinkStack S){if(S==NULL) return true;else return false;
}

4.链栈的入栈

Status Push(LinkStack &S,SElemType e){p=(SElemType*)malloc(MAXSIZE*sizeof(SElemType));p->data=e;p->next=S;S=p;return OK;
}

5.链栈的出栈

Status Pop(LinkStack &S,SElemType e){if(S==NULL) return error;e=S->data;p=S;S=S->next;free(p);return ok;
}

6.取栈顶元素

SElemType GetTop(LinkStack S){if(S!=NULL)return S->data;
}