数据结构——顺序栈

一、顺序栈的定义

栈是限定仅在表尾进行插入和删除操作的线性表，我们允许将插入和删除的一端叫做栈顶，另一端称为栈底，任何数据元素的栈称为空栈，栈又称为后进先出的线性表

栈顶指针：指向的是最后一个元素的下一个位置

注意：首先他是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系，只不过他是一种特殊的线性表而已。

（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->top==0;当满足时就是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）直接抛弃栈里所有元素，将栈顶指针直接指向0

void 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; }