C语言中栈的结构和函数接口的使用示例
[Pokemon]大猫猫 人气:0一、栈的结构
栈:一种操作受限的线性表,只允许在线性表的一端进行插入和删除操作,进行插入删除的一端称作栈顶,另一端称之为栈底
通过动态顺序表的实现,可以发现在对数组进行尾插尾删时效率很高, 因此栈可以用数组实现,将数组的尾部作为栈顶, 结构如下:
通过单链表的实现,可以发现在对链表进行头插头删时效率很高,因此也可以用链表来实现,将单链表的头结点作为栈顶,结构如下:
综合考虑:数组的实现方法更优,本篇以数组的方式介绍栈的结构和函数接口
//栈的元素类型 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; }
加载全部内容