顺序栈Stack——数据结构系列教程(c++版)

#ifndef ENTITYS_H_INCLUDED
#define ENTITYS_H_INCLUDED

//************************************************************************************************************************************************************************
//                                                                      自定义类型
//************************************************************************************************************************************************************************

//========================================================================================================================================================================
//                                                                    学生结构体(Student)
//========================================================================================================================================================================
struct Student {
    int id;// 学号
    std::string name;// 姓名
    std::string dob;// 出生日期
    std::string sex;// 性别
    std::string gender;// 民族
    std::string address;// 地址
    float score;// 入学总分
    std::string school;// 学校
    std::string team;// 班级
    std::string status;// 状态

    bool operator<(const Student& other) const { return id < other.id; }
    bool operator>(const Student& other) const { return id > other.id; }
    bool operator==(const Student& other) const { return id == other.id; }
    bool operator!=(const Student& other) const { return id != other.id; }

    friend std::ostream& operator<<(std::ostream& os, const Student& s) {
        os << "[" << s.id<< ", " << s.name << ", " << s.dob << ", " << s.sex << ", " << s.gender  << ", " << s.address << ", " << s.score<< ", " << s.school<< ", " << s.team<< ", " << s.status << "]";
        return os;
    }
};

//========================================================================================================================================================================
//
//                                                                    学生索引结构体(Student)
//
//========================================================================================================================================================================
struct StudentIndex {
    int id;// 学号
    int row;// 行号

    bool operator<(const StudentIndex& other) const { return id < other.id; }
    bool operator>(const StudentIndex& other) const { return id > other.id; }
    bool operator==(const StudentIndex& other) const { return id == other.id; }
    bool operator!=(const StudentIndex& other) const { return id != other.id; }

    friend std::ostream& operator<<(std::ostream& os, const StudentIndex& i) {
        os << "[" << i.id << ", " << i.row<< "]";
        return os;
    }
};

//========================================================================================================================================================================
//                                                                    迷宫坐标结构体(Pos)
//========================================================================================================================================================================
struct Pos{
    int x;     //x坐标
    int y;    //y坐标
    int step; //步数
};

//========================================================================================================================================================================
//                                                                    打印任务结构体(PrintTask)
//========================================================================================================================================================================
struct PrintTask{
    int taskId;     // 任务ID
    char content[50]; // 打印内容
};

#endif // ENTITYS_H_INCLUDED
        

5.2 ArrayStack.h 头文件

#ifndef ARRAYSTACK_H_INCLUDED
#define ARRAYSTACK_H_INCLUDED

#include "Entitys.h"

//************************************************************************************************************************************************************************
//
//      类名：数组栈(ArrayStack)
//
//      概述：一个可复用的数组栈，存储结构采用数组实现，支持任意类型数据（模板泛型）。
//
//      说明：默认栈的最大容量为100，入栈出栈时间复杂度为O(1)
//
//************************************************************************************************************************************************************************

#define MAXSIZE 100  // 栈的最大容量

//========================================================================================================================================================================
//
//                                                                 数组栈结构体(ArrayStack)
//
//========================================================================================================================================================================
template <typename T>
struct ArrayStack
{
    // ------------------------------------------------------------------------------------------------------
    //                                          私有成员
    // 注：私有成员只能在该结构体内部访问调用，外部通过该结构体定义(实例化)的变量(对象)不能访问调用）
    //------------------------------------------------------------------------------------------------------
    private:

        //---------------声明私有成员变量---------------

        T data[MAXSIZE];     // 存储数据，支持任意类型
        int top;            // 栈顶指针，初始为-1表示空栈

        //---------------声明私有成员函数---------------


    // ------------------------------------------------------------------------------------------------------
    //                                          公共成员
    // 注：公共成员能在该结构体内部访问调用，外部通过该结构体定义(实例化)的变量(对象)也能访问调用）
    //------------------------------------------------------------------------------------------------------
    public:

        //---------------声明公共成员函数---------------

        // 构造函数：外部通过该结构体定义(实例化)变量(对象)时，自动执行该函数(主要用于初始化成员变量的值)
        ArrayStack() {
            top = -1;
        }

        int isEmpty();                  // 判断栈是否为空
        int isFull();                   // 栈是否已满
        void push(const T& value);      // 入栈操作
        T pop();                        // 出栈操作（返回栈顶元素）
        T getTop();                     // 获取栈顶元素（不弹出）
        void print();                   // 打印栈数据（从栈底到栈顶，不修改top指针）

        // 析构函数：自动销毁栈，避免内存泄漏
        ~ArrayStack() {
        }
};

