堆栈（数据结构）实现

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个盘子逐个放入堆叠中，然后从所述堆叠中逐个移除，则放置的第一个盘子也将是最后一个盘子被移除。你不能删除不在顶部的菜肴，因为它上面的所有菜肴都覆盖了它。堆栈数据结构也是如此。

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