一、栈-顺序栈的原理
1.1 栈
栈： 限制在一端进行插入操作和删除操作的线性表（俗称堆栈）。
栈顶： 允许进行操作的一端称为“栈顶”。
栈底： 另一固定端称为“栈底”。
空栈： 当栈中没有元素时称为“空栈”。
特点 ： 后进先出（LIFO）。
1.2 栈的应用
1、浏览器的前进后退功能： 通过顺序栈可以实现浏览器的前进后退功能，将浏览历史记录存储在栈中。
2、函数调用栈： 顺序栈常被用于实现函数调用栈，记录函数调用的顺序和返回地址。
3、撤销操作： 顺序栈可以用于实现编辑器或文档处理程序中的撤销操作，将编辑操作记录在栈中，当需要撤销时，可以通过栈中的操作逆序执行。
4、迷宫求解： 顺序栈可以用于实现迷宫求解算法，将可行路径存储在栈中，回溯时可以通过栈中的路径信息找到上一步的位置。
二、栈-顺序栈的实现
2.1 顺序栈
它是顺序表的一种，其存储结构与顺序表相同，由数组定义。在配合使用数组下标表示的栈顶指针top（相对指针）的情况下，可以完成各种操作。
typedef int data_t ; //定义栈中数据元素的数据类型
typedef struct
{
data_t *data ; //用指针指向栈的存储空间
int maxlen; //当前栈的最大元素个数
int top ; //指示栈顶位置(数组下标)的变量
} sqstack; //顺序栈类型定义
2.2 顺序栈的创建
sqstack * stack_creat(int len)
{
sqstack *s;
//malloc
if((s = (sqstack *)malloc(sizeof(sqstack))) == NULL)
{
printf("malloc sqstack failed\n");
return NULL;
}
if((s->data = malloc(len * sizeof(data_t))) == NULL)
{
printf("malloc data failed\n");
return NULL;
}
memset(s->data, 0, len * sizeof(data_t));
s->maxlen = len;
s->top = -1;
return s;
}
2.3 入栈
算法思路：
①检查栈是否满？
②若没满，top++;s->data[s->top] = x;
int stack_push(sqstack *s, data_t value)
{
if(NULL == s)
{
printf("s is NULL\n");
return -1;
}
if(s->top == s->maxlen-1)
{
printf("stack is full\n");
return -1;
}
s->top++;
s->data[s->top] = value;
return 0;
}
2.4 出栈
data_t stack_pop(sqstack *s)
{
s->top--;
return (s->data[s->top+1]);
}
2.5 检查栈空与满
算法思路：
空：top为-1。
int stack_empty(sqstack *s)
{
if(NULL == s)
{
printf("s is NULL\n");
return -1;
}
return (s->top == -1 ? 1 : 0);
}
算法思路：
满：top等于maxlen-1。
int stack_full(sqstack *s)
{
if(NULL == s)
{
printf("s is NULL\n");
return -1;
}
return (s->top == s->maxlen-1 ? 1 : 0);
}
2.6 取栈顶元素
data_t stack_top(sqstack *s)
{
return (s->data[s->top]);
}
2.7 清空栈
int stack_clear(sqstack *s)
{
if(NULL == s)
{
printf("s is NULL\n");
return -1;
}
s->top = -1;
return 0;
}
2.8 栈内存释放
int stack_free(sqstack *s)
{
if(NULL == s)
{
printf("s is NULL\n");
return -1;
}
if(s->data != NULL)
{
free(s->data);
}
free(s);
return 0;
}
三、栈-链式栈原理及实现
3.1 链式栈
在数据结构的领域中，链表和栈是两种常见的数据结构，它们各自有着独特的特性和应用。现在，我们考虑一种特殊的情况：将链表用作栈的实现。插入操作和删除操作均在链表头部进行，链表尾部就是栈底，栈顶指针就是头指针。
typedef int data_t ; //定义栈中数据元素数据类型
typedef struct node_t {
data_t data ; //数据域
struct node_t *next ; //链接指针域
} linkstack_t ; //链栈类型定
3.2 链式栈的创建
①申请一个结点空间。
②data赋值，next置空。
③地址返回。
linkstack stack_create()
{
linkstack s;
s = (linkstack)malloc(sizeof(listnode));
if(NULL == s)
{
printf("malloc failed\n");
return NULL;
}
s->data = 0;
s->next = NULL;
return s;
}
3.3 判断是否为空栈
int stack_empty(linkstack s)
{
if(NULL == s)
{
printf("s is empty\n");
return -1;
}
return (s->next == NULL ? 1 : 0);
}
3.4 入栈
int stack_push(linkstack s, data_t value)
{
linkstack p;
if(NULL == s)
{
printf("s is NULL\n");
return -1;
}
p = (linkstack)malloc(sizeof(listnode));
if(NULL == p)
{
printf("malloc failed\n");
return -1;
}
p->data = value;
//p->next = NULL;
p->next = s->next;
s->next = p;
return 0;
}
3.5 出栈
data_t stack_pop(linkstack s)
{
linkstack p;
data_t t;
p = s->next;
s->next = p->next;
t = p->data;
free(p);
p = NULL;
return t;
}
3.6 返回栈顶元素
data_t stack_top(linkstack s)
{
return (s->next->data);
}
3.7 栈的释放
linkstack stack_free(linkstack s)
{
linkstack p;
if(NULL == s)
{
printf("s is NULL\n");
return NULL;
}
while(s != NULL)
{
p = s;
s = s->next;
printf("free:%d\n", p->data);
free(p);
}
return NULL;
}