【C语言 | 数据结构】栈

文章目录

• • 前言
  • 1、栈
  • • 1.1栈的概念和定义
    • • 1.1.2栈的基本概念：
      • 1.2栈的方法(接口)
      • 1.3栈的实现方法
      • 1.4栈的性质
      • 1.5栈的应用
      • • 1.6栈的结构
        • 2、栈的实现
        • • • 2.1 顺序栈
            • • • 2.1.1 顺序栈的结构体
                • 2.1.2 顺序栈的初始化
                • 2.1.3 顺序栈的销毁
                • 2.1.4 顺序栈的入栈
                • 2.1.5 顺序栈的出栈
                • 2.1.5 顺序栈的判空
                • 2.1.5 顺序栈的栈顶元素
                • 2.1.5 顺序栈的有效个数
                • 2、顺序栈的完整代码实现

                  前言

                  前面讲解了数据结构中的链表、顺序表，接下来就是栈了

                  1、栈

                  1.1栈的概念和定义

                  栈是一种限定仅在表尾进行插入或删除操作的线性表。这一端被称为栈顶（top），相对地，另一端被称为栈底（bottom）。栈顶是允许操作的，而栈底是固定的。栈的插入操作通常称为进栈/压栈/入栈（PUSH），而删除操作则称为退栈/出栈（POP）。

                  1.1.2栈的基本概念：

                  栈顶(top)和栈底(bottom)：

                  • 栈顶：栈顶是栈中最后一个被插入或删除的元素的位置。当新的元素被添加到栈中时，它被放置在栈顶；同样，当元素从栈中被删除时，也是从栈顶开始删除的。
                  • 栈底：它表示栈的起始位置或者说是最早被插入的元素所在的位置，栈底是固定的。

                    1.2栈的方法(接口)

                    • Push（入栈/压栈）：在栈顶位置压入一个新数据。
                    • Pop（出栈）：从栈顶位置删除一个数据。
                    • Top：获取栈顶数据
                    • Size：获取栈的有效数据个数
                    • Empty：判断栈是否为空

                      1.3栈的实现方法

                      栈（Stack）的实现方法主要有两种：基于数组的实现和基于链表的实现。数组实现栈比较简单，需要使用realloc来扩容，使用链表来实现就不需要扩容了，可以按需申请空间，插入和删除操作的时间复杂度都为O(1)。

                      1.4栈的性质

                      1. 后进先出（LIFO）：栈遵循后进先出（Last In First Out）的原则，即最后进入栈的元素将最先被移出栈。这是栈最显著的特点。
                      2. 集合性：栈是由若干个元素集合而成，当没有元素的空集合称为空栈。
                      3. 线性结构：栈在逻辑上呈现一种线性结构，使用数组的话在物理逻辑上是连续的，但不同于普通的线性表，栈的插入和删除操作仅在一端（栈顶）进行。
                      4. 数学性质：当多个编号元素依某种顺序压入，且可任意时刻弹出时，所获得的编号元素排列的数目，恰好满足卡塔兰数列的计算，即Cn = C(2n, n) / (n+1)，其中n为编号元素的个数，Cn是可能的排列数目。
                      5. 栈的大小限制：栈的大小通常是有限的，当栈满时，不能再进行进栈操作，否则会引发溢出错误；当栈空时，不能再进行出栈操作，否则会引发下溢错误。

                      1.5栈的应用

                      • 函数调用：当一个函数调用另一个函数时，操作系统会给每个线程分配一块内存空间，这块内存被组织成栈结构。每个函数调用都需要将当前状态的信息（如函数调用前的参数、局部变量和程序计数器等）保存到栈中，等到函数调用结束后再从栈中弹出这些信息，恢复调用前的状态。这个过程被称作函数的压栈和弹栈操作。
                      • 表达式求值：在计算机中，对算术表达式进行求值时，通常使用栈来实现。编译器可以通过两个栈来实现，一个栈用来保存操作数，另一个栈用来保存运算符。从左到右遍历表达式，当遇到数字时，将其压入操作数栈；当遇到运算符时，与运算符栈栈顶元素进行比较，根据运算符的优先级进行相应的压栈或出栈操作，并计算表达式的值。

                        系统调用：在操作系统中，内核通常会将一个系统调用的参数、返回值和程序计数器等状态保存到进程的用户栈中，在系统调用结束后再从栈中弹出这些信息，恢复调用前的状态。

                        递归实现的非递归化：某些递归算法可以通过使用栈的数据结构转换为非递归形式，通过手动管理栈来模拟递归调用的过程。

                        1.6栈的结构

                        2、栈的实现

                        栈的实现可以使用数组来完成，也可以使用链表来完成，使用数组来完成相对简单，

                        2.1 顺序栈

                        顺序栈是使用顺序存储结构（数组）实现的栈，即利用一段连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设一个指针（通常称为栈顶指针）指示当前栈顶元素的位置。顺序栈具有结构简单、操作方便、易于实现等优点，因此在实际应用中非常广泛。

                        2.1.1 顺序栈的结构体

                        typedef int SDataType;typedef struct Stack{SDataType* _a;int _top;int _capacity;}Stack;

                        栈结构里面有三个成员，一个栈顶，一个栈的数组，一个栈的总容量

                        2.1.2 顺序栈的初始化

                        void StackInit(Stack* ps){ps->_a = NULL;ps->_capacity = ps->_top = 0;}

                        这里有两种方法初始化，一个是top始终指向栈顶的下一个元素的索引，一个是top始终是栈顶元素的索引。

                        2.1.3 顺序栈的销毁

                        // 销毁栈void StackDestroy(Stack* ps){assert(ps);free(ps->_a);ps->_a = NULL;ps->_capacity = ps->_top = 0;}

                        2.1.4 顺序栈的入栈

                        // 入栈void StackPush(Stack* ps, SDataType data){assert(ps); if (ps->_top == ps->_capacity){int _newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;SDataType* _new_a = (SDataType*)realloc(ps, _newcapacity * sizeof(SDataType));if (_new_a == NULL){perror("StackPush()::realloc()");exit(-1);}ps->_a = _new_a;ps->_capacity = _newcapacity;}ps->_a[ps->_top++] = data;}

                        2.1.5 顺序栈的出栈

                        // 出栈void StackPop(Stack* ps){assert(ps);assert(ps->_top > 0);ps->_top--;}

                        2.1.5 顺序栈的判空

                        // 判空void StackEmpty(Stack* ps){assert(ps);return ps->_top == 0;}

                        2.1.5 顺序栈的栈顶元素

                        // 获取栈顶元素void StackTop(Stack* ps){assert(ps);assert(ps->_top > 0);return ps->_a[ps->_top - 1];}

                        2.1.5 顺序栈的有效个数

                        // 计算栈内有效个数void StackSize(Stack* ps){assert(ps);return ps->_top;}

                        2、顺序栈的完整代码实现

                        #include #include #include #include typedef int SDataType;typedef struct Stack{SDataType* _a;int _top;int _capacity;}Stack;// 初始化void StackInit(Stack* ps){ps->_a = NULL;ps->_capacity = ps->_top = 0;}// 销毁栈void StackDestroy(Stack* ps){assert(ps);free(ps->_a);ps->_a = NULL;ps->_capacity = ps->_top = 0;}// 入栈void StackPush(Stack* ps, SDataType data){assert(ps); if (ps->_top == ps->_capacity){int _newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;SDataType* _new_a = (SDataType*)realloc(ps, _newcapacity * sizeof(SDataType));if (_new_a == NULL){perror("StackPush()::realloc()");exit(-1);}ps->_a = _new_a;ps->_capacity = _newcapacity;}ps->_a[ps->_top++] = data;}// 出栈void StackPop(Stack* ps){assert(ps);assert(ps->_top > 0);ps->_top--;}// 计算栈内有效个数void StackSize(Stack* ps){assert(ps);return ps->_top;}// 获取栈顶元素void StackTop(Stack* ps){assert(ps);assert(ps->_top > 0);return ps->_a[ps->_top - 1];}// 判空void StackEmpty(Stack* ps){assert(ps);return ps->_top == 0;}