C++循环链表队列的实现 |21xrx.com

C++循环链表队列的实现

2023-06-24 08:54:49 深夜i 13 0

C++ 循环链表队列实现

C++循环链表队列是一种非常基础而实用的数据结构，它能够在不同场合通过快速、高效的队列操作实现数据的输入、输出和处理。它的实现原理与普通的链表队列基本一致，不同的是在队列的队尾处，将队尾节点的next指针指向队首节点，形成一个闭环。下面我们来看看 C++循环链表队列的实现。

定义节点类

定义一个循环链表队列节点类（Node），包含了节点值（value）、指向下一个节点（next）、队列长度（count）等基本属性，头文件定义如下：

template<typename E> class CQueue; //声明循环队列
template<typename E>
class Node {
  friend class CQueue<E>;
  private:
    E value;
    Node<E>* next;
    static int count;
  public:
    Node() : next(NULL) {++count;};
    Node(const E& val) : value(val), next(NULL) {++count;};
    ~Node() {--count;};
    static int nodeCount() {return count;};
};

定义 CQueue 类

定义一个循环链表队列类（CQueue），它的节点类型为 Node ，包含私有变量 head、tail 以及公有函数 enqueue、dequeue、isEmpty、isFull 等。其中 head 指向链表队列的头节点，tail 指向链表队列的尾节点，enqueue 函数用于添加节点，dequeue 函数则是用于移除节点，isEmpty 和 isFull 函数分别判断链表队列是否为空和是否已满。头文件定义如下：

#include "node.hpp"
#include <stdexcept>
static int max_len;
template<typename E>
class CQueue {
  private:
    Node<E> *head, *tail;
  public:
    CQueue() : head(NULL), tail(NULL) {};
    CQueue(int len) : head(NULL), tail(NULL) {max_len = len;}
    ~CQueue() {};
    bool isEmpty() {return (head == NULL);}
    bool isFull() {return (Node<E>::nodeCount() == max_len);}
    void enqueue(const E& e);
    E dequeue();
};

定义 enqueue 函数

enqueue 函数是循环链表队列的核心方法，它负责将新的节点添加到队列尾部，代码实现如下：

template<typename E>
void CQueue<E>::enqueue(const E& e) {
  if (isFull()) {
    throw std::overflow_error("Queue is Full!");
  }
  Node<E>* new_node = new Node<E>(e);
  if (isEmpty())
    head = new_node;
    tail = new_node;
   else
    tail->next = new_node;
    tail = new_node;
  
  tail->next = head;
}

定义 dequeue 函数

dequeue 函数扮演着 dequeue 操作的角色，负责从循环链表队列的头部移除节点，同时保证循环链表队列的完整性，代码实现如下：


template<typename E>
E CQueue<E>::dequeue() {
  if (isEmpty()) {
    throw std::underflow_error("Queue is Empty!");
  }
  Node<E>* tmp_node = head;
  E tmp_val = tmp_node->value;
  head = head->next;
  tail->next = head;
  delete tmp_node;
  return tmp_val;
}

使用循环链表队列


CQueue<int> queue(5);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);
queue.enqueue(5);
queue.enqueue(6); //抛出了一个压栈异常
std::cout << queue.dequeue() << std::endl; //输出1
std::cout << queue.dequeue() << std::endl; //输出2
std::cout << queue.dequeue() << std::endl; //输出3
queue.enqueue(7);
std::cout << queue.dequeue() << std::endl; //输出4
std::cout << queue.dequeue() << std::endl; //输出5

使用 C++循环链表队列能够有效地将数据进行处理和存储，同时也可以在数据的输入和输出过程中大大提高数据处理效率。希望读者能够通过这篇文章了解和掌握 C++循环链表队列的实现原理，并在实际开发过程中灵活运用。

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

下一篇: 如何在C++中保留小数（除法）

评论区

相似文章