- 栈的概念
只能在表尾进行插入(入栈)和删除(出栈)的数据结构，也就是表头和中间不能插入和删除(受到限制的线性表)；
其表尾比较特殊，我们一般把这个表尾叫做栈顶，表头端叫栈底，没有数据节点，则叫空栈。
特点：后进先出(先进后出) - 栈的表现形式
- 因为栈只能在表尾进行插入(入栈)和删除(出栈)，因此在写可操作函数时，没有头删头插等
- 结构体设计
struct Stack
{
第一个数据成员：ELEM_TYPE *base (指针类型，用来接收malloc从堆里申请的一整块连续的空 间)
第二个数据成员：int top (栈顶指针，但不用刻板的认为一定是指针类型)(即就是需要一个变量，既能表示下一个数据的插入位置，又能表示有多少个有效值
第三个数据成员：int stack_size(存储当前容量的大小)
};
注意：① base称为栈底指针，在顺序栈中，它始终指向栈底的位置， 如果base为
NULL，则表明栈结构不存在
② top为栈顶指针，其初始值指向栈底，即top=base可作为栈空的标记，每当插入
新的栈顶元素时，指针top增1，删除栈顶元素时，指针top减1
5. 子函数想影响父函数，必须取地址加解引用。
6. 代码
stack.h头文件
#pragma once
//顺序栈的结构体设计
#define INIT_SIZE 10
typedef int ELEM_TYPE;
typedef struct stack
{
ELEM_TYPE* base;//指针，用来接收malloc从堆内申请的一整块内存
int top;//和书上不一致，书上是指针类型，这块存的是数组下标，所以用int 类型，也可以达到指针的作用
int stack_size;//变量，存储当前的最大容量
}Stack,*PStack;
//顺序栈可执行函数的声明
//初始化
void Init_stack(struct stack* ps);
//入栈(插入节点)
bool Push(struct stack* ps,ELEM_TYPE val);
//出栈(获取栈顶元素值，并且删除)//用到一个输出参数
bool Pop(PStack ps, ELEM_TYPE *rtval); //ELEM_TYPE *告诉获取的值是多少，PStack ps获取值是否成功
//获取栈顶元素(获取栈顶元素值，但是不删除)
bool Top(PStack ps, ELEM_TYPE* rtval);
//判空
bool Isempty(PStack ps);
//判满
bool Isfull(PStack ps);
//扩容
void Inc(PStack ps);
//获取有效长度
int Get_length(PStack ps);
//清空
void Clear(PStack ps);
//销毁
void Destroy(PStack ps);
//打印
void Show(PStack ps);
stack.cpp头文件
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include"stack.h"
//顺序栈可执行函数的声明
//初始化
void Init_stack(struct stack* ps)
{
assert(ps != NULL);
if (ps == NULL)
{
return;
}
ps->base = (ELEM_TYPE*)malloc(INIT_SIZE * sizeof(struct stack));
ps->top = 0;//初始状态
ps->stack_size = INIT_SIZE;
}
//入栈(插入节点)
bool Push(struct stack* ps, ELEM_TYPE val)
{
assert(ps != NULL);
if (ps == NULL)
{
return false;
}
//入栈，需要判满，如果满了，扩容
if (Isfull(ps))
{
Inc(ps);
}
//肯定有额外空间入栈
ps->base[ps->top] = val;
//记得，插入和删除结束后挪动栈顶指针
ps->top++;
return true;
}
//出栈(获取栈顶元素值，并且删除)//用到一个输出参数
bool Pop(PStack ps, ELEM_TYPE* rtval) //ELEM_TYPE *告诉获取的值是多少，PStack ps获取值是否成功
{
assert(ps != NULL);
if (ps == NULL)
{
return false;
}
//出栈，需要判空
if (Isempty(ps))
{
return false;
}
ps->top--;
*rtval = ps->base[ps->top];
return true;
}
//获取栈顶元素(获取栈顶元素值，但是不删除)
bool Top(PStack ps, ELEM_TYPE* rtval)
{
assert(ps != NULL);
if (ps == NULL)
{
return false;
}
if (Isempty(ps))
{
return false;
}
*rtval = ps->base[ps->top - 1];
return true;
}
//判空
bool Isempty(PStack ps)
{
return ps->top == 0;
}
//判满
bool Isfull(PStack ps)
{
return ps->top == ps->stack_size;
}
//扩容
static void Inc(PStack ps)
{
assert(ps != NULL);
if (ps == NULL)
{
return;
}
//当前面的参数为0，相当于malloc,后边参数为0，相当于free
ps->base = (ELEM_TYPE *)realloc(ps->base, ps->stack_size * sizeof(struct stack)*2);//前边变量放原先的空间的地址，后边变量放需要扩容后的总大小
assert(ps->base != NULL);//内存扩容成功
ps->stack_size *= 2;
}
//获取有效长度
int Get_length(PStack ps)
{
return ps->top;//代表当前总个数，也代表下一个值的插入位置
}
//清空 不需要释放malloc申请的空间，只需要将栈顶指针改为0，则认为里面数据都失效
void Clear(PStack ps)
{
ps->top = 0;
}
//销毁 需要释放malloc申请的空间
void Destroy(PStack ps)
{
assert(ps != NULL);
if (ps == NULL)
{
return;
}
free(ps->base);
ps->base = NULL;//防止野指针
ps->stack_size = ps->top = 0;
}
//打印
void Show(PStack ps)
{
for (int i = 0; i < ps->top; i++)
{
printf("%d ", ps->base[i]);
}
printf("\n");
}
main主函数
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include"stack.h"
int main()
{
struct stack ps;
Init_stack(&ps);
for (int i = 0; i < 15; i++)
{
Push(&ps, i + 1);
}
Show(&ps);
printf("length=%d\n", Get_length(&ps));
printf("stack_size=%d\n", ps.stack_size);
ELEM_TYPE tmp;
bool tag1 = false;
tag1 = Pop(&ps, &tmp);
if (tag1)
{
printf("tmp=%d\n", tmp);
}
Show(&ps);
ELEM_TYPE tmp2;
bool tag2 = Top(&ps, &tmp2);
if (tag2)
{
printf("tmp2=%d\n", tmp2);
}
Show(&ps);
Clear(&ps);
printf("length=%d\n", Get_length(&ps));
printf("stack_size=%d\n", ps.stack_size);
Destroy(&ps);
//Destroy(&ps);//可以销毁两次，是因为处理野指针了
return 0;
}
运行结果：
