数据结构 - 栈
一.栈的定义
1.栈的分类
栈根据存储结构的不同被分为 顺序栈 和 链式栈
2.栈的结构
①.顺序栈
②.链式栈
top->next 即为指向栈顶的指针 
3.栈的结构体定义
①.顺序栈
②.链式栈
二.顺序栈的基本运算
0.顺序栈结构体定义
typedef int data_t;
typedef struct
{
data_t *data; //指向栈的指针
int maxlen; //表示栈的最大长度
int top; //栈顶元素的下标，用来指明栈顶的位置
}s1.创建一个空栈 - Stack_Create
/**
* @description: 创建一个空栈
* @param - len : 栈的最大长度
* @return : 指向栈的指针
*/
sqstack_t *Stack_create(int len)
{
sqstack_t *s;
/* 1.为栈申请空间 */
s = (sqstack_t *)malloc(sizeof(sqstack_t));
if(NULL == s)
{
printf("sqstatck create failed!\n");
return NULL;
}
/* 2.为栈内的数据域申请空间 */
s->data = (data_t *)malloc(len * sizeof(data_t));
if(NULL == s->data)
return NULL;
s->maxlen = len;
s->top = -1; //初始化 top = -1 ， 则代表栈为空栈
return s;
}2.清空栈 - Stack_Clear
/**
* @description: 清空一个栈
* @param - s : 要操作的栈的指针
* @return : 无
*/
void Stack_Clear(sqstack_t *s)
{
s->top = -1;
}3.判断是否为栈空 - Empty_Stack
/**
* @description: 判断栈是否为空
* @param - s : 要操作的栈
* @return : 返回 1 则为空 ， 否则为非空
*/
int Stack_Empty(sqstack_t *s)
{
return (s->top == -1 ? 1 : 0);
}4.判断是否满栈 - Full_Stack
/**
* @description: 判断栈是否为满
* @param - s : 要操作的栈的指针
* @return : 1 为满 ， 否则为空
*/
int Stack_Full(sqstack_t *s)
{
return (s->top == s->maxlen-1 ? 1 : 0);
}5.元素进栈 - Push_Stack
/**
* @description: 入栈
* @param - s : 要操作的栈的指针
* @param - value : 要压入的输入
* @return : 0 为成功 ， 其他为失败
*/
int Stack_Push(sqstack_t *s,data_t value)
{
/* 1.判断栈是否为满 */
if(Stack_Full(s))
{
printf("stack is already full!\n");
return -1;
}
/* 2.栈顶元素的下标先++ */
s->top++;
/* 3.填充数据 */
s->data[s->top] = value;
return 0;
}6.元素出栈 - Pop_Stack
/**
* @description: 出栈,并返回出栈的元素
* @param - s : 要操作的栈的指针
* @return : 出栈的元素
*/
int Stack_Pop(sqstack_t *s)
{
s->top--;
return s->data[s->top + 1];
}7.取栈顶元素 - Get_Top
/**
* @description: 取栈顶的元素
* @param - s : 要操作的栈的指针
* @return : 栈顶的的元素
*/
int Stack_Get_top(sqstack_t *s)
{
return (s->data[s->top]);
}8.释放栈的空间
/**
* @description: 释放栈的空间
* @param - s : 要操作的栈
* @return : 无
*/
void Stack_Free(sqstack_t *s)
{
/* 1.先释放数据域 */
free(s->data);
s->data = NULL;
/* 2.释放栈空间 */
free(s);
s = NULL;
}三.链式栈的基本操作
0.链式栈结构体定义
typedef int data_t;
typedef struct node
{
data_t data; //数据域名
struct node *next; //指针，指向栈下一个元素
}linkstack_t;1.创建一个空栈
/**
* @description: 创建一个空栈
* @param : 无
* @return : 创建的栈的首结点指针
*/
linkstack_t *Linkstack_Create(void)
{
linkstack_t *s;
/* 为栈申请空间 */
s = (linkstack_t *)malloc(sizeof(linkstack_t));
if(NULL == s)
{
printf("linkstack create error!\n");
return NULL;
}
s->next = NULL; //初始化头结点
return s;
}2.判断栈是否为空
/**
* @description: 判断是否为空栈
* @param - s : 要操作的栈的首结点指针
* @return : 1 为成功 ，其他为失败
*/
int Linkstack_Empty(linkstack_t *s)
{
if(NULL == s->next)
return 1;
else
return 0;
}3.清空栈
/**
* @description: 清空栈
* @param - s : 要操作的栈的首结点指针
* @return : 无
*/
void Linkstack_Clear(linkstack_t *s)
{
linkstack_t *p; //r 指向要释放的结点 ， p 指向
p = s->next;
/* 遍历所有结点，最后一个结点的 p->next 为 NULL */
while(p)
{
s->next = p->next;
free(p);
p = s->next;
}
}4.入栈
/**
* @description: 入栈（用单链表的头插实现）
* @param - s : 要操作的栈的首结点指针
* @param - value : 入栈元素的值
* @return : 0 为成功， -1 为失败
*
*/
int Linkstack_Push(linkstack_t *s,data_t value)
{
linkstack_t *p; //用来指向新创建的结点
/* 1.创建一个新的结点 */
p = (linkstack_t *)malloc(sizeof(linkstack_t));
if(NULL == p)
{
printf("malloc error!\n");
return -1;
}
/* 2.给新结点填充数据 */
p->data = value;
/* 3.利用单链表的头插，为栈压入结点 */
p->next = s->next;
s->next = p;
return 0;
}
5.出栈
/**
* @description: 出栈，并返回出栈的元素
* @param - s : 要操作的栈的首结点指针
* @return : 出栈的元素的值
*/
data_t Linkstack_Pop(linkstack_t *s)
{
linkstack_t *p; //指向要出栈的元素
data_t value;
p = s->next; //指向栈顶元素
value = p->data; //获取栈顶元素的值
/* a(i-1) 指向 a(i+1) 即删除了 a(i) */
s->next = p->next;
free(p);
p = NULL;
return value;
}6.查看栈顶元素
/**
* @description: 查看栈顶的元素
* @param - s : 要操作的栈的首结点指针
* @return : 栈顶的元素
*/
data_t Linkstack_Get_Pop(linkstack_t *s)
{
return (s->next->data);
}7.释放栈的空间
/**
* @description: 释放栈的空间
* @param - s : 要操作的栈的首结点指针
*/
void Linkstack_Free(linkstack_t *s)
{
linkstack_t *p;
/* 1.初始化 p 指向首结点 */
p = s;
/* 2.遍历整个链表 */
while(p)
{
s = s->next;
free(p);
p = s;
}
}