Stack 클래스를 사용하여 List 클래스 구현하기

Question

저는 Python과 같은 해석 언어를 작성하려고합니다. 따라서 함수와 변수의 '주소'를 저장하기위한 List 클래스가 필요합니다. 나는 List 클래스를 구현하기위한 스택 클래스를 구현하고 있습니다 :

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

내가 사전처럼 파이썬을 구현하기위한이 목록 클래스를 사용합니다. Variable 클래스에는 UIntegerP 유형이 필요합니다. 이 두 함수를 어떻게 구현할 수 있습니까?

Answer 1

스택이 Push 및 Pop 함수 만 노출한다고 가정하면 그 위에 인덱싱을 사용하여 효율적으로 목록을 구현할 수 없습니다.

일반적인 C++ 스타일로 프로그래밍하는 경우 기본 데이터 구조는 dynamic array 또는 linked list이됩니다. 그런 다음 위에 스택을 만들 수 있습니다. 그러나 연결된 목록의 인덱싱은 느려질 것입니다 (선형 시간 복잡성).

기능적 스타일로 프로그래밍하는 경우 기본 구조는 "목록"입니다.이 목록은 변경 불가능한 단일 연결 목록이며 변경 불가능한 스택과 실질적으로 동일합니다. 그러나 다시 색인을 생성하는 것은 느려질 것입니다.

---

또한 Stack 잘못 구현되어 있습니다 : 단일 T에 대한 메모리를 할당하고,하지만 당신은 당신이 T의의 수에 제한이 사용할 수 있습니다 가정합니다. 당신은 링크 된리스트 라우트를 갈 필요가 있습니다 : 각 아이템을위한 새로운 노드를 할당하고 포인터로 노드를 연결하십시오; 또는 동적 배열 경로로 이동해야합니다. 특정 크기의 배열을 할당하고 너무 작아지면 배열을 다시 할당하십시오.