使用堆栈 class 实现列表 class

Question

我正在尝试编写一种类似 Python 的解释型编程语言，因此我需要一个列表 class 来存储 'address of' 函数和变量。我实现了 Stack class 来实现 List class:

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：

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
};

我将使用此列表 class 来像字典一样实现 Python。变量 class 需要 UIntegerP 类型。我如何实现这两个功能？

Answer 1

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

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

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

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

使用堆栈 class 实现列表 class

Implementing List class with using Stack class

c++

c++11

language-design