本文共 2628 字，大约阅读时间需要 8 分钟。

循环队列是一种线性数据结构，基于FIFO（先进先出）原理执行操作。它通过在数组的两端分别维持索引计数器来实现。这些计数器允许插入到数组末尾并在超过末尾时环绕到数组开头，从而模拟环形的行为。

环形队列的工作原理

性能分析

• 固定长度数组：能快速访问和修改位置，适合频繁操作的场景。
• 常数复杂度：常规操作时间复杂度为 O(1)，空间复杂度较小，非常适合缓存场景。

代码实现

#include "../headers/CircleQueue.hh"
#define DEFAULT_SIZE 15
template
   
    
CircleQueue
    
     ::CircleQueue()
{
    d_front = d_rear = -1;
    d_maxsize = DEFAULT_SIZE;
    d_size = 0;
    d_arr = new T[d_maxsize];
}
template
     
      
CircleQueue
      
       ::CircleQueue(size_t size)
{
    d_front = d_rear = -1;
    d_maxsize = size;
    d_size = 0;
    d_arr = new T[size];
}
template
       
        
CircleQueue
        
         ::~CircleQueue() { delete[] d_arr; } template
         
           bool CircleQueue
          
           ::is_full() const { return (d_rear == d_maxsize - 1 && d_front == 0) || (d_rear == d_front - 1); } template
           
             bool CircleQueue
            
             ::is_empty() const { return d_front == -1 || d_rear == -1; } template
             
               void CircleQueue
              
               ::enque(const T& value) { if (is_full()) { std::cout << "环形队列已满" << std::endl; return; } else if (d_front == -1) { d_rear = d_front = 0; } else if (d_rear == d_maxsize - 1 && d_front != 0) { d_rear = 0; } else { d_rear++; } d_arr[d_rear] = value; d_size++; } template
               
                 T CircleQueue
                
                 ::deque() { if (is_empty()) { std::cout << "环形队列为空!!" << std::endl; return T(); } T data = d_arr[d_front]; if (d_front == d_rear) { d_front = -1; d_rear = -1; } else if (d_front == d_size - 1) { d_front = 0; } else { d_front++; } d_size--; return data; } template
                 
                   T CircleQueue
                  
                   ::front() const { return d_arr[d_front]; } template
                   
                     T CircleQueue
                    
                     ::rear() const { return d_arr[d_rear]; } template
                     
                       size_t CircleQueue
                      
                       ::size() const { return d_size; } template
                       
                         const T* CircleQueue
                        
                         ::buffer() { return d_arr; } template
                         
                           std::ostream& operator<<(std::ostream& os, CircleQueue
                          
                           & q) { const T* buf = q.d_arr; if (q.d_front == -1) { os << "CircleQueue为空"; return os; } if (q.d_rear >= q.d_front) { for (size_t i = q.d_front; i <= q.d_rear; ++i) { os << buf[i] << ","; } } else { for (size_t i = q.d_front; i < q.d_size; ++i) { os << buf[i] << ","; } for (size_t i = 0; i <= q.d_rear; ++i) { os << buf[i] << ","; } } os << std::endl; return os; }
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

总结

综上所述，环形队列通过固定长度数组和前后索引指针实现，能够在常数时间复杂度内高效完成操作。这一设计在需要频繁随机访问和插入/移除的场景中表现优异，同时易于管理和扩展。