当前位置：首页 > ds >正文

编程日志4.28

ds 2025/5/8 13:40:44

队列的链表表示代码

#include<iostream>
#include<stdexcept>
using namespace std;

//队列类的声明

template<typename T>//1.模板声明，表明Queue类是一个通用的模板类，可以用于存储任何类型的元素T

class Queue {//2.Queue类的声明，表示一个队列的数据结构
private://定义成员变量私有
   struct Node {//结构体定义，用于表示队列中的结点，每个结点包含一个数据成员data和一个指向下一个结点的指针next
       T data;
       Node* next;
       Node(T d) :data(d), next(NULL) {}
   };
   Node* front;//保存队首结点指针
   Node* rear;//保存队尾结点指针
   int size;//保存队列元素个数

public://定义公共成员函数
   //8.Queue（）是构造函数，用于初始化队列。它将队首、队尾结点指针设置为NULL，并将队列的大小设置为0
   Queue() :front(NULL), rear(NULL), size(0) {}
   ~Queue();//9.析构函数，用于释放队列所占用的内存
   void enqueue(T element);//10.用于将一个新元素入队
   T dequeue();//11.用于出队
   T getFront() const;//12.用于获取队首的元素，但不弹出它
   int getSize() const;//13.用于获取队列中元素的数量
};

//队列的扩容

//由链表实现队列时，每次如果是新生成的结点，则不涉及到像顺序表那样的扩容操作

//队列的销毁

template<typename T>
Queue<T>::~Queue() {//析构函数的声明，用于在对象销毁时执行清理操作
   //不断循环访问队列中的元素，每次取出队首元素，存储到临时变量temp中，并删除队首，
   //并且利用delete将弹出的元素进行内存释放，知道队列为空为止
   while (front) {
       Node* temp = front;
       front = front->next;
       delete temp;
   }
}

//入队

template<typename T>
void Queue<T>::enqueue(T element) {
   //如果队列为空，则创建一个新的结点，并将其赋值给rear和front。这将创建一个新的队列，只有一个元素。
   if (rear == NULL) {
       rear = new Node(element);
       front = rear;
   }
   else {//否则，将新的结点插入到队列的末尾，将新结点的next指针指向当前的rear结点，然后更新rear为新结点
       rear->next = new Node(element);
       rear = rear->next;
   }
   size++;//增加队列长度
}

//出队

template<typename T>
T Queue<T>::dequeue() {
   if (front == NULL) {//栈空抛出异常
       throw std::underflow_error("Queue is empty");
   }
   T element = front->data;//将队首结点的数据成员赋值给element变量，准备返回队首的元素
   Node* temp = front;//将队首节点的指针赋值给temp变量，用于后续删除结点
   front = front->next;//将队首结点的next指针赋值给队首结点本身，从而将队首结点从链表中移除
   delete temp;//调用delete操作符释放temp所指向的节点内存
   size--;//队列大小-1
   if (size == 0)rear = NULL;//队列为空，rear指针置为NULL
   return element;//返回队首元素值element
}

//获取队首元素

template<typename T>
T Queue<T>::getFront() const {
   if (front == NULL) {//队空，操作不合法，抛出异常
       throw std::underflow_error("Queue is empty");
   }
   return front->data;//队不空，返回队首元素
}

//获取队列长度

template<typename T>
int Queue<T>::getSize() const {
return size;//队尾减去队头得队列长度
}

//主函数

int main() {
   Queue<int> q;
   q.enqueue(3);//入队3
   q.enqueue(4);
   cout << q.getFront() << endl;//队首元素为3
   q.enqueue(5);
   cout << q.getFront() << endl;//3
   q.dequeue();//移除队首元素3
   cout << q.getFront() << endl;//4
   cout << q.getSize() << endl;//2 (4,5)
   return 0;
}

查看全文

http://www.xdnf.cn/news/4737.html