C++中如何实现队列数据结构 |21xrx.com

C++中如何实现队列数据结构

2023-06-23 13:33:17 深夜i 12 0

C++ 队列数据结构实现

队列是一种常用的数据结构，在C++中也有多种实现方法。本文将介绍C++中如何实现队列数据结构。

一、队列介绍

队列是一种先进先出（FIFO）的数据结构，类似于排队的过程。在队列中，新元素从队尾进入，旧元素从队头弹出。队列通常有两种操作，分别为入队（Enqueue）和出队（Dequeue），可以用一个数组或链表来实现。

二、基于数组的队列实现

以下是一个基于数组的队列实现示例：

#include <iostream>
using namespace std;
class Queue{
private:
  int front, rear, size;
  int* arr;
public:
  Queue(int size){
    this->size = size;
    front = -1;
    rear = -1;
    arr = new int[size];
  }
  void Enqueue(int x){
    if(rear == size-1)
      cout << "Queue is full" << endl;
      return;
    
    arr[++rear] = x;
    if(front==-1) front++;
  }
  void Dequeue(){
    if(front == -1 || front > rear)
      cout << "Queue is empty" << endl;
      return;
    
    front++;
  }
  void display(){
    if(front == -1 || front > rear)
      cout << "Queue is empty" << endl;
      return;
    
    for(int i=front; i<=rear; i++)
      cout << arr[i] << " ";
    cout << endl;
  }
};
int main(){
  Queue q(5);
  
  q.Dequeue();
  q.Enqueue(1);
  q.Enqueue(2);
  q.Enqueue(3);
  q.display();
  q.Dequeue();
  q.display();
  q.Enqueue(4);
  q.Enqueue(5);
  q.Enqueue(6);
  q.display();
  return 0;
}

以上代码中，我们用数组arr来存储队列元素，front指向队头，rear指向队尾，size为队列最大容量。入队操作Enqueue将元素插入到队尾，如果队列已满则输出"Queue is full"。出队操作Dequeue将队头元素移除，如果队列为空则输出"Queue is empty"。display方法用于展示当前队列的元素。

三、基于链表的队列实现

基于链表的队列实现示例如下：

#include <iostream>
using namespace std;
class Node{
public:
  int data;
  Node* next;
};
class Queue{
private:
  Node* front;
  Node* rear;
public:
  Queue()
    front = NULL;
    rear = NULL;
  
  void Enqueue(int x){
    Node* temp = new Node();
    temp->data = x;
    temp->next = NULL;
    if(front == NULL && rear == NULL)
      front = rear = temp;
      return;
    
    rear->next = temp;
    rear = temp;
  }
  void Dequeue(){
    Node* temp = front;
    if(front == NULL)
      cout << "Queue is empty" << endl;
      return;
    
    if(front == rear)
      front = rear = NULL;
    
    else
      front = front->next;
    
    delete temp;
  }
  void display(){
    if(front == NULL)
      cout << "Queue is empty" << endl;
      return;
    
    Node* temp = front;
    while(temp != NULL)
      cout << temp->data << " ";
      temp = temp->next;
    
    cout << endl;
  }
};
int main(){
  Queue q;
  q.Dequeue();
  q.Enqueue(1);
  q.Enqueue(2);
  q.Enqueue(3);
  q.display();
  q.Dequeue();
  q.display();
  q.Enqueue(4);
  q.Enqueue(5);
  q.Enqueue(6);
  q.display();
  return 0;
}

以上代码中，我们用链表来存储队列元素。入队操作Enqueue将一个新节点插入到链表尾部，而出队操作Dequeue则移除链表头的节点。如果队列为空则输出"Queue is empty"。display方法用于展示当前队列的元素。

总结

通过以上两种方法，我们可以在C++中实现队列数据结构。基于数组的实现方法更简单，但队列大小固定，而基于链表的实现方法则可以动态地扩展队列大小。具体选择哪种方法需要根据实际需要来判断。

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

下一篇: C++中的min头文件

评论区

相似文章