数据结构——栈

发布于:2024-07-11 ⋅ 阅读:(29) ⋅ 点赞:(0)

文章目录

1. 定义

2. 概念

3. 原理

函数调用栈的原理

调用栈的示例

代码示例

4. 存储结构

顺序栈

链式栈

顺序栈和链式栈的比较

5. 函数功能

6. 代码示例


1. 定义

栈 (stack) 是一种限制在表的一端进行插入和删除操作的线性表。插入和删除操作只能在栈顶(top)进行,遵循“后进先出” (LIFO, Last In First Out) 或“先进后出” (FILO, First In Last Out) 的原则。这种特性使得栈在某些场景中非常有用,如处理递归调用、表达式求值、深度优先搜索等。

特点:后进先出 (LIFO) 或先进后出 (FILO)

栈的基本特点是“后进先出”或“先进后出”。这意味着最新插入的元素最先被删除,而最早插入的元素最后被删除。栈的这种特性可以通过日常生活中的一些例子来理解:

  • 堆叠的盘子:最上面的盘子最先被拿走,而最下面的盘子最后被拿走。
  • 报纸:最上面的一期报纸最先被拿走,而最下面的一期报纸最后被拿走。
  • 电梯中的人们:最后进电梯的人最先出电梯。
  • 邮局的邮件:最新到达的邮件最先被处理。

这些例子都体现了栈的“后进先出”或“先进后出”的特性。

栈的基本操作

栈的基本操作包括:

  1. 入栈 (push):将元素压入栈顶。
  2. 出栈 (pop):将栈顶元素弹出。
  3. 查看栈顶元素 (peek):查看栈顶元素但不弹出。
  4. 检查栈是否为空 (isEmpty):判断栈是否为空。
  5. 获取栈的大小 (size):获取栈中元素的个数。

如下图所示,栈的入栈和出栈操作分别将元素添加到栈顶和从栈顶移除。

在这个图中,元素 a0​ 最先被压入栈底,接着依次是 a1​、a2、a3 和 a4。当执行出栈操作时,最先被移除的是 a4​,然后是 a3​、a2​、a1​,最后是 a0​。

2. 概念

栈顶 (Top)

  • 定义:栈顶是允许进行插入和删除操作的一端,又称为栈尾。栈顶由一个称为栈顶指针的位置指示器来指示,它是动态变化的。
  • 作用:在栈的所有操作中,栈顶是最重要的,因为所有的插入和删除操作都在栈顶进行。

栈底 (Bottom)

  • 定义:栈底是固定不变的,不允许进行插入和删除操作的一端,又称为表头。
  • 作用:栈底是栈的起始点,标志着栈的开始。

空栈

  • 定义:不含任何元素的空表称为空栈。
  • 作用:空栈的判定是栈操作的一个重要条件,当栈为空时,不能进行出栈操作。

栈的操作

  • 入栈 (Push):将元素压入栈顶。
  • 出栈 (Pop):将栈顶元素弹出。
  • 栈顶元素 (Peek):查看栈顶元素但不弹出。
  • 检查栈是否为空 (IsEmpty):判断栈是否为空。
  • 获取栈的大小 (Size):获取栈中元素的个数。

栈的顺序表表示

设栈 S={a1,a2,…,an},则 a1​ 称为栈底元素,an 为栈顶元素。栈中元素按 a1,a2,…,an 的次序进栈 (Push),出栈 (Pop) 的顺序为:an,…,a2,a1。

栈的操作示例

情况 1:初始情况下 top=−1

  1. 空栈:初始时栈为空,栈顶指针 top 指向 -1。
  2. Push A:将元素 A 入栈,栈顶指针 top 移动到 0,A 成为栈顶元素。
  3. Push B, C, D:依次将元素 B, C, D 入栈,栈顶指针 top 依次移动,最终 D 成为栈顶元素。
  4. Pop D:将栈顶元素 D 出栈,栈顶指针 top 移动到 2,C 成为新的栈顶元素。

情况 2:初始情况下 top=0

  1. 空栈:初始时栈为空,栈顶指针 top 指向 0。
  2. Push A:将元素 A 入栈,栈顶指针 top 移动到 1,A 成为栈顶元素。
  3. Push B, C, D:依次将元素 B, C, D 入栈,栈顶指针 top 依次移动,最终 D 成为栈顶元素。
  4. Pop D:将栈顶元素 D 出栈,栈顶指针 top 移动到 3,C 成为新的栈顶元素。

3. 原理

栈在计算机科学中的一个重要应用是函数调用。函数调用是程序执行过程中的基本操作之一,无论何种编程语言,函数调用都遵循一个“先进后出”的原则。这种“先进后出”机制的实现离不开栈。

函数调用栈的原理

