数据结构（四）顺序栈 链式栈

一、概念

栈是一种先进后出的数据结构。FILO(firt in late out)
逻辑结构：线性结构

二、存储结构：

（一） 顺序存储

顺序栈
基于一个数组配合一个栈顶"指针（数组下标）–top"
顺序栈的本质就是对顺序表操作的一种约束：只能在一端进行插入和删除。

操作：
创建
清空
销毁
入栈、压栈——判断栈满
出栈、弹栈——判断栈空
打印栈所有元素

（二）链式存储

1. 结构体定义

//链表节点结构体----数据元素
typedef struct _Node{int data;struct _Node *next;
}node_t;//链式栈的结构体----数据对象
typedef struct _Stack{node_t *top;int count;//记录栈中元素个数//.....其他属性信息
}stack_t;

2.创建栈表

（1）函数定义

int create_stack(stack_t **my_stack);

1. 在内存中申请一块stack_t类型大小的空间存储栈的内容；
2. 初始化栈的成员的数据：将count置0，top置NULL

（2）注意点

1. 进入函数就需要判断传入的参数是否为NULL，为空退出函数
2. 在申请完内存空间后判断，申请空间是否成功，失败退出函数

（3）代码实现

int create_stack(stack_t **my_stack){if(NULL==my_stack) //判断传入参数是否为空{return -1;}*my_stack=(stack_t *)malloc(sizeof(stack_t));if(NULL==*my_stack){return -1;}//初始化(*my_stack)->top=NULL;(*my_stack)->count=0;return 0;
}

3. 入栈

（1）函数定义

int push_stack(stack_t *my_stack, int data);

1. 在内存中申请一块node_t类型大小的数据空间
2. 进行头插
3. count自加一

（2）注意点

1. 需要检查传入参数是否为空，为空退出函数
2. top指向的元素即是第一个数据节点

（3）代码实现

int push_stack(stack_t *my_stack, int data){if(NULL==my_stack){return -1;}//申请一个新数据节点node_t *node=(node_t *)malloc(sizeof(node_t));if(NULL==node){return -1;}node->next=my_stack->top;my_stack->top=node;node->data=data;my_stack->count++;return 0;
}

3. 出栈

（1）函数定义

int pop_stack(stack_t *my_stack, int *num);

1. 头删
2. count自减

（2）注意点

1. 需要检查传入指针参数和*num是否为空，为空退出函数
2. 检查栈是否为空，为空退出函数

（3）代码实现

//出栈
int pop_stack(stack_t *my_stack, int *num){if(NULL==my_stack||NULL==num){return -1;}if(is_empty(my_stack)){return -1;}//头删node_t *pdel=my_stack->top;*num=pdel->data;my_stack->top=pdel->next;free(pdel);pdel=NULL;my_stack->count--;return 0;
}

4. 判断栈是否为空

（1）函数定义

int is_empty(stack_t *my_stack);

（2）注意点

1. 判断传入的指针参数是否为空

（3）代码实现

int is_empty(stack_t *my_stack){if(NULL==my_stack){return -1;}return (my_stack->count)?0:1; 
}

5. 清空栈

（1）函数定义

int clean_stack(stack_t *my_stack);

1. 循环头删
2. count置0
3. 只要top的指向不为空，就一直循环

（2）注意点

1. 入参合理性检查
2. count不要忘记置0

（3）代码实现

int clean_stack(stack_t *my_stack){if(NULL==my_stack){return -1;}node_t *pdel=NULL;while(my_stack->top){pdel=my_stack->top;my_stack->top=pdel->next;free(pdel);}pdel=NULL;my_stack->count=0;return 0;
}

6. 销毁栈

（1）函数定义

int destroy_stack(stack_t **my_stack);

（2）注意点

（3）代码实现

int destroy_stack(stack_t **my_stack){if(NULL==my_stack||NULL==*my_stack){return -1;}//先清空再销毁if(clean_stack(*my_stack)){return -1;}free(*my_stack);*my_stack=NULL;return 0;
}

7. 打印栈

（1）函数定义

int print_stack(stack_t *my_stack);

（2）注意点

1. 入参合理性检查

（3）代码实现

int print_stack(stack_t *my_stack){if(NULL==my_stack){return -1;}if(is_empty(my_stack)){printf("栈空\n");return -1;}node_t *ptemp=my_stack->top;for(int i=0;i<my_stack->count;i++){printf("%d ",ptemp->data);ptemp=ptemp->next;}putchar(10);return 0;
}