目录
顺序栈
结构
初始化一个空顺序栈
压栈
出栈
例子 十进制转八进制
链式栈
管理结构体的定义
初始化
压栈
出栈
顺序栈
顺序栈的实现，主要就是定义一块连续的内存来存放这些栈元素，同时为了方便管理， 再定义一个整数变量来代表当前栈顶元素在此连续内存中的偏移量，这样就可以很方便地知 道栈的状态和当前栈顶元素的位置，便于压栈和出栈操作。将栈内存地址和栈顶元素偏移量 放在一起，形成一个专门用来管理顺序栈的结构体，我们称之为管理结构体
结构
struct sequent_stack // 栈的管理结构体
{
int *stack; // 用 stack 指向一块连续的内存来存储栈元素
int size; // size 保存了该顺序栈的总大小
int top; // 用 top 来指示栈顶元素的偏移量
};初始化一个空顺序栈
一个空栈意味着栈中 没有元素，首先将 stack 指向的内存清零，其次更重要的是将 top 置为-1，同时规定-1 为 空栈的标志，这么做的好处是：将来压栈第一个元素之后，立即将 top 加 1 就会得到 0， 而第一个元素就放在 stack 所指向的内存的开端处，偏移量刚好为 0
struct sequent_stack *init_stack(int size) // 参数 size 表明空栈的初始大小
{
struct sequent_stack *s;
s = malloc(sizeof(struct seqent_stack)); // 申请栈管理结构体
if(s != NULL)
{
s->stack = calloc(size, sizeof(int)); // 申请栈空间，并由 stack 指向
s->size = size;
s->top = -1; // 将栈顶偏移量置为-1，代表空栈
}
return s;
}压栈
假设栈中已有一些元素，压栈的第一步首先要判 断栈是否已满，如果已满就要考虑扩充栈空间或者直接出错返回，如果未满，则需要将新的 栈顶元素堆叠到原栈顶之上
bool stack_full(struct sequent_stack *s)
{
return s->top >= s->size-1; // 判断栈是否已满
}
bool push(struct sequent_stack *s, int data)
{
if(stack_full(s)) // 如果栈已满，则出错返回
return false;
s->top++;
s->stack[s->top] = data;
return true;
}出栈
出栈之前，需要判断栈是否为空
bool stack_empty(struct sequent_stack *s)
{
return s->top == -1; // 判断栈是否为空
}
bool pop(struct sequent_stack *s, int *p) // p 指向存放栈顶元素的内存
{
if(stack_empty(s)) // 如果栈为空，则出错返回
return false;
*p = s->stack[s->top];
s->top--;
return true;
}例子 十进制转八进制
int main(void)
{
struct sequent_stack *s;
s = init_stack(10); // 初始化一个具有 10 个元素空间的顺序栈
int n;
scanf("%d", &n); // 让用户输入一个需要转换的十进制数
while(n > 0)
{
push(s, n%8); // 使用短除法将余数统统压栈
n /= 8;
}
int m;
while(!stack_empty(s)) // 只要栈不为空，就继续循环
{
pop(s, &m); // 出栈并打印出来
printf("%d", m);
}
printf("\n");
return 0;
}
链式栈
对于链式栈而言，同样也需要一系列基本操作：初始化、压栈、出栈、判断是否为空、 判断是否已满等等。首先，初始化一个空栈，意味着使得 top 指向 NULL，而 size 记为 0
管理结构体的定义
struct node // 栈节点结构体
{
int data;
struct node *next;
};
struct linked_stack // 栈管理结构体
{
struct node *top;
int size;
};初始化
struct linked_stack *init_stack(void)
{
struct linked_stack *s;
s = malloc(sizeof(struct linked_stack)); // 申请一个管理结构体
if(s != NULL)
{
s->top = NULL; // j 将栈置空
s->size = 0;
}
return s;
}压栈
压栈首先需要一个新节点，然后 将新的节点的 next 指针指向原来的栈顶，再让 top 指针指向该新的栈顶元素即可
创建新结点
struct node *new_node(int data) // 创建一个新的节点
{
struct node *new;
new = malloc(sizeof(struct node));
if(new != NULL)
{
new->data = data;
new->next = NULL;
}
return new;
}将新节点 new 压栈
bool push(struct linked_stack *s, struct node *new) // 将新节点 new 压栈
{
if(s == NULL || new == NULL)
return false;
new->next = s->top; // 第①步（见上图）
s->top = new; // 第②步
s->size++;
return true;
}出栈
对于出栈来说，首先要判断栈是否为空，如果不为空，则先要用一个指针 tmp 来保存 原栈顶元素的地址，然后返回栈顶元素，再将 top 指针指向下一个元素，最后要注意释放 tmp 所指向的原栈顶元素的内存空间
bool pop(struct linked_stack *s, int *p)
{
if(s == NULL || p == NULL || stack_empty(s))
return false;
struct node *tmp = s->top; // 第①步
*p = tmp->data; // 第②步
s->top = s->top->next; // 第③步
free(tmp); // 第④步
s->size--;
return true;
}
