新數據結構

Question

最近我覺得，隨着基本的數據結構，如棧和隊列，一個新的數據結構應該只存儲最後n個給定的值。

我給它起了名字TUBE。

這將有三個基本操作 -

top() // returns the element on the top 

void push(element) // push element into the tube 

void pop() //deletes the top element in the tube 

For example if i have created a tube of size 4 

initial - [] 

push(2) - [2] 

push(3) - [3,2] 

push(4) - [4,3,2] 

push(5) - [5,4,3,2] 

push(6) - [6,5,4,3] 

push(7) - [7,6,5,4] 

push(8) - [8,7,6,5] 

pop - [7,6,5] 

pop - [6,5] 

我覺得這可能是非常有用的，在做的過程中，我們需要記住一些我們所訪問的前一個元素。

template<class T> 
class tube 
{ 
    T *val; 
    int size; 
    int front,rear; 
public: 
    tube(int k) 
    { 
     val=new T[k]; 
     size=k; 
     front=rear=-1; 
    } 

    T top() 
    { 
     if (front!=-1) 
       return val[front]; 
     else 
      return NULL; 
    } 

    void push(T k) 
    { 
     front=(front+1)%size; 

     if (rear==-1) 
      rear=0; 

     else if (front == rear) 
      rear=(rear+1)%size; 

     val[front]=k; 
    } 

    void pop() 
    { 
     if (front == -1) 
      abort(); 
     else if (front == rear) 
      front=rear=-1; 
     else 
     { 
      front--; 
      if (front<0) 
       front=size-1; 
     } 
    } 
}; 

請分享您對這方面的看法，並提出改進建議，將不勝感激。

Answer 1

1. 實現使用std :: deque，而不是原始指針。因爲它是你的代碼泄漏。

2. top（）不會編譯，NULL不是T型的。但是如果你測試了一些其中0可能是有效返回值的東西，它就會工作。如果top（）爲空則更好。

   template < typename T > 
   class tube 
   { 
       private: 
       std::deque<T> data; 
       size_t capacity; 
   
       public: 
       explicit tube(size_t cap) : capacity(cap) 
       { 
       } 
   
       T const& top() const 
       { 
         return data.front(); 
       } 
   
       void pop() 
       { 
        data.pop_front(); 
       } 
   
       void push(T const& t) 
       { 
        if(data.size() == capacity) 
        { 
         data.pop_back(); 
        } 
        data.push_front(t); 
       } 
       };