数据结构——5.顺序栈

前言链表、顺序表是常规线性表而栈与队列属于操作受限的特殊线性表。本章主要讲解栈的基础概念并实现动态扩容的顺序栈。一、栈基本概念栈定义栈是插入、删除操作受到限制的线性表所有数据操作仅能在同一端完成。相关术语栈顶允许执行插入、删除操作的一端。栈底不允许增删操作的另一端。空栈内部不包含任何数据元素的栈。核心特性栈遵循后进先出Last In First OutLIFO规则最后存入的数据会最先被取出。基本操作名称入栈 / 压栈向栈中插入元素类比子弹装入弹夹。出栈 / 弹栈从栈中删除元素类比子弹从弹夹射出二、代码实现#define _CRT_SECURE_NO_WARNINGS #include stdio.h #include stdlib.h #include string.h #include assert.h #include memory.h #include SeqStack_1.h //1.初始化函数 void Init_SeqStack(SeqStack* psq) { assert(psq ! NULL); psq-base (ELEMTYPE*)malloc(STACK_INIT_SIZE * sizeof(ELEMTYPE)); if (psq-base NULL) exit(EXIT_FAILURE); psq-top 0; psq-stacksize STACK_INIT_SIZE; } //2.入栈 bool Push(SeqStack* psq, ELEMTYPE val) { //0. assert(psq ! NULL); //1.判满。如果满就扩容 if (Full(psq)) { Increase(psq); } //2.直接给top下标格子进行插入值val psq-base[psq-top] val;// //3.更新一下top栈顶指针的指向 psq-top; return true; } //3.出栈 bool Pop(SeqStack* psq) { //0 assert(psq ! NULL); //1.判空 if (Empty(psq)) return false; //2.直接将top指针往后走一下认为刚才的最后一个元素刚才的栈顶元素是无效值 psq-top--; return true; } //4.获取栈顶元素值只瞄一眼栈顶最新元素值是多少别动他 ELEMTYPE Top(SeqStack* psq) { //0 assert(psq ! NULL); //1.判空 if (Empty(psq)) exit(EXIT_FAILURE); //2.获取栈顶元素值 return psq-base[psq-top - 1];//要栈顶指针的下一个指向 } //5.扩容 void Increase(SeqStack* psq) { ELEMTYPE* tmp (ELEMTYPE*)realloc(psq-base, psq-stacksize * sizeof(ELEMTYPE) * 2); if (tmp ! NULL) psq-base tmp; psq-stacksize * 2; } //6.判空 bool Empty(SeqStack* psq) { //0 assert(psq ! NULL); return psq-top 0; } //7.判满 bool Full(SeqStack* psq) { // assert(psq ! NULL); return psq-top psq-stacksize; } //8.打印(用来测试的) void Show(SeqStack* psq) { assert(psq ! NULL); for (int i 0; i psq-top; i) { printf(%d , psq-base[i]); } printf(\n); } //9.清空 void Clear(SeqStack* psq) { assert(psq ! NULL); psq-top 0; } //10.销毁 void Destroy(SeqStack* psq) { assert(psq ! NULL); free(psq-base); psq-base NULL; psq-stacksize 0; psq-top 0; } int main() { SeqStack st; Init_SeqStack(st); Push(st, 12); Push(st, 34); Push(st, 56); Show(st); Pop(st); Show(st); return 0; }三、运行结果四、代码说明本实现为动态顺序栈空间不足时会自动扩容不受初始容量限制。top为栈顶标记始终指向下一个待入栈的位置空栈时top 0。操作规范所有接口均加入断言校验防止空指针访问内存分配失败直接终止程序保证代码健壮性。区分Clear和DestroyClear仅清空元素保留内存Destroy彻底释放动态数组内存。