《数据结构全解析：栈（数组实现）》

发布于：2025-09-08 ⋅ 阅读:(12) ⋅ 点赞:(0)

目录

一.栈的概念和结构

1.1 栈的核心概念

1.2 栈的结构定义

二.栈的初始化

三.关于栈的操作

1. 初始化栈（StackInit）

2. 检查容量并扩容（StackCheckCapacity）

3. 入栈（StackPush）

4. 出栈（StackPop）

5. 取栈顶元素（StackTop）

6. 判空（StackEmpty）

7. 销毁栈（StackDestroy）

四. 操作示例

总结

五. 完整代码如下(自行取用)

一.栈的概念和结构

栈是一种重要的线性数据结构，其核心特性是 --“先进后出”（Last In, First Out，LIFO）--，即最后进入栈的元素最先被取出。这种特性类似于日常生活中的 “堆叠” 场景（如叠放的盘子、书本），只能从顶端操作。

1.1 栈的核心概念

  1. 操作限制
    栈只允许在一端进行数据的插入和删除操作，这一端被称为栈顶（Top）；另一端称为栈底（Bottom），栈底元素是最先进入且最后被取出的。

  2. 基本操作

    • 入栈（Push）：将元素添加到栈顶（栈顶指针上移）。
    • 出栈（Pop）：从栈顶移除元素（栈顶指针下移）。
    • 取栈顶元素（Top/Peek）：获取栈顶元素的值（不删除）。
    • 判空（IsEmpty）：判断栈是否没有元素。
    • 求长度（Size）：获取栈中元素的个数。
  3. 栈的实现依赖于底层存储结构，常见的有两种：顺序栈（数组实现）链式栈（链表实现）

下面我们将学习用数组来实现栈  我们只需要对数组的尾部来进行操作就行

优势：

  • 访问速度快：栈顶元素通过数组下标直接访问（arr[top]），时间复杂度 O (1)，适合频繁读取栈顶的场景。
  • 内存紧凑：仅存储数据本身，无额外指针开销，内存利用率高（尤其在元素数量稳定时）。
  • 缓存友好：连续内存布局符合 CPU 缓存的局部性原理，访问相邻元素时缓存命中率高，实际运行速度更快。

1.2 栈的结构定义

下面让我们来观察一下用数组来实现结构体栈的定义

// 定义栈中元素的数据类型（可根据需求修改，如int、char等）
typedef int STDataType; 
typedef struct Stack
{
	STDataType* arr; //数组 用于存放数据
	int top; //对顶部进行操作 也是栈内有效数据
	int capacity; //栈的容量
}ST;

顺序栈的结构体需要包含三个关键成员：

  • 动态数组指针：用于存储栈的元素（连续内存空间）。
  • 栈顶指针（top）：记录栈顶元素的位置（通常用数组下标表示）。
  • 容量（capacity）：记录当前数组的最大可存储元素数量（避免溢出）。

栈顶指针（top）的设计细节：

  • 初始时 top = 0（栈为空，栈顶位置在数组起始处之前）。
  • 入栈时：先将元素存入 arr[top]，再执行 top++（栈顶后移）。
  • 出栈时：先执行 top--，再逻辑删除栈顶元素（无需真正清除数据）。

二.栈的初始化

void StackInit(Stack* ps) {
    assert(ps != NULL);  // 确保传入的栈指针有效
    ps->arr = NULL;      // 初始无内存分配
    ps->top = 0;         // 栈顶起始位置为0（空栈）
    ps->capacity = 0;    // 初始容量为0
}

三.关于栈的操作

1. 初始化栈（StackInit）

初始化时需将数组指针置空，栈顶和容量设为 0，确保栈处于 “空状态”。

void StackInit(Stack* ps) {
    assert(ps != NULL);  // 确保传入的栈指针有效
    ps->arr = NULL;      // 初始无内存分配
    ps->top = 0;         // 栈顶起始位置为0（空栈）
    ps->capacity = 0;    // 初始容量为0
}
2. 检查容量并扩容（StackCheckCapacity）

入栈前需检查当前元素数量（top）是否等于容量（capacity），若相等则需要扩容（通常扩容为原容量的 2 倍，初始容量设为 4）。

void StackCheckCapacity(Stack* ps) {
    assert(ps != NULL);
    // 若栈满（元素数 == 容量），则扩容
    if (ps->top == ps->capacity) {
        // 扩容策略：初始容量为4，之后每次翻倍
        int newCapacity = (ps->capacity == 0) ? 4 : ps->capacity * 2;
        // 重新分配内存（realloc支持NULL指针，首次分配等价于malloc）
        STDataType* newArr = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
        if (newArr == NULL) {
            perror("realloc fail");  // 内存分配失败时报错
            exit(1);                 // 退出程序
        }
        ps->arr = newArr;            // 更新数组指针
        ps->capacity = newCapacity;  // 更新容量
    }
}

扩容逻辑的优势：

  • 采用 “翻倍扩容” 可减少扩容次数，平均时间复杂度接近 O (1)（ amortized O (1)）。
3. 入栈（StackPush）

在栈顶添加元素，步骤：先检查容量（不足则扩容），再将元素存入栈顶位置，最后移动栈顶指针。

void StackPush(Stack* ps, STDataType x) {
    assert(ps != NULL);
    StackCheckCapacity(ps);  // 确保有足够空间
    ps->arr[ps->top] = x;    // 将元素存入栈顶
    ps->top++;               // 栈顶指针后移（指向新的栈顶位置）
}
4. 出栈（StackPop）

