栈的介绍
一种特殊的线性表，只允许在固定的一端进行插入（压栈）和删除（出栈）元素操作。栈中的数据元素遵守后进先出的原则,进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
文件分装
对应文件的代码
Stack.h
#pragma once //需要用到的库函数的头文件 #include<stdio.h> #include<stdlib.h> #include<assert.h> // 栈存储的数据类型 typedef int STDataType; // 栈的声明 typedef struct Stack { STDataType* _a; int _top; // 栈顶 int _capacity; // 容量 }Stack; // 初始化栈 void StackInit(Stack* ps); // 入栈 void StackPush(Stack* ps, STDataType data); // 出栈 void StackPop(Stack* ps); // 获取栈顶元素 STDataType StackTop(Stack* ps); // 获取栈中有效元素个数 int StackSize(Stack* ps); // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 int StackEmpty(Stack* ps); // 销毁栈 void StackDestroy(Stack* ps);
Stack.c
#include"Stack.h" // 初始化栈 void StackInit(Stack* ps) { //断言，保证指针的有效性 assert(ps); ps->_a = NULL; ps->_capacity = 0; ps->_top = 0; } // 入栈 void StackPush(Stack* ps, STDataType data) { assert(ps); // 入栈之前判断容量是否满了 if (ps->_capacity == ps->_top) { int newcapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity; STDataType* tmp = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType)); //判断是否成功开辟空间 if (!tmp) { printf("Realloc Fail!\n"); exit(-1); } ps->_a = tmp; ps->_capacity = newcapacity; } ps->_a[ps->_top++] = data; } // 出栈 void StackPop(Stack* ps) { assert(ps); ps->_top--; } // 获取栈顶元素 STDataType StackTop(Stack* ps) { assert(ps); return ps->_a[ps->_top - 1]; } // 获取栈中有效元素个数 int StackSize(Stack* ps) { assert(ps); return ps->_top; } // 检测栈是否为空，如果为空返回1，如果不为空返回0 int StackEmpty(Stack* ps) { assert(ps); return ps->_top == 0 ? 1 : 0; } // 销毁栈 void StackDestroy(Stack* ps) { assert(ps); //释放空间之前先判断是否开辟了空间 if (ps->_a != NULL) { free(ps->_a); ps->_a = NULL; } ps->_capacity = 0; ps->_top = 0; }
test.c
#include"Stack.h" int main() { Stack s; StackInit(&s); StackPush(&s, 1); StackPush(&s, 2); StackPush(&s, 3); StackPush(&s, 4); while (!StackEmpty(&s)) { printf("%d ", StackTop(&s)); StackPop(&s); } StackDestroy(&s); return 0; }
