用数组实现栈

叶茂林

发布于 2024-07-06 08:23:57

760

发布于 2024-07-06 08:23:57

文章被收录于专栏：叶子的开发者社区叶子的开发者社区

栈的实现可以用链表或者数组实现

链表实现的话，push就往头节点插入，pop就删除头节点

这里用数组实现，需要三个成员变量，分别记录栈容量、栈顶索引（栈元素数量）、数组首地址

    int volume = 16;
    int top = 0;
    int *data = nullptr;

初始化

    Stack() {
        data = new int[volume];
    }

为了栈容量动态增长，写一个成长函数，将容量翻倍，即申请一块新内存，将原来元素拷贝过去，释放掉原来的空间

    void grow() {
        int *temp = new int[2 * volume];
        for (int i = 0; i < volume; ++i) {
            temp[i] = data[i];
        }
        delete[]data;
        data = temp;
        volume *= 2;
    }

push的时候直接放到栈顶位置，然后栈顶移动，判断元素是否满了，满了就增长栈容量

    void push(int value) {
        data[top] = value;
        ++top;
        if (top == volume) {
            grow();
        }
    }

如此一来top实际上是栈元素的个数

    bool empty() const {
        return top == 0;
    }

    bool size() const {
        return top;
    }

pop的时候先看看栈是不是空的，不是空的就移动栈顶，返回栈顶元素

    int pop() {
        if (empty())
            return -1;
        return data[--top];
    }

完整类

class Stack {
    int volume = 16;
    int top = 0;
    int *data = nullptr;

    void grow() {
        int *temp = new int[2 * volume];
        for (int i = 0; i < volume; ++i) {
            temp[i] = data[i];
        }
        delete[]data;
        data = temp;
        volume *= 2;
    }

public:
    Stack() {
        data = new int[volume];
    }

    void push(int value) {
        data[top] = value;
        ++top;
        if (top == volume) {
            grow();
        }
    }

    int pop() {
        if (empty())
            return -1;
        return data[--top];
    }

    bool empty() const {
        return top == 0;
    }

    bool size() const {
        return top;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-07-05，如有侵权请联系 cloudcommunity@tencent.com 删除

data