目录
栈（动态版）的功能实现（<入栈，出栈>&<顺序，乱序>）测试示例：
后记：●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！
《数据结构(C语言版)》实战项目之栈（动态版）的功能实现
——By 作者：新晓·故知
一、完整源码：
完整源码如下，欢迎复制测试指正！
栈（动态版）的功能实现（<入栈，出栈>&<顺序，乱序>）测试示例：
编辑
完整源码：
Test.c:
#include "Stack.h" //栈的测试 //按照顺序压栈、出栈 void TestStack1() { ST st; StackInit(&st); ////1.一个一个创建数据，可连续也可不连续 //StackPush(&st, 1); //StackPush(&st, 2); //StackPush(&st, 3); //StackPush(&st, 4); //StackPush(&st, 5); //2.使用循环压栈创建数据 for (int i = 0; i < 6; ++i) { StackPush(&st, i); } while (!StackEmpty(&st)) { printf("%d ", StackTop(&st)); StackPop(&st); } printf("\n"); StackDestroy(&st); } //乱序压栈、出栈 void TestStack2() { ST st; StackInit(&st); //1.一个一个创建数据，可连续也可不连续 StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); //1、2、3压栈，3出栈，再进行4、5压栈，再打印整体出栈 printf("%d ", StackTop(&st)); StackPop(&st); StackPush(&st, 4); StackPush(&st, 5); while (!StackEmpty(&st)) { printf("%d ", StackTop(&st)); StackPop(&st); } printf("\n"); StackDestroy(&st); } int main() { TestStack1(); TestStack2(); return 0; }
Stack.c:
#include "Stack.h" //栈的接口功能函数 //初始化 void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->top = 0; ps->capacity = 0; } //销毁 void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; } //压栈 void StackPush(ST* ps, STDataType x) { assert(ps); //需要注意top的位置，取决于如何对top的初始化 //本程序top的初始化位置为0 //判断是否栈满，栈满即需要扩容 if (ps->top == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //此处的4是随机合理给定，无特别规定，*2是合理利用空间 ps->a = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType)); //relloc给的是总的新空间的大小 if (ps->a == NULL) { printf("relloc fail\n"); exit(-1); } ps->capacity = newCapacity; } ps->a[ps->top] = x; ps->top++; } //出栈 void StackPop(ST* ps) { assert(ps); assert(ps->top > 0); --ps->top; } //判断栈是否为空 bool StackEmpty(ST* ps) { assert(ps); ////写法1 //if (ps->top > 0) //{ // return false; //} //else //{ // return true; //} //写法2 return ps->top == 0; } //栈顶 STDataType StackTop(ST* ps) { assert(ps); assert(ps->top>0); return ps->a[ps->top - 1]; } //查看栈的数据 int StackSize(ST* ps) { assert(ps); return ps->top; }
Stack.h:
#pragma once #include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include<assert.h> //静态(不常用） //struct Stack //{ // int a[N]; // int top; //栈顶的位置 //}; //动态 typedef int STDataType; typedef struct Stack { STDataType* a; int top; //栈顶的位置 int capacity; //容量 }ST; //接口功能函数 //初始化 void StackInit(ST* ps); //销毁 void StackDestroy(ST* ps); //压栈 void StackPush(ST* ps, STDataType x); //出栈 void StackPop(ST* ps); //判断栈是否为空 bool StackEmpty(ST* ps); //栈顶 STDataType StackTop(ST* ps); //查看栈的数据 int StackSize(ST* ps);
二、栈的功能实现分析：
1.栈的概念及结构：
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
编辑
编辑
2.栈的实现方式：
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
编辑
编辑
3.栈的实现步骤：
（1）动态结构定义：
//动态 typedef int STDataType; typedef struct Stack { STDataType* a; int top; //栈顶的位置 int capacity; //容量 }ST;
（2）栈的初始化：
//栈的接口功能函数 //初始化 void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->top = 0; ps->capacity = 0; }
（3）压栈（入栈）：
//压栈 void StackPush(ST* ps, STDataType x) { assert(ps); //需要注意top的位置，取决于如何对top的初始化 //本程序top的初始化位置为0 //判断是否栈满，栈满即需要扩容 if (ps->top == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //此处的4是随机合理给定，无特别规定，*2是合理利用空间 ps->a = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType)); //relloc给的是总的新空间的大小 if (ps->a == NULL) { printf("relloc fail\n"); exit(-1); } ps->capacity = newCapacity; } ps->a[ps->top] = x; ps->top++; }
（4）出栈：
//出栈 void StackPop(ST* ps) { assert(ps); assert(ps->top > 0); --ps->top; }
（5）判断栈是否为空：
//判断栈是否为空 bool StackEmpty(ST* ps) { assert(ps); ////写法1 //if (ps->top > 0) //{ // return false; //} //else //{ // return true; //} //写法2 return ps->top == 0; }
（6）栈顶查找：
//栈顶 STDataType StackTop(ST* ps) { assert(ps); assert(ps->top>0); return ps->a[ps->top - 1]; }
（7）查看栈的数据：
//查看栈的数据 int StackSize(ST* ps) { assert(ps); return ps->top; }
（8）栈的销毁：
//销毁 void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; }
栈的辨析：
编辑
栈顶top的位置：
编辑
