数据结构入门：基于数组的栈实现详解 | 极客日志

C算法

数据结构入门：基于数组的栈实现详解

综述由AI生成栈这种先进后出的线性表结构，对比了数组与链表作为底层存储的优劣，最终选择数组实现。详细阐述了栈的定义、接口设计及核心功能，包括初始化、入栈、出栈、获取栈顶、判空及销毁操作。通过动态扩容机制解决空间限制问题，并提供了完整的 C 语言头文件、源文件及测试代码示例，帮助读者理解栈的基本原理与工程实践。

FrontendX发布于 2026/3/16更新于 2026/5/112 浏览

数据结构入门：基于数组的栈实现详解

1. 栈的概念

栈是一种特殊的线性表，只允许在固定一端插入和删除操作，进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守先进后出（LIFO, Last In First Out）的原则。

压栈：栈的插入操作叫做进栈（压栈、入栈），数据在栈顶。
出栈：栈的删除操作叫做出栈，数据也在栈顶。

2. 栈的底层结构选择

实现栈时，可以选择顺序表或链表作为底层结构。

数组实现：插入元素时在指定位置操作，删除元素时移动 top 指针。缺点是可能存在空间浪费。
链表实现：按需申请和释放空间，无空间浪费。但每次插入或删除都需要遍历链表，时间复杂度为 O(N)。

综合来看，采用数组结构实现栈更为合适，解决了动态扩容问题后效率更高。

3. 栈的实现

3.1 栈的定义

typedef int SDataType;

typedef struct Stack {
    SDataType* a;      // 栈底指针
    int capacity;      // 栈的容量大小
    int top;           // 栈实际存储数据的个数
} Stack;

3.2 栈的接口

// 初始化栈
void StackInit(Stack* ps);
// 栈顶入数据
void StackPush(Stack* ps, SDataType x);
// 获取栈顶元素
SDataType StackTop(Stack* ps);
// 删除栈顶数据
void StackPop(Stack* ps);
// 栈是否为空
bool StackEmpty(Stack* ps);
// 栈的大小
int StackSize(Stack* ps);
// 销毁栈
void ;

void StackInit(Stack* ps) {
    assert(ps);
    ps->a = NULL;
    ps->capacity = ps->top = 0;
}

void StackPush(Stack* ps, SDataType x) {
    assert(ps);
    // 增容
    if (ps->capacity == ps->top) {
        int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        SDataType* tmp = (SDataType*)realloc(ps->a, sizeof(SDataType) * newcapacity);
        if (tmp == NULL) {
            printf("StackPush(): realloc fail\n");
            exit(-1);
        }
        ps->a = tmp;
        ps->capacity = newcapacity;
    }
    ps->a[ps->top] = x;
    ps->top++;
}

bool StackEmpty(Stack* ps) {
    assert(ps);
    return ps->top == 0;
}

SDataType StackTop(Stack* ps) {
    assert(ps);
    assert(!StackEmpty(ps));
    return ps->a[ps->top - 1];
}

void StackPop(Stack* ps) {
    assert(ps);
    assert(!StackEmpty(ps));
    ps->top--;
}

int StackSize(Stack* ps) {
    assert(ps);
    return ps->top;
}

void StackDestroy(Stack* ps) {
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->capacity = ps->top = 0;
}

#pragma once
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <assert.h>

typedef int SDataType;

typedef struct Stack {
    SDataType* a;
    int capacity;
    int top;
} Stack;

void StackInit(Stack* ps);
void StackPush(Stack* ps, SDataType x);
SDataType StackTop(Stack* ps);
void StackPop(Stack* ps);
bool StackEmpty(Stack* ps);
int StackSize(Stack* ps);
void StackDestroy(Stack* ps);

#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"

void StackInit(Stack* ps) {
    assert(ps);
    ps->a = NULL;
    ps->capacity = ps->top = 0;
}

void StackPush(Stack* ps, SDataType x) {
    assert(ps);
    if (ps->capacity == ps->top) {
        int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        SDataType* tmp = (SDataType*)realloc(ps->a, sizeof(SDataType) * newcapacity);
        if (tmp == NULL) {
            printf("StackPush(): realloc fail\n");
            exit(-1);
        }
        ps->a = tmp;
        ps->capacity = newcapacity;
    }
    ps->a[ps->top] = x;
    ps->top++;
}

SDataType StackTop(Stack* ps) {
    assert(ps);
    assert(!StackEmpty(ps));
    return ps->a[ps->top - 1];
}

void StackPop(Stack* ps) {
    assert(ps);
    assert(!StackEmpty(ps));
    ps->top--;
}

bool StackEmpty(Stack* ps) {
    assert(ps);
    return ps->top == 0;
}

int StackSize(Stack* ps) {
    assert(ps);
    return ps->top;
}

void StackDestroy(Stack* ps) {
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->capacity = ps->top = 0;
}

#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"

void TestStack1() {
    Stack st;
    StackInit(&st);
    StackPush(&st, 1);
    StackPush(&st, 2);
    StackPush(&st, 3);
    StackPush(&st, 4);
    StackPush(&st, 5);
    
    SDataType ret = StackTop(&st);
    printf("%d ", ret);
    
    StackPop(&st);
    StackPop(&st);
    
    int size = StackSize(&st);
    printf("%d ", size);
    
    StackDestroy(&st);
}

int main() {
    TestStack1();
    return 0;
}