3. 数据结构——栈的操作实现

1. 顺序栈

主要操作：初始化、栈判空、入栈、出栈、去栈顶元素

1.1 直接数组存储栈

//顺序栈的实现 
#include<stdio.h>
#define MaxSize 50
typedef int ElemType;
typedef struct{ElemType data[MaxSize];int top;  //指向栈顶指针，最开始-1 
}SqStack;//1.初始化
void InitStack(SqStack &S){S.top=-1;
}//2.判栈空
bool StackEmpty(SqStack S){return S.top==-1;
} //3.进栈
bool Push(SqStack &S,ElemType x){if(S.top==MaxSize-1)  //栈已满 return false;S.data[++S.top]=x; return true;
} //4. 出栈
bool Pop(SqStack &S,ElemType &x){if(S.top==-1)  //栈空不能取出元素 return false;x=S.data[S.top--];   return true; 
} //5.读栈顶元素
bool getTop(SqStack S,ElemType &x){if(S.top==-1)return false;x=S.data[S.top];return true;
} 

1.2 *top和*base指针指向栈顶和栈底位置

#include<stdio.h>
#include<stdlib.h>#define OK 1
#define OVERFLOW -2
#define ERROR 0
#define MAXSIZE 100typedef int ElemType;
typedef int Status;typedef struct{ElemType *base,*top;  //栈底指针、栈顶指针int stacksize;   //栈可用的最大容量 
}SqStack;//1.初始化
Status InitStack(SqStack &S){S.base=(ElemType*)malloc(sizeof(ElemType)*MAXSIZE);
//	S.base=new ElemType[MAXSIZE];if(!S.base)  //分配内存失败 return OVERFLOW;S.top=S.base;  //初始化的时候栈顶和栈底指针均指向第一个元素S.stacksize=MAXSIZE;return OK; 
} //2.入栈
Status Push(SqStack &S,ElemType e){if(S.top-S.base==S.stacksize)  //栈满 return ERROR;*S.top++=e;  //先赋值后自增return OK; 
}//3.出栈
Status Pop(SqStack &S,ElemType &e){if(S.base==S.top)  //栈空 return ERROR;e=*--S.top; return OK;
} //4. 取栈顶元素
Status GetTop(SqStack S,ElemType &e){if(S.base==S.top)  //栈空 return ERROR;e=*(S.top-1); return OK;
} 

2. 链栈(不带头节点，以链头做为栈顶)

主要操作：初始化、栈判空、入栈、出栈、去栈顶元素、销毁栈

//栈的链式存储结构(不带头节点,以链头为栈顶) 
#include<stdio.h>
#include<stdlib.h> 
typedef int ElemType;
typedef struct StackNode{ElemType data;struct StackNode *next;
}StackNode ,*LinkStack;//1.初始化
bool InitStack(LinkStack &S){S=NULL;return true;
}//2.判栈空
bool StackEmpty(LinkStack S){return S==NULL;
} //3.进栈
bool Push(LinkStack &S,ElemType x){LinkStack p=(StackNode*)malloc(sizeof(StackNode));p->data=x;p->next=S;S=p;return true;
} //4. 出栈
bool Pop(LinkStack &S,ElemType &x){if(S==NULL)return false;x=S->data;LinkStack p=S;S=S->next;free(p);  //释放空间 return true;
} //5.读栈顶元素
bool getTop(LinkStack S,ElemType &x){if(S==NULL)   //栈为空 return false;	x=S->data;return true; 
}//6.销毁队列
void DestroyStack(LinkStack &S){while(S!=NULL){LinkStack p=S;S=S->next;free(p); p=NULL;}
}