C++实现链队列的建立 |21xrx.com

C++实现链队列的建立

2023-07-04 18:56:38 深夜i -- --

C++ 链队列实现建立

链队列是一种基于链表结构的队列实现方式，采用指针连接各个节点，具有插入和删除节点方便、占用空间灵活等优点。在C++中实现链队列需要进行以下步骤：

1. 定义链队列的结构体

首先需要定义链队列的节点结构体，包含一个元素值和指向下一个节点的指针。


struct Node{
  int data; //元素值
  Node* next; //下一个节点指针
};

然后定义链队列结构体，包含队首和队尾节点指针。


struct LinkQueue{
  Node* front; //队首节点指针
  Node* rear; //队尾节点指针
};

2. 定义链队列的基本操作

链队列的基本操作包括初始化、入队、出队、判断队列是否为空等。

初始化操作：将队首和队尾节点指针均置为空。


void Init(LinkQueue &Q)
  Q.front = Q.rear = nullptr; //队首和队尾指针均为空

入队操作：先新建一个节点，将元素值和下一个节点指针赋值，然后将新节点插入到队尾节点之后。


void EnQueue(LinkQueue &Q, int x){
  Node* newNode = new Node; //新建一个节点
  newNode->data = x; //设置元素值
  newNode->next = nullptr; //将下一个节点指针置为空
  if(Q.rear == nullptr) //如果队列为空，队首和队尾均指向新节点
    Q.front = Q.rear = newNode;
  else
    Q.rear->next = newNode; //队尾节点后插入新节点
    Q.rear = Q.rear->next; //队尾指针指向新节点
  
}

出队操作：判断队列是否为空，若非空则将队首节点删除，队首指针指向下一个节点。


bool DeQueue(LinkQueue &Q, int &x){
  if(Q.front == nullptr) //队列为空，无法出队
    return false;
  Node* p = Q.front; //保存队首节点指针
  x = p->data; //保存出队元素值
  if(Q.front == Q.rear) //队列中只有一个节点
    Q.front = Q.rear = nullptr;
  else
    Q.front = Q.front->next; //队首指针指向下一个节点
  delete p; //释放原队首节点
  return true;
}

判断队列是否为空：判断队首节点指针是否为空。


bool Empty(LinkQueue Q)
  return Q.front == nullptr;

3. 测试链队列

最后编写一个测试程序，检测链队列的基本操作是否正确。


int main() {
  LinkQueue Q;
  int x;
  Init(Q);
  for(int i=0;i<5;i++)
    EnQueue(Q, i+1);
  while(DeQueue(Q, x))
    cout<<x<<" ";
  return 0;
}

输出结果为：

1 2 3 4 5

这证明了我们的链队列实现方式是正确的。

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

下一篇: C++ 文件写入前的初始化工作

评论区

()

相似文章