新数据结构

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