栈
1.栈的结构
2.栈的特点
1.先进后出；2.只能在栈顶压栈和出栈；3.top永远指向栈顶元素。
3.栈的顺序实现
（1）数据准备
#define OK1
#define ERROR0
#define TRUE1
#define FALSE0
#define MAXSIZE20/* 存储空间初始分配量 */
typedef int Status;
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */
//顺序栈结构
typedef struct{
SElemTypedata[MAXSIZE];
inttop;//用于栈顶指针
}SqStack;
（2）初始化
//初始化
Status InitStack(SqStack *s){
s->top= -1;
returnOK;
}
（3）将栈置空
Status ClearStack(SqStack *s){
s->top= -1;
returnOK;
}
（4）判断栈是否为空
Status StackEmpty(SqStack s){
if(s.top== -1) {
returntrue;
}else{
return false;
}
}
（5）返回栈的长度
Status StackLength(SqStack s){
returns.top+1;
}
（6）获取栈顶
Status GetTop(SqStack s,SElemType *e){
if(s.top==-1) {
returnERROR;
}else{
*e = s.data[s.top];
}
returnOK;
}
（7）压栈
Status PushData(SqStack *s,SElemType e){
if(s->top==MAXSIZE-1) {
//栈已满
returnERROR;
}else{
//栈顶+1
s->top++;
s->data[s->top] = e;
}
returnOK;
}
（8）出栈
Status PopData(SqStack *s,SElemType *e){
if(s->top== -1) {
returnERROR;
}else{
//栈顶-1
*e = s->data[s->top];
s->top--;
}
returnOK;
}
（9）栈遍历
Status StackTraverse(SqStack s){
inti=0;
printf("此栈中所有元素\n");
while(i<=s.top) {
printf("%d ",s.data[i]);
i++;
}
printf("\n");
returnOK;
}
（10）顺序栈的调试
intmain(intargc,constchar* argv[]) {
SqStacks;
SElemType e;
InitStack(&s);
for(inti=0; i<10; i++) {
PushData(&s, i);
}
StackTraverse(s);
GetTop(s, &e);
printf("栈顶元素:%d \n栈长度:%d\n",e,StackLength(s));
//
PopData(&s, &e);
printf("弹出栈顶元素:%d\n",e);
StackTraverse(s);
ClearStack(&s);
StackTraverse(s);
return0;
}
4.栈的链式实现
（1）数据准备
#define OK1
#define ERROR0
#define TRUE1
#define FALSE0
#define MAXSIZE20/* 存储空间初始分配量 */
typedef int Status;
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */
//单向链表
typedef struct StackNode{
SElemTypedata;
structStackNode*next;
}StackNode, *LinkStackPtr;
//
typedef struct{
LinkStackPtr top;//栈顶指针
intcount;//元素个数
}LinkStack;
（2）构造一个空栈
Status InitStack(LinkStack *s){
s->top=NULL;
s->count=0;
returnOK;
}
（3）栈遍历
void StackTraverse(LinkStack s){
LinkStackPtr p = s.top;
printf("栈中的元素为：");
while(p) {
printf("%d ",p->data);
p = p->next;
}
printf("\n");
}
（4）压栈:插入元素
Status Push(LinkStack *s,SElemType e){
//创建一个新结点
LinkStackPtr temp = (LinkStackPtr)malloc(sizeof(StackNode));
temp->data= e;
temp->next= s->top;
s->top= temp;
s->count++;
returnOK;
}
（5）出栈
Status Pop(LinkStack *s,SElemType *e){
if(s->count==0) {
returnERROR;
}
*e = s->top->data;
//
LinkStackPtr p = s->top;
s->top= p->next;
free(p);
s->count--;
returnOK;
}
（6）获取栈顶元素
Status GetTop(LinkStack s,SElemType *e){
if(s.top==NULL) {
returnERROR;
}else{
*e = s.top->data;
}
returnOK;
}
（7）清空栈
Status ClearStack(LinkStack *s){
LinkStackPtr p,q;
p = s->top;
while(p) {
q = p;
p = p->next;
free(q);
}
s->top= p;
s->count=0;
returnOK;
}
（8）斐波拉契数列
intFbi(inti){
if(i<2) {
returni==0?0:1;
}
returnFbi(i-1) +Fbi(i-2);
}
（9）链式栈的调试
intmain(intargc,constchar* argv[]) {
LinkStack s;
InitStack(&s);
inte;
for(inti=0; i<10; i++) {
Push(&s, i);
}
StackTraverse(s);
GetTop(s, &e);
printf("栈顶元素为:%d\n",e);
//
Pop(&s, &e);
printf("弹出的栈顶元素：%d\n",e);
StackTraverse(s);
//
ClearStack(&s);
StackTraverse(s);
//
printf("斐波拉契数列!\n");
for(inti=0; i<10; i++) {
printf("%d ",Fbi(i));
}
printf("\n");
return0;
}