删除栈顶元素，步骤：先检查栈是否为空（空栈不能出栈），再移动栈顶指针（逻辑删除）。

void StackPop(Stack* ps) {
    assert(ps != NULL);
    assert(!StackEmpty(ps));  // 确保栈非空（StackEmpty实现见下文）
    ps->top--;                // 栈顶指针前移，逻辑删除栈顶元素
}

注意：顺序栈的出栈是 “逻辑删除”，不会真正清除内存中的数据，仅通过top指针标记有效元素范围，效率极高（O (1)）。

5. 取栈顶元素（StackTop）

返回栈顶元素的值（不删除），需先确保栈非空。

STDataType StackTop(Stack* ps) {
    assert(ps != NULL);
    assert(!StackEmpty(ps));  // 确保栈非空
    return ps->arr[ps->top - 1];  // top指向栈顶下一个位置，故-1取栈顶
}
6. 判空（StackEmpty）

判断栈是否为空（top == 0 时为空）。

bool StackEmpty(Stack* ps) {
    assert(ps != NULL);
    return ps->top == 0;  // top为0表示无元素
}
7. 销毁栈（StackDestroy）

释放动态数组的内存，重置栈的状态，避免内存泄漏。

void StackDestroy(Stack* ps) {
    assert(ps != NULL);
    free(ps->arr);    // 释放动态数组内存
    ps->arr = NULL;   // 指针置空，避免野指针
    ps->top = 0;      // 重置栈顶
    ps->capacity = 0; // 重置容量
}

四. 操作示例

int main() {
    Stack st;
    StackInit(&st);       // 初始化栈

    // 入栈：1 → 2 → 3（栈顶为3）
    StackPush(&st, 1);
    StackPush(&st, 2);
    StackPush(&st, 3);

    // 取栈顶并出栈（3 → 2 → 1）
    while (!StackEmpty(&st)) {
        printf("Top: %d\n", StackTop(&st));  // 输出3、2、1
        StackPop(&st);
    }

    StackDestroy(&st);    // 销毁栈
    return 0;
}

总结

用数组实现的栈是一种高效、紧凑的选择，适合元素数量相对稳定、对性能要求高的场景（如函数调用栈、表达式求值）。其核心是通过动态数组和栈顶指针管理元素，严格保证 “后进先出” 的特性，同时通过合理的扩容策略平衡效率与空间开销。

五. 完整代码如下(自行取用)

#define _CRT_SECURE_NO_WARNINGS 
#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>
// 定义栈中元素的数据类型（可根据需求修改，如int、char等）
typedef int STDataType;

// 顺序栈的结构体
typedef struct Stack {
    STDataType* arr;   // 动态数组指针，指向栈的存储空间
    int top;           // 栈顶指针：指向栈顶元素的下一个位置（初始为0）
    int capacity;      // 栈的容量：当前数组可容纳的最大元素数
} Stack;
void StackInit(Stack* ps) {
    assert(ps != NULL);  // 确保传入的栈指针有效
    ps->arr = NULL;      // 初始无内存分配
    ps->top = 0;         // 栈顶起始位置为0（空栈）
    ps->capacity = 0;    // 初始容量为0
}
void StackCheckCapacity(Stack* ps) {
    assert(ps != NULL);
    // 若栈满（元素数 == 容量），则扩容
    if (ps->top == ps->capacity) {
        // 扩容策略：初始容量为4，之后每次翻倍
        int newCapacity = (ps->capacity == 0) ? 4 : ps->capacity * 2;
        // 重新分配内存（realloc支持NULL指针，首次分配等价于malloc）
        STDataType* newArr = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
        if (newArr == NULL) {
            perror("realloc fail");  // 内存分配失败时报错
            exit(1);                 // 退出程序
        }
        ps->arr = newArr;            // 更新数组指针
        ps->capacity = newCapacity;  // 更新容量
    }
}
void StackPush(Stack* ps, STDataType x) {
    assert(ps != NULL);
    StackCheckCapacity(ps);  // 确保有足够空间
    ps->arr[ps->top] = x;    // 将元素存入栈顶
    ps->top++;               // 栈顶指针后移（指向新的栈顶位置）
}
bool StackEmpty(Stack* ps) {
    assert(ps != NULL);
    return ps->top == 0;  // top为0表示无元素
}
void StackPop(Stack* ps) {
    assert(ps != NULL);
    assert(!StackEmpty(ps));  // 确保栈非空（StackEmpty实现见下文）
    ps->top--;                // 栈顶指针前移，逻辑删除栈顶元素
}


void StackDestroy(Stack* ps) {
    assert(ps != NULL);
    free(ps->arr);    // 释放动态数组内存
    ps->arr = NULL;   // 指针置空，避免野指针
    ps->top = 0;      // 重置栈顶
    ps->capacity = 0; // 重置容量
}
STDataType StackTop(Stack* ps) {
    assert(ps != NULL);
    assert(!StackEmpty(ps));  // 确保栈非空
    return ps->arr[ps->top - 1];  // top指向栈顶下一个位置，故-1取栈顶
}
int main() {
    Stack st;
    StackInit(&st);       // 初始化栈

    // 入栈：1 → 2 → 3（栈顶为3）
    StackPush(&st, 1);
    StackPush(&st, 2);
    StackPush(&st, 3);

    // 取栈顶并出栈（3 → 2 → 1）
    while (!StackEmpty(&st)) {
        printf("Top: %d\n", StackTop(&st));  // 输出3、2、1
        StackPop(&st);
    }

    StackDestroy(&st);    // 销毁栈
    return 0;
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布