当前位置：首页 > 其他 > 手搓顺序表实现栈代码详解及新手教程——从原理到实现的完整指南

手搓顺序表实现栈代码详解及新手教程——从原理到实现的完整指南

3个月前 (07-06)

一、简介和特点

顺序栈是一种基于数组实现的后进先出（LIFO）数据结构。通过动态数组管理存储空间，它具备以下特点：

1. 数组存储：数据连续存储，支持随机访问，访问效率高。

2. 动态扩容：当栈满时自动扩展容量（本实现采用翻倍扩容），避免溢出。

3. 操作简单：通过栈顶指针 top 管理元素入栈、出栈，逻辑清晰。

二、与其他相比的优点

相比链式栈：无需额外指针存储节点关系，内存利用率更高。

相比静态数组栈：动态扩容机制解决了固定容量限制，更灵活。

新手友好：代码简洁，核心逻辑集中在 add()、del()、select() 三个方法，易于理解。

三、实现步骤

1. 构造栈：传入参数 newsize 初始化容量，分配 new int[newsize] 创建数组。

2. 元素入栈：

检查 top + 1 == size 是否栈满；

若满，创建两倍容量新数组，复制原数据并释放旧空间；

将元素存入 stack[top++]，更新 top。

3. 删除元素：仅将 top 减1，不实际删除数据（节省开销）。

4. 获取栈顶：直接返回 stack[top - 1]，不修改栈状态。

四、代码及注释

#include <iostream>
using namespace std;

// 定义 Stack 类
class Stack {
private:
    int top;         // 栈顶指针，存储当前栈顶元素的下标（初始化为0）
    int* stack;      // 指向栈的指针，动态分配数组存储数据
    int size = 0;    // 栈的当前容量（初始为空，由构造函数传入）

public:
    // 构造函数：初始化栈的容量
    Stack(int newsize) {
        top = 0;          // 栈顶初始化为0（空栈）
        size = newsize;   // 设置栈的初始容量
        stack = new int[newsize];  // 动态分配内存，创建数组
    }

    // 添加元素到栈顶
    void add(int data) {
        // 检查栈是否已满（top+1 == size 表示下一个位置超出容量）
        if (top + 1 == size) {
            // 栈满时扩容：创建两倍容量的新数组
            int* tmp = new int[size * 2];
            // 将原数组元素复制到新数组
            for (int i = 0; i < size; i++) {
                tmp[i] = stack[i];
            }
            // 释放原数组内存
            delete[] stack;
            // 更新栈指针和容量
            stack = tmp;
            size *= 2;
        }
        // 将元素添加到栈顶（top指向的位置），并更新栈顶指针
        stack[top++] = data;
    }

    // 删除栈顶元素（不移除数据，仅调整top指针）
    void del() {
        top = max(0, top - 1);  // 防止top减到负数，确保至少为0
    }

    // 获取栈顶元素（不删除）
    int select() {
        return stack[top - 1];  // 返回当前栈顶元素
    }
};