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