目录
一、栈的构造二、栈的函数接口
1. 初始化和销毁2. 入栈和出栈3. 访问栈顶元素以及判空和元素个数
一、栈的构造
栈：一种操作受限的线性表，只允许在线性表的一端停止插入和删除操作，停止插入删除的一端称作栈顶，另一端称之为栈底
通过动态顺序表的实现，可以发如今对数组停止尾插尾删时效率很高， 因而栈可以用数组实现，将数组的尾部作为栈顶， 构造如下：
通过单链表的实现，可以发如今对链表停止头插头删时效率很高，因而也可以用链表来实现，将单链表的头结点作为栈顶，构造如下：
综合考虑：数组的实现方法更优，本篇以数组的方式介绍栈的构造和函数接口
//栈的元素类型
typedef int StackDataType;
//栈的构造
typedef struct Stack
{
StackDataType* a; //寄存元素的数组
int top; //指向栈顶元素的下一个位置
int capacity; //容量
}Stack;
二、栈的函数接口
1. 初始化和销毁
初始时给栈分配一些空间，并将 top置为 0，代表指向栈顶元素的下一个位置
初始化函数如下：
void StackInit(Stack* ps)
{
assert(ps);
//开拓空间
ps->a = (StackDataType*)malloc(sizeof(StackDataType) * 4);
if (ps->a == NULL)
{
perror("malloc");
exit(-1);
}
ps->top = 0;
ps->capacity = 4;
}
栈是动态开拓的，不用时需要销毁
销毁函数如下：
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
2. 入栈和出栈
入栈：在栈顶插入元素，当空间不够时需要扩容
入栈函数如下：
void StackPush(Stack* ps, StackDataType x)
{
assert(ps);
//空间不够时，需要扩容
if (ps->top == ps->capacity)
{
StackDataType* tmp = (StackDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(StackDataType));
if (tmp == NULL)
{
perror("realloc");
exit(-1);
}
ps->a = tmp;
ps->capacity *= 2;
}
//top 指向栈顶元素的下一个位置，因而 top 先插入数据，然后再自增
ps->a[ps->top] = x;
ps->top++;
}
出栈：删除栈顶元素
出栈函数如下：
void StackPop(Stack* ps)
{
assert(ps);
//栈为空时不能删除，这里直接调用判空函数
assert(!StackEmpty(ps));
ps->top--;
}
3. 访问栈顶元素以及判空和元素个数
返回栈顶元素函数如下：
StackDataType StackTop(Stack* ps)
{
assert(ps);
//栈为空时不能取栈顶元素，这里直接调用判空函数
assert(!StackEmpty(ps));
//top 指向栈顶元素的下一个，所以需要-1
return ps->a[ps->top - 1];
}
判空函数如下：
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
元素个数函数如下：
size_t StackSize(Stack* ps)
{
assert(ps);
//top 即为元素个数
return ps->top;
}
到此这篇关于C语言中栈的构造和函数接口的使用示例的文章就介绍到这了,更多相关C语言栈的构造内容请搜索网站以前的文章或继续阅读下面的相关文章希望大家以后多多支持网站！ |
