Stack（データ構造）の実装

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

はい、これはスタックを実装する方法の1つです。スタックを定義する重要なことは、LIFO（最後入れ先出し）です。あなたがトップに追加したり、トップから削除したりする限り、それはスタックです。それを料理の積み重ねと考えてください。もし10枚の皿が一つずつ積み重ねられ、次いで前記積み重ねから一つずつ取り除かれれば、最初に置かれた皿は最後に取り除かれた皿になる。上のすべての料理で覆われているので、上にない料理は取り除くことができません。同じことがスタックデータ構造にも当てはまります。

あなたの実装は確かにスタックです。