c++ - 使用 Stack 类实现 List 类

Question

我正在尝试编写像 Python 这样的解释型编程语言，因此我需要一个 List 类来存储函数和变量的“地址”。我实现了用于实现 List 类的 Stack 类:

typedef unsigned int UIntegerP; //This type for storing addresses
#define Free 0x0

template <typename T> class Stack{ 
    public:
        unsigned long UsedBSize; // You can use that like End Of Stack (EOS)

        Stack(void){
            this->BSize = 0; this->UsedBSize = 0;
            this->Buffer = new T;           
        }
        ~Stack(void){
            delete this->Buffer;
        }

        inline void Push(T Variable){ 
            if(this->UsedBSize == this->BSize){ 
                this->BSize++; 
            } this->Buffer[this->UsedBSize] = Variable; this->UsedBSize++;
        }    
        inline T Pop(bool IsProtected = false){ 
            if(IsProtected){
                return this->Buffer[this->UsedBSize]; 
            }else{
                this->UsedBSize--; T Element = this->Buffer[this->UsedBSize]; this->Buffer[this->UsedBSize] = Free; 
                return Element;
            }   
        }   
    private:
        T *Buffer;
        unsigned long BSize; 

};

这是我要实现的类:

class List{
    private:
        Stack<UIntegerP> *stack = new Stack<UIntegerP>; //A stack for storing variable addresses

    public:
        ~List(void){
            delete this->stack;
        }

        List(Stack<UIntegerP> Elements){ 
            while(Elements.UsedBSize != 0){
                this->stack->Push(Elements.Pop());
            }
        }

        List(Stack<UIntegerP> *Elements){
           while(Elements->UsedBSize != 0){
               this->stack->Push(Elements->Pop());
           }
        }

        UIntegerP Get(unsigned long Size); //Get Address with Index number
        UIntegerP Set(unsigned long Size, UIntegerP Address); //Set Address with Index number
};

我将使用这个 List 类来实现类似 Python 的字典。变量类需要 UIntegerP 类型。我如何实现这两个功能？

Answer 1

假设您的堆栈仅公开了 Push 和 Pop 函数，那么您将无法有效地实现在其之上建立索引的列表。

如果您使用普通的 C++ 风格进行编程，那么基本数据结构将是 dynamic array或 linked list .然后，您可以在这些之上构建一个堆栈。但请注意，链表中的索引会很慢(线性时间复杂度)。

如果您以函数式风格编程，那么基本结构是“列表”，它是一个不可变的单向链表，实际上与不可变堆栈相同。但同样，用它编制索引会很慢。

---

另请注意，您的 Stack 实现不正确:您正在为单个 T 分配内存，但随后您假设可以将其用于无限数量的 Ts。您要么需要走链表路线:为每个项目分配一个新节点并用指针连接节点；或者你需要走动态数组路线:分配一个特定大小的数组，当它变得太小时，重新分配它。