简介：本系列博客为C数据结构系列内容，通过代码来具体实现某个经典简单数据结构
适宜人群：已大体了解C语法同学
作者留言：本博客相关内容如需转载请注明出处，本人学疏才浅，难免存在些许错误，望留言指正
作者博客链接：睡觉待开机
1.认识栈
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除
操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）
的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
2.栈选取设计的思路
该用数组还是链表来实现栈呢？我们在实现栈之前不妨先分析一下:
如果用数组实现栈
如果用链表来实现
综上所述，我们发现链表与数组都可以比较恰当。通常情况下，一般使用数组实现居多
下面我使用数组进行演示:
3.所有接口一览
4.各个接口的实现
注：因为在实现上很简单，因而不做详细说明。
在实现上，底层是数组，也可以说是顺序表。
1.初始化与销毁接口
void StackInit(ST* ps) { assert(ps); ps->arr = NULL; ps->capacity = ps->top = 0; } void StackDestroy(ST* ps) { assert(ps); free(ps->arr); ps->arr = NULL; ps->capacity = ps->top = 0; ps = NULL; }
2.入栈出栈
void StackPush(ST* ps, STDateType x) { assert(ps); if (ps->capacity == ps->top) { //初始值的情况 int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; STDateType* temp = (STDateType*)realloc(ps->arr, newcapacity * sizeof(STDateType)); if (temp == NULL) { perror("malloc fail!"); exit(-1); } ps->arr = temp; ps->capacity = newcapacity; } ps->arr[ps->top++] = x; } void StackPop(ST* ps) { assert(ps); assert(ps->top > 0); ps->top--; } STDateType StackTop(ST* ps) { assert(ps); return ps->arr[ps->top - 1]; }
3.统计与判断
bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } int StackSize(ST* ps) { assert(ps); return ps->top; }
5.全部代码
#define _CRT_SECURE_NO_WARNINGS 1 #include"Stack.h" test1() { ST st; StackInit(&st); StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); StackPush(&st, 4); StackPush(&st, 5); StackPush(&st, 6); while (!StackEmpty(&st)) { printf("%d", StackTop(&st)); StackPop(&st); } StackDestroy(&st); } int main() { test1(); return 0; }
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> //用数组的方式实现栈结构 typedef int STDateType; typedef struct Stack { STDateType* arr; int top; int capacity; }ST; //初始化与销毁 void StackInit(ST* ps); void StackDestroy(ST* ps); //入栈出栈 void StackPush(ST* ps,STDateType x); STDateType StackTop(ST* ps); void StackPop(ST* ps); //统计与判断 bool StackEmpty(ST* ps); int StackSize(ST* ps);
#define _CRT_SECURE_NO_WARNINGS 1 #include"Stack.h" void StackInit(ST* ps) { assert(ps); ps->arr = NULL; ps->capacity = ps->top = 0; } void StackDestroy(ST* ps) { assert(ps); free(ps->arr); ps->arr = NULL; ps->capacity = ps->top = 0; ps = NULL; } void StackPush(ST* ps, STDateType x) { assert(ps); if (ps->capacity == ps->top) { //初始值的情况 int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; STDateType* temp = (STDateType*)realloc(ps->arr, newcapacity * sizeof(STDateType)); if (temp == NULL) { perror("malloc fail!"); exit(-1); } ps->arr = temp; ps->capacity = newcapacity; } ps->arr[ps->top++] = x; } void StackPop(ST* ps) { assert(ps); assert(ps->top > 0); ps->top--; } STDateType StackTop(ST* ps) { assert(ps); return ps->arr[ps->top - 1]; } bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } int StackSize(ST* ps) { assert(ps); return ps->top; }
完。