在函数调用过程中,当前执行的函数需要调用另一个函数时,当前函数的状态(包括当前指令位置、局部变量等)会被压入栈中,然后开始执行被调用的函数。当被调用的函数执行完毕后,栈顶的状态会被弹出,恢复到之前的状态,继续执行原函数。

void funcA() {
    funcB();
}

void funcB() {
    funcC();
}

调用顺序和返回顺序

在上面的例子中:

  • 调用顺序funcA() -> funcB() -> funcC()
  • 返回顺序funcC() -> funcB() -> funcA()
  1. 调用 funcA()

    • 首先调用 funcA(),在执行 funcA() 时,程序遇到 funcB() 的调用,暂停 funcA() 的执行,把 funcA() 的状态压入栈中,然后转去执行 funcB()
  2. 调用 funcB()

    • funcB() 中,同样遇到 funcC() 的调用,暂停 funcB() 的执行,把 funcB() 的状态压入栈中,然后转去执行 funcC()
  3. 调用 funcC()

    • 执行 funcC() 时没有进一步的调用,所以 funcC() 完成后,程序从栈中弹出 funcB() 的状态,恢复执行 funcB()
  4. 返回 funcB()

    • funcB() 执行完毕后,程序从栈中弹出 funcA() 的状态,恢复执行 funcA()
  5. 返回 funcA()

    • 最后 funcA() 执行完毕,整个调用过程结束。

调用栈的示例

在函数调用过程中,栈的变化如下:

  1. 初始情况(栈为空):

    [空]
  2. 调用 funcA()

    [funcA]
  3. 调用 funcB()

    [funcA]
    [funcB]
    
  4. 调用 funcC()

    [funcA]
    [funcB]
    [funcC]
    
  5. funcC() 返回后

    [funcA]
    [funcB]
    
  6. funcB() 返回后

    [funcA]
    
  7. funcA() 返回后(栈为空):

    [空]
    

通过这个例子,我们可以直观地看到栈在函数调用过程中的作用。每次函数调用时,当前状态会被压入栈中,而函数返回时,栈顶状态会被弹出并恢复。这种机制保证了函数调用的有序进行和正确返回。

代码示例

在这个例子中,程序从 main 函数开始,调用 funcA,然后 funcA 调用 funcB,接着 funcB 调用 funcC。每次函数调用时,当前函数的状态都会被压入栈中,当调用的函数执行完毕后,程序会返回到上一个函数继续执行。

#include <stdio.h>

// 示例函数A
void funcA() {
    printf("Inside funcA\n");
    funcB();
}

// 示例函数B
void funcB() {
    printf("Inside funcB\n");
    funcC();
}

// 示例函数C
void funcC() {
    printf("Inside funcC\n");
}

int main() {
    funcA();  // 从这里开始调用链
    return 0;
}

 

4. 存储结构

栈的存储结构可以分为两种:顺序栈和链式栈。它们分别利用数组和链表来实现栈的功能。

顺序栈

顺序栈是使用数组来实现的栈结构。其特点是利用数组的顺序存储方式,直接通过下标访问数组中的元素。

顺序栈的基本操作

  1. 初始化栈
  2. 判断栈是否为空
  3. 判断栈是否满
  4. 入栈操作(push)
  5. 出栈操作(pop)
  6. 获取栈顶元素

链式栈

链式栈是使用链表来实现的栈结构。其特点是利用链表的链式存储方式,不需要预分配存储空间,能灵活地进行内存管理。

链式栈的基本操作

  1. 初始化栈
  2. 判断栈是否为空
  3. 入栈操作(push)
  4. 出栈操作(pop)
  5. 获取栈顶元素

顺序栈和链式栈的比较

顺序栈的优缺点

优点

  • 内存利用率高,存取元素速度快。
  • 支持随机访问,通过下标可以直接访问任意元素。

缺点

  • 需要预先分配固定大小的数组,可能会导致内存浪费或不够用。
  • 入栈和出栈操作可能需要移动大量元素,效率较低。

链式栈的优缺点

优点

  • 不需要预先分配存储空间,可以根据需要动态分配内存。
  • 插入和删除操作不需要移动元素,效率较高。

缺点

  • 由于每个节点需要额外存储指针,会占用更多的内存空间。
  • 访问速度较慢,不能随机访问,只能顺序访问。

5. 函数功能

栈是一种后进先出(LIFO,Last In First Out)的数据结构。本节将基于动态数组实现一个栈,实现以下函数:

  1. 初始化栈
  2. 返回栈内元素个数
  3. 添加新元素(压栈)
  4. 栈顶元素出栈并返回
  5. 释放栈内存

初始化栈

void initStack(Stack *stack, size_t capacity)
{
    stack->data = (int *)malloc(capacity * sizeof(int)); // 分配初始内存
    stack->size = 0;                                     // 初始化栈内元素个数为0
    stack->capacity = capacity;                          // 设置栈的初始容量
}

