数据结构——顺序栈

一、顺序栈的定义栈是限定仅在表尾进行插入和删除操作的线性表我们允许将插入和删除的一端叫做栈顶另一端称为栈底任何数据元素的栈称为空栈栈又称为后进先出的线性表栈顶指针指向的是最后一个元素的下一个位置注意首先他是一个线性表也就是说栈元素具有线性关系即前驱后继关系只不过他是一种特殊的线性表而已。1进栈入栈入栈栈的插入。2出栈弹栈栈的删除操作。二、顺序栈的主要代码实现1、顺序栈的结构体设计1与顺序表一样我们需要一个数组用来保存后续可能会保存的值需一个可放入的最大空间以及此时的数据元素个数2顺序栈一样他也需要一个数组用来保存后续可能会保存的值需一个可放入数组元素的最大空间以及数组的数据元素个数注我们不需要单独定义数组元素个数因为此时栈顶指针做的事情就是指向现有元素的下一个元素的位置因为数组是元素下标是以0开始所以此时栈顶指向的就是栈的元素的个数可以把他想象成数组#define STACK_INIT_SIZE 10//顺序表实现的栈 的初始大小 typedef int ElemType; //顺序栈的结构体设计 typedef struct SeqStack { ElemType* base;//1.指针类型用来接收malloc的返回值 int top;//2.栈顶指针用来指向栈顶元素的的下一个存储位置也能表示当前有效元素个数 int stacksize;//3.当前总的空间大小用来扩容 }SeqStack;2、初始化栈//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; }3、入栈雷同头插思路1顺序栈可以将其想象为数组与链表不同他的内存是连续的所以我们不需要有指针域来保存地址。2判断传入的指针是否有效3因为顺序栈相当于是数组所以此时如果栈元素所占的字节数已经达到栈的最大内存那么此时就没有空间可以插入元素所以需要扩容4因为栈顶指针指向的就是最后元素的下一个元素的位置因为栈是一个特殊的线性表他只可以在栈顶插入也只能在栈顶删除。此时栈顶指针指向的位置就是我们即将头插的位置。5将要插入的值给到栈顶指针指向的位置并将栈顶指针1//2.入栈 bool Push(SeqStack* psq, ElemType val) { //0.assert asser(psq!NULL); //1.判满 (如果满了就扩容) if (Full(psq)) { Increase(psq); } //2.直接给top指向的下标格子进行插入值 val psq-base[psq-top] val; //3.更新一下top栈顶指针的指向 psq-top; return true; }4、出栈雷同头删思路1因为顺序栈是受到限制的线性表他只能从栈顶插入栈顶删除。所以具有先进后出的特点。2判断传入指针是否有效3判断顺序表是否是空表如果是空表则删不了4找到合适的删除位置也就是头删利用栈顶指针因为栈顶指针指向最后一个有效元素的下一个位置此时直接让栈顶指针-1就意味着将原本的栈的最后有效元素给抛弃掉让原倒数第二个元素变成栈的新的最后一个有效元素bool Pop(SeqStack* psq) { //0.assert //1.判空 if (Empty(psq)) { return false; } //2.直接将top指针往后走一下认为刚才的最后一个元素(刚才的栈顶元素)是无效值即可 psq-top--; return true; }5、获取栈顶有效元素值只有读的权限没有改的权限思路1因为顺序栈是受到限制的线性表他只能从栈顶进行插入栈顶进行删除具有先进后出的特点2利用栈顶指针栈顶指针指向的前一个有效元素给获取出来3如果是空栈就获取不了直接退出//4.获取栈顶元素值只看栈顶元素的值 没有修改权限 ElemType Top(SeqStack* psq) { assert(psq ! NULL); if (Empty(psq)) { return; } return psq-base[psq-top--]; }6、扩容思路1因为扩容具有可能会在原始的基础上进行申请空间也可能新的一片空间也可能扩容失败所以需要另外申请一个指针来申请内存//5.扩容 *2 void Increase(SeqStack* psq) { ElemType*tmp (ElemType*)realloc(psq-base, psq-stacksize * sizeof(ElemType) * 2); if (tmp ! NULL) psq-base tmp; psq-stacksize * 2; }7、判空思路1当栈顶指针指向栈底时也就是0时此时说明没有有效元素2直接return psq-top0;当满足时就是true 当不满足时就是false//6.判空 bool Empty(SeqStack* psq) { return psq-top 0; }8.判满思路1判断栈顶指针指向的是否已经是栈的最大字节格子//7.判满 bool Full(SeqStack* psq) { return psq-top psq-stacksize; }9、打印//8.打印(用来测试的) void Show(SeqStack* psq) { for (int i 0; i psq-top; i) printf(%d , psq-base[i]); printf(\n); }10、清空思路1直接抛弃栈里所有元素将栈顶指针直接指向0void Clear(SeqStack* psq) { psq-top 0; }11、销毁思路1将申请的空间全部释放掉void Destroy(SeqStack* psq) { free(psq-base); psq-base NULL; psq-stacksize 0; psq-top 0; }12、主函数测试int main() { SeqStack st; Init_SeqStack(st); Push(st, 12); Push(st, 23); Push(st, 34); Show(st); Pop(st); Show(st); printf(TOP%d\n, Top(st)); Push(st, 12); Push(st, 23); Push(st, 34); Push(st, 12); Push(st, 23); Push(st, 34); Push(st, 12); Push(st, 23); printf(TOP:%d, StackSize:%d\n, st.top, st.stacksize); Push(st, 34); Show(st); printf(TOP:%d, StackSize:%d\n, st.top, st.stacksize); Clear(st); Show(st); printf(TOP:%d, StackSize:%d\n, st.top, st.stacksize); Destroy(st); printf(TOP:%d, StackSize:%d\n, st.top, st.stacksize); return 0; }