栈|数据结构|C语言|详细讲解|代码实现

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

//定义链表节点的数据类型
typedef?struct?Node{
????int?data;
????struct?Node*?pNext;
}NODE,*PNODE;

//定义栈数据类型
typedef?struct?Stack{
????PNODE?top;//指向栈顶元素
????PNODE?bottom;//指向栈底元素的下一个位置
}stack,*pstack;

void?init(pstack?s);//初始化，创建空栈
void?push(pstack?s,int?val);//入栈
void?traverse(pstack?s);//出栈
int?showTop(pstack?s);//显示栈顶元素
int?pop(pstack?s);//出栈
bool?isEmpty(pstack?s);

int?main(){
????stack?S;
????init(&S);
????push(&S,1);
????push(&S,-9);
????push(&S,88);
????traverse(&S);
????printf("栈顶元素为%d\n",showTop(&S));
????printf("出来一个栈顶元素：%d\n",pop(&S));
????printf("出来一个栈顶元素：%d\n",pop(&S));
????printf("出来一个栈顶元素：%d\n",pop(&S));
????//printf("出来一个栈顶元素：%d\n",pop(&S));
????traverse(&S);
????
????
????return?0;
}


//初始化栈
//创建一个空栈，空战就是栈的top和bottom指针都指向一个空的不存储任何数据的节点
void?init(pstack?s){
????s->top=(PNODE)malloc(sizeof(NODE));
????if(!s->top){
????????printf("动态内存分配失败\n");
????????exit(-1);
????}else{
????????s->bottom=s->top;
????????s->top->pNext=NULL;//或s->bottom->pNext=NULL;
????}
}


void?push(pstack?s,int?val){
????PNODE?pnew=(PNODE)malloc(sizeof(NODE));
????pnew->data=val;
????pnew->pNext=s->top;/*这一步不能是pnew->pNext=s->bottom，因为这一步是入栈而不是插入第一个元素。
??????????????????????????bottom和top最开始都存着的空节点的地址，但只有top一直存着最顶端元素的地址*/
????s->top=pnew;
}


void?traverse(pstack?s){
????if(isEmpty(s)){
????????printf("栈已空，无法遍历");
????????exit(-1);
????}
????PNODE?p=s->top;
????while(p!=s->bottom){
????????printf("%d??",p->data);
????????p=p->pNext;
????}
????printf("\n");
}

int?showTop(pstack?s){
????return?s->top->data;
}

bool?isEmpty(pstack?s){
????if(s->top==s->bottom){
????????return?1;
????}
????return?0;
}

int?pop(pstack?s){
????if(isEmpty(s)){
????????printf("栈已空，无法出栈");
????????exit(-1);
????}
????int?val=s->top->data;
????PNODE?p=s->top;
????s->top=s->top->pNext;
????free(p);
????return?val;
}