返回栈内元素个数

size_t getSize(const Stack *stack)
{
    return stack->size; // 返回栈内的元素个数
}

添加新元素(压栈)

void push(Stack *stack, int element)
{
    if (stack->size >= stack->capacity) // 如果栈已满,扩展栈容量
    {
        size_t newCapacity = stack->capacity * 2;
        stack->data = (int *)realloc(stack->data, newCapacity * sizeof(int));
        stack->capacity = newCapacity;
    }
    stack->data[stack->size++] = element; // 将新元素压入栈顶,并更新栈内元素个数
}

栈顶元素出栈并返回

int pop(Stack *stack)
{
    if (stack->size == 0)
    {
        printf("栈为空,无法出栈\n");
        exit(1); // 栈为空,无法出栈
    }
    return stack->data[--stack->size]; // 栈顶元素出栈,并更新栈内元素个数
}

释放栈内存

void destroyStack(Stack *stack)
{
    free(stack->data); // 释放栈内存
    stack->size = 0;   // 重置栈内元素个数
    stack->capacity = 0; // 重置栈容量
}

6. 代码示例

以下是一个完整代码,实现了一个基于动态数组的栈,包含初始化、添加新元素、弹出栈顶元素、获取栈内元素个数和释放栈内存的基本操作。

#include <stdio.h>
#include <stdlib.h>

// 栈结构
typedef struct
{
    int *data;       // 动态数组存储栈元素
    size_t size;     // 栈内元素个数
    size_t capacity; // 动态数组的容量
} Stack;

// 初始化栈
void initStack(Stack *stack, size_t capacity)
{
    stack->data = (int *)malloc(capacity * sizeof(int)); // 分配初始容量的内存
    stack->size = 0;                                     // 初始元素个数为0
    stack->capacity = capacity;                          // 设置容量
}

// 返回栈内元素个数
size_t getSize(const Stack *stack)
{
    return stack->size;
}

// 添加新元素(压栈)
void push(Stack *stack, int element)
{
    if (stack->size == stack->capacity) // 如果栈已满,需要扩展容量
    {
        stack->capacity *= 2; // 容量翻倍
        stack->data = (int *)realloc(stack->data, stack->capacity * sizeof(int)); // 重新分配内存
    }
    stack->data[stack->size] = element; // 将元素压入栈顶
    stack->size++;                      // 更新元素个数
}

// 栈顶元素出栈并返回
int pop(Stack *stack)
{
    if (stack->size == 0) // 如果栈为空
    {
        return -1; // 返回无效值
    }
    stack->size--;                 // 更新元素个数
    return stack->data[stack->size]; // 返回栈顶元素
}

// 释放栈内存
void destroyStack(Stack *stack)
{
    free(stack->data); // 释放动态数组内存
    stack->data = NULL;
    stack->size = 0;
    stack->capacity = 0;
}

int main()
{
    Stack myStack; // 声明栈

    // 初始化栈
    initStack(&myStack, 2);
    printf("初始化栈,初始容量为2\n");

    // 向栈压入元素
    push(&myStack, 1);
    push(&myStack, 2);
    push(&myStack, 3); // 添加一个元素以触发容量扩展

    printf("栈内元素个数:%zu\n", getSize(&myStack)); // 打印栈内元素个数

    // 弹出栈顶元素
    printf("弹出栈顶元素:%d\n", pop(&myStack));
    printf("弹出栈顶元素:%d\n", pop(&myStack));
    printf("弹出栈顶元素:%d\n", pop(&myStack));

    // 释放栈内存
    destroyStack(&myStack);
    printf("栈内存已释放\n");

    return 0;
}
  1. 栈结构定义

    • int *data: 动态数组,用于存储栈的元素。
    • size_t size: 当前栈内元素的个数。
    • size_t capacity: 动态数组的容量。
  2. 初始化栈

    • initStack(Stack *stack, size_t capacity): 分配初始容量的内存,并将栈的元素个数和容量初始化。
  3. 返回栈内元素个数

    • getSize(const Stack *stack): 返回当前栈内的元素个数。
  4. 添加新元素(压栈)

    • push(Stack *stack, int element): 将新元素压入栈顶,如果栈已满,则扩展栈的容量(容量翻倍)。
  5. 栈顶元素出栈并返回

    • pop(Stack *stack): 将栈顶元素弹出并返回,如果栈为空,则返回-1表示无效值。
  6. 释放栈内存

    • destroyStack(Stack *stack): 释放动态数组的内存,并将栈的元素个数和容量重置。

main 函数中,进行了以下操作:

  • 初始化栈并设置初始容量为2。
  • 向栈中压入元素,并打印栈内元素的个数。
  • 从栈中弹出元素,并打印出栈元素。
  • 释放栈的内存。