C++ Queue 代码实现 |21xrx.com

C++ Queue 代码实现

2023-06-28 11:25:58 深夜i 12 0

- C++ - Queue - 代码实现

Queue是一种线性数据结构，它遵循“先进先出”(FIFO)的原则。在 C++ 中，Queue可以通过使用stl库的queue模板类轻松地实现。但是，如果您想从头开始编写自己的Queue类，这里是您需要知道的。

一个Queue通常由两组操作组成：插入操作（enqueue）和删除操作（dequeue）。每个插入操作都在队列的尾部加入新元素，而每个删除操作都从队列的头部删除元素。此外，Queue还应该支持其他一些基本操作，例如获取队列的大小和判断队列是否为空等。

以下是一个经典的C++实现：

template<class T> 
class Queue { 
private: 
  struct Node { 
    T data; 
    Node* next; 
    Node() :next(NULL) {} 
    Node(const T& d, Node* n = NULL) :data(d), next(n) {} 
    ~Node() {} 
  }; 
   
  Node* front; 
  Node* rear; 
  int size; 
   
public: 
  Queue(); 
  ~Queue(); 
  void enqueue(const T& value); 
  void dequeue(); 
  T frontValue() const; 
  bool empty() const; 
  int getSize() const; 
}; 
template<class T> 
Queue<T>::Queue() :front(NULL), rear(NULL), size(0) {} 
template<class T> 
Queue<T>::~Queue() { 
  while (front != NULL) { 
    Node* temp = front; 
    front = front->next; 
    delete temp; 
  } 
} 
template<class T> 
void Queue<T>::enqueue(const T& value) { 
  Node* newNode = new Node(value); 
  if (front == NULL)  
    front = newNode; 
   
  else  
    rear->next = newNode; 
   
  rear = newNode; 
  size++; 
} 
template<class T> 
void Queue<T>::dequeue() { 
  if (empty()) { 
    throw runtime_error("Queue is empty."); 
  } 
  Node* temp = front; 
  front = front->next; 
  delete temp; 
  size--; 
} 
template<class T> 
T Queue<T>::frontValue() const{ 
  if (empty()) { 
    throw runtime_error("Queue is empty."); 
  } 
  return front->data; 
} 
template<class T> 
bool Queue<T>::empty() const 
  return size == 0; 
 
template<class T> 
int Queue<T>::getSize() const 
  return size;

在上述代码中，我们定义了一个嵌套类型Node，它有两个数据域：数据值和指向下一个节点的指针。Queue类具有三个私有变量：指向Queue的第一个元素的指针front，指向最后一个元素的指针rear和一个整数size（代表队列的长度）。

我们在构造函数中初始化了这些变量，将它们都赋值为NULL或0。在enqueue()函数中，我们创建一个新的Node并将其添加到Queue的末尾。在dequeue()函数中，我们从队头删除元素。如果队列为空，则抛出异常。

因为Queue是一种动态数据结构，所以在销毁队列时，我们需要遍历整个Queue并释放每个元素的内存。这是在析构函数中完成的。而在getSize()函数、empty()函数和frontValue()函数中，则分别返回队列的长度、队列是否为空和队列的头部元素。

虽然Queue可以轻松地通过使用stl库的queue模板类来实现，但是自己编写Queue类无疑更有利于深入理解Queue的实现方式。通过定义自己的Queue类，您将更好地理解该数据结构，并将在创建更高效的程序时受益。

上一篇: idea打包java可执行jar包

下一篇: C++类的实现

评论区

相似文章