📝栈的概念及结构
栈的概念:
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端
称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。栈是一种限定只允许在一端进行插入和删除操作的线性数据结构。
栈的主要特点:
先进后出(LIFO, Last In First Out)。新添加的元素都放在栈顶,取出元素时也是从栈顶取出。
只允许在一端(栈顶)进行插入和删除操作。插入操作称为入栈,删除操作称为出栈。
栈内元素的访问只能是顺序访问,不能随机访问。
通常使用数组或链表来实现栈。
栈的基本操作:
- push(item): 将元素添加到栈顶。 - pop(): 弹出栈顶元素,同时删除该元素。 - peek(): 返回栈顶元素,但不删除。 - isEmpty(): 检查栈是否为空。 - size(): 返回栈中元素的个数。
栈的结构:
使用数组实现栈时,维护一个top指针指向栈顶元素的下一个位置。入栈时将元素添加到数组top位置,并将top加1;出栈时从top位置取元素,并将top减1。
使用链表实现栈时,链表的头结点指向栈顶元素。入栈添加新节点到头结点后面,出栈删除头结点。
所以栈具有后进先出的特性,是一种限定只允许在一端插入和删除的线性数据结构。
🌉栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的
代价比较小。
使用数组实现栈确实具有一些优点：
内存连续性：数组在内存中是连续存储的，这使得对数组的访问速度相对较快，因为它允许缓存友好的访问模式。
尾部操作高效：数组在尾部插入或删除元素的时间复杂度为 O(1)，这使得栈的 push 和 pop 操作效率很高。
但是，使用数组实现栈也有一些限制：
4. 固定大小：数组的大小一旦确定，就不能动态扩展，如果栈需要存储的元素数量超过了数组的大小，就会导致栈溢出。
5. 动态调整的开销：当栈的大小超出数组容量时，需要重新分配更大的数组并将原始数据复制到新数组中，这会引入一定的开销。
相比，链表实现栈的优点是：
动态大小：链表可以根据需要动态扩展，不受固定大小的限制。
插入和删除操作的效率：在链表中，插入和删除操作的时间复杂度为 O(1)，不会像数组那样需要重新分配和复制数据。
但链表实现也有其缺点：
空间开销：链表中的每个节点都需要额外的指针来指向下一个节点，这会增加存储开销。
缓存不友好：由于节点在内存中不一定是连续存储的，可能会导致缓存未命中，从而降低访问速度。
因此，选择使用数组或链表实现栈取决于具体的需求和性能要求。如果需要高效的尾部操作和内存连续性，则数组实现可能更合适；而如果需要动态大小和高效的插入/删除操作，则链表实现可能更合适。
🌠栈的接口
本文将将使用动态链表实现栈：
StackCode.h
# define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> //方便修改 typedef int STDataType; typedef struct Stack { STDataType* _a; int _top;//栈顶 int _capacity;//容量 }Stack; //初始化栈 void StackInit(Stack* ps); //入栈 void StackPush(Stack* ps, STDataType x); //出栈 void StackPop(Stack* ps); //获取栈顶元素 STDataType StackTop(Stack* ps); //获取栈中有效元素个数 int StackSize(Stack* ps); //检测栈是否有空，如果为空返true，如果不为空，返回false； bool StackEmpty(Stack* ps); //销毁栈 void StackDestroy(Stack* ps);
🌉初始化栈
//初始化栈 void StackInit(Stack* ps) { assert(ps);//assert(ps)检查ps指针是否合法,防止空指针问题。 ps->_a = NULL;//栈初始化时还未分配数组空间。 ps->_capacity = ps->_top = 0; }
注意：
将_capacity和_top成员都设置为0。
_capacity表示栈的总容量,初始化时为0表示还未分配空间。
_top表示栈顶元素的下一个位置,作为栈的有效元素计数器。初始化时为0表示栈为空。
🌠入栈
void StackPush(Stack* ps, STDataType x) { assert(ps); //满了，需要扩容 if (ps->_top == ps->_capacity)//判断栈是否满了(ps->_top == ps->_capacity),如果满了需要扩容: {//如果_capacity为0,新容量为4,否则新容量为原容量的2倍 int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2; STDataType* temp = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType));//使用realloc重新分配数组空间 if (NULL == temp) { perror("realloc temp");//实际分配失败会打印错误并返回 return; } ps->_a = temp;//扩容成功后,更新_a指针和_capacity ps->_capacity = newcapacity; } //将元素x赋值到栈顶位置ps->_a[ps->_top] ps->_a[ps->_top] = x; ps->_top++; }
🌉出栈
//出栈 void StackPop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); ps->_top--; }
修改_top指针,就可以模拟出栈操作了。元素本身不做删除,只是修改指针来"移除"顶部元素。
🌠获取栈顶元素
//获取栈顶元素 STDataType StackTop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->_a[ps->_top - 1]; }
由于栈使用数组实现,元素位置从0开始编号，栈顶指针_top指向当前栈顶元素的下一个位置，所以实际栈顶元素的位置是_top - 1
🌉获取栈中有效元素个数
//获取栈中有效元素个数 int StackSize(Stack* ps) { assert(ps); return ps->_top; }
栈使用数组实现,元素从0开始插入，_top指针指向当前最后一个元素的下一个位置，所以_top值就代表当前栈中元素的个数
🌉检测栈是否为空
//检测栈是否为空，如果为空返回true，结果不为空false bool StackEmpty(Stack* ps) { assert(ps); if (ps->_top == 0) return true; else return false; }
🌉销毁栈
//销毁栈 void StackDestroy(Stack* ps) { assert(ps); ps->_a = NULL; ps->_capacity = ps->_top = 0; }
}
Stack.c文件：
# define _CRT_SECURE_NO_WARNINGS 1 #include "StackCode.h" //初始化栈 void StackInit(Stack* ps) { assert(ps); ps->_a = NULL; ps->_capacity = ps->_top = 0; } //入栈 void StackPush(Stack* ps, STDataType x) { assert(ps); //满了，需要扩容 if (ps->_top == ps->_capacity) { int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2; STDataType* temp = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType)); if (NULL == temp) { perror("realloc temp"); return; } ps->_a = temp; ps->_capacity = newcapacity; } ps->_a[ps->_top] = x; ps->_top++; } //出栈 void StackPop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); ps->_top--; } //获取栈顶元素 STDataType StackTop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->_a[ps->_top - 1]; } //获取栈中有效元素个数 int StackSize(Stack* ps) { assert(ps); return ps->_top; } //检测栈是否为空，如果为空返回true，结果不为空false bool StackEmpty(Stack* ps) { assert(ps); if (ps->_top == 0) return true; else return false; } //销毁栈 void StackDestroy(Stack* ps) { assert(ps); ps->_a = NULL; ps->_capacity = ps->_top = 0; }
🌉测试文件
Test.c
#include "STackCode.h" int main() { Stack s; StackInit(&s); StackPush(&s,1); StackPush(&s,2); StackPush(&s,3); StackPush(&s,4); int top = StackTop(&s); printf("%d", top); StackPop(&s); StackPush(&s, 5); StackPush(&s, 6); while (!StackEmpty(&s)) { int top = StackTop(&s); printf("%d", top); StackPop(&s); } StackDestroy(&s); return 0; }
测试结果：
