栈(数据结构)实现

Question

因此，通过Coursera课程，我刚刚开始学习数据结构，并且我了解到使用数组创建堆栈数据结构是可能的。我只是想知道我写的是不是堆栈应该做的事情。

#include <iostream>
using namespace std;

const int MAX_SIZE = 10000;

class Stack {
    public:
        Stack();
        ~Stack();
        void push(int n);
        void pop();
        int top();
        bool isEmpty() const;
        void print() const;
    private:
        int* array [MAX_SIZE];
        int curNum;
};

Stack::Stack() {
    curNum = 0;
}

Stack::~Stack() {
    for (int i = 0; i < curNum; ++i) 
        delete array[i];
}

void Stack::push(int n) {
    if (curNum >= MAX_SIZE) {
        cout << "reached maximum capacity...can't add an element\n";
        return;
    }
    array[curNum] = new int(n);
    curNum++;
}

void Stack::pop() {
    delete array[curNum];
    curNum--;
}

int Stack::top() {
    return *array[curNum];
}

void Stack::print() const{
    for (int i = 0; i < curNum; ++i) 
        cout << *array[i] << endl;
}

bool Stack::isEmpty() const{
    return curNum == 0;
}

int main () {
    Stack stack;
    stack.push(5);
    stack.print();
    stack.pop();
}

另外，我发现很多人并不使用动态内存分配来完成这类任务。有什么原因吗？似乎在编译时指定数组的大小可能导致内存不足或过度分配内存给我

Answer 1

是的，这是实现堆栈的一种方式。定义堆栈的重要一点是LIFO (后进先出)。所以，只要你只是在顶部添加和删除，那么这就是一个堆栈。把它想象成一堆盘子，如果把10个盘子逐个放入一叠，然后逐个从这一叠中取出，那么放在上面的第一个盘子也是最后一个取出的。你不能移除不在顶部的盘子，因为它被上面的所有盘子所覆盖。堆栈数据结构也是如此。

所以你的实现实际上是一个堆栈。

Answer 2

当我们想要颠倒顺序的东西时，我们使用的堆栈也需要恒定的时间，这意味着推送时间为O(1)，而pop意味着删除或添加它的速度会快得多