#endif // ARRAYSTACK_H_INCLUDED
                
                
                

5.3 ArrayStack.cpp 程序代码

#include <iostream>
#include"ArrayStack.h"

//**********************实现公有成员函数**********************

// 判断栈是否为空函数
template <typename T>
int ArrayStack<T>::isEmpty() {
    return top == -1;
}

// 判断栈是否已满函数
template <typename T>
int ArrayStack<T>::isFull() {
    return top == MAXSIZE - 1;
}

// 入栈操作函数
template <typename T>
void ArrayStack<T>::push(const T& value) {
    if (isFull()) {
        printf("栈溢出！\n");
    }
    data[++top] = value;
}

// 出栈操作函数（返回栈顶元素）
template <typename T>
T ArrayStack<T>::pop() {
    if (isEmpty()) {
        printf("栈为空！\n");
        return T();
    }
    return data[top--];
}

// 获取栈顶元素函数（不弹出）
template <typename T>
T ArrayStack<T>::getTop() {
    if (isEmpty()) {
        return T();
    }
    return data[top];
}

// 打印栈数据（从栈底到栈顶，不修改top指针）
template <typename T>
void ArrayStack<T>::print() {
    if (isEmpty()) {
        printf("栈为空，无元素可遍历！\n");
        return;
    }

    // 方式1：从栈底（索引0）到栈顶（索引top）遍历（符合栈的"先进先出"遍历逻辑）
    printf("栈元素（栈底 → 栈顶）：");
    for (int i = 0; i <= top; i++) {
        printf("%d ", data[i]);
    }
    printf("\n");

    // 可选：方式2 - 从栈顶到栈底遍历（按需选择）
    // printf("栈元素（栈顶 → 栈底）：");
    // for (int i = top; i >= 0; i--) {
    //     printf("%d ", data[i]);
    // }
    // printf("\n");

    // 可选：打印栈状态（便于调试，不修改指针）
    printf("栈状态：栈顶指针=%d，元素个数=%d\n", top, top + 1);
}                   

// 显式实例化常用类型（避免链接错误，可选）
template class ArrayStack<int>;
template class ArrayStack<char>;
template class ArrayStack<float>;
template class ArrayStack<std::string>;
template class ArrayStack<Student>; // 新增：显式实例化Student类型
template class ArrayStack<Pos>; // 新增：显式实例化Pos类型
template class ArrayStack<PrintTask>; // 新增：显式实例化PrintTask类型

5.4 main.cpp 测试代码

#include "ArrayStack.h"
#include <iostream>
#include <string>

int main() {
    ArrayStack<int> stacks;

    // 1. 入栈测试
    printf("\n=== 入栈测试 ===\n");
    stacks.push(1);
    stacks.push(2);
    stacks.push(3);
    stacks.push(4);
    stacks.push(5);
    printf("入栈1、2、3、4、5后：\n");
    stacks.print();

    // 2. 出队测试
    printf("\n=== 出栈测试 ===\n");
    printf("出栈3次：");
    printf("%d ",stacks.pop());
    printf("%d ",stacks.pop());
    printf("%d \n",stacks.pop());
    printf("出栈后");
    stacks.print();
    
    return 0;
}

输出结果

=== 入栈测试 ===
入栈1、2、3、4、5后：
栈元素（栈底 → 栈顶）：1 2 3 4 5
栈状态：栈顶指针=4，元素个数=5

=== 出栈测试 ===
出栈3次：5 4 3
出栈后栈元素（栈底 → 栈顶）：1 2
栈状态：栈顶指针=1，元素个数=2
    

六、注意事项

七、应用场景

• 逆序处理的场景：进制转换、字符串逆序、数组逆序 → 栈天生做逆序；
• 匹配 / 成对校验的场景：括号匹配、标签匹配（HTML/XML）→ 左入栈，右出栈匹配；
• 回溯 / 反悔的场景：表达式求值、DFS 深度优先搜索、函数调用栈 → 走不通就回退（出栈）。

八、总结

• 栈是线性数据结构，核心特性是 LIFO（后进先出）；
• 核心操作是 Push（入栈）和 Pop（出栈），辅助操作是 getTop（查看栈顶）和 isEmpty（判断栈空）；
• 实现方式分为数组栈（简单高效，有容量限制）和链式栈（动态扩容，略复杂）；
• 核心应用包括括号匹配、DFS、函数调用栈、浏览器后退等，操作时间复杂度均为 O (1)。

本教程通过代码解析和实战示例，覆盖了栈的核心原理、关键操作实现和实际使用场景。栈作为基础数据结构，掌握栈的实现，是深入学习更复杂数据结构的重要基础。