[数据结构]栈的实现与应用

文章目录

一、引言
二、栈的基本概念
- 1、栈是什么
- 2、栈的实现方式对比
- 3、函数栈帧
三、栈的实现
- 1、结构体定义
- 2、初始化
- 3、销毁
- 4、显示
- 5、数据操作
四、分析栈
- 1、优点
- 2、缺点
五、总结
- 1、练习题
- 2、源代码

一、引言

栈，作为一种基础且重要的数据结构，在计算机科学领域中有着广泛的应用。它不仅为函数调用提供了必要的支持，还在算法设计和问题解决中发挥着关键作用。本文将对栈的基本概念、实现方式以及函数栈帧进行详细的介绍和分析。

二、栈的基本概念

1、栈是什么

栈是一种特殊的线性数据结构，其只允许在固定的一端进行插入和删除操作。插入和删除的这一端被称为栈顶，而另一端则被称为栈底。栈遵循后进先出的原则，即最后插入的元素会最先被删除。这种特性使得栈在算法设计和问题解决中具有独特的优势。

请添加图片描述

2、栈的实现方式对比

数组实现：将数组的尾部充当栈顶，数据的插入与删除操作变得非常高效。同时数组的结构，使得其CPU高速缓存的命中率较高。唯一的缺陷就是，扩容或缩容会有一定的性能开销。
链表实现：采用单链表结构，将链表头部设为栈顶，数据的插入与删除操作同样能高效完成。但链表需要额外的存储空间来保存指针信息，且由于链表的结构，CPU高速缓存的命中率相对较低。此外，链表实现的复杂度相较于数组实现也更高一些。

3、函数栈帧

在函数调用过程中，系统会为每个函数分配一个栈帧。栈帧中存储了函数的局部变量、参数以及返回地址等信息。当函数执行完毕后，其栈帧会被销毁，从而释放占用的栈空间。函数栈帧的分配和销毁过程体现了栈的后进先出原则。

函数栈帧的存在使得函数调用具有嵌套性，即一个函数可以调用另一个函数，而被调用的函数又可以继续调用其他函数。这种嵌套调用关系通过栈来维护，确保了函数调用的正确性和稳定性。

三、栈的实现

1、结构体定义

首先，定义了栈的数据结构。栈使用动态数组来存储元素，同时记录了栈顶索引和栈的容量。

typedef int DataType;
typedef struct Stack {
	DataType* array;
    int top;
	int capacity;
}S;

2、初始化

接下来，实现了栈的初始化函数。该函数为栈分配内存，并初始化栈顶索引和容量。

void Init(S* ps, int capacity)
{
    assert(ps != NULL && capacity >= 0);

    DataType* pos = (DataType*)malloc(sizeof(DataType) * capacity);
    if (pos == NULL)
    {
        fprintf(stderr, "内存分配失败");
        exit(EXIT_FAILURE);
    }

    ps->array = pos;
    ps->capacity = capacity;
    ps->top = -1;
}

3、销毁

实现了栈的销毁函数。该函数释放栈所占用的内存，并将栈的指针、容量和栈顶索引重置为初始状态。

void Destroy(S* ps)
{
    if (ps == NULL)
        return;

    free(ps->array);
    ps->array = NULL;
    ps->capacity = 0;
    ps->top = -1;
}

4、显示

实现了栈的显示函数。该函数遍历栈中的元素，并调用用户定义的打印函数来打印每个元素。

void Print(S* ps, void (*Prin)(DataType))
{
    assert(ps != NULL);

    for (int i = ps->top; i >= 0; i--)
    {
        Prin(ps->array[i]);
    }
    printf("\n");
}

5、数据操作

void Push(S* ps, DataType data)
{
    assert(ps != NULL);

    if (ps->top == ps->capacity - 1)
    {
        int capacity = ps->capacity == 0 ? 2 : ps->capacity * 2;
        DataType* pos = (DataType*)realloc(ps->array, sizeof(DataType) * capacity * 2);
        if (pos == NULL)
        {
            fprintf(stderr, "内存分配失败");
            exit(EXIT_FAILURE);
        }

        ps->array = pos;
        ps->capacity = capacity;
    }

    ps->array[++(ps->top)] = data;
}

void Pop(S* ps)
{
    assert(ps != NULL && ps->top != -1);

    if (ps->capacity > 64 && ps->top < ps->capacity / 3)
    {
        int capacity = ps->capacity / 3;

        DataType* pos = (DataType*)realloc(ps->array, sizeof(DataType) * capacity);
        if (pos == NULL)
        {
            fprintf(stderr, "内存分配失败");
            exit(EXIT_FAILURE);
        }

        ps->array = pos;
        ps->capacity = capacity;
    }

    ps->top--;
}

DataType Top(S* ps)
{
    assert(ps != NULL);

    return ps->array[ps->top];
}