21xrx.com
2025-03-24 08:43:48 Monday
文章检索 我的文章 写文章
C++中的队列实现
2023-06-23 18:52:51 深夜i     --     --
C++ 队列 实现

队列是一种经常使用的数据结构，其遵循“先进先出”（FIFO）的原则。在C++中，可以通过模板类来实现队列。模板类允许开发者根据需要定义不同类型的数据，而无需将队列的代码进行修改。

C++ STL（标准模板库）提供了一个队列类，即std::queue。std::queue是一个适配器类，其底层实现是通过deque（双端队列）实现的。因此，std::queue的操作和deque类似。

std::queue可以通过在程序中包含 头文件来使用。以下是std::queue的一些常用操作：

1. push()：将元素在队列的末尾插入

2. pop()：移除队列的第一个元素

3. front()：返回队列的第一个元素，不会移除该元素

4. back()：返回队列的最后一个元素，不会移除该元素

5. empty()：返回队列是否为空

6. size()：返回队列中元素的数量

以下是一个示例程序，演示如何使用std::queue：

#include <iostream>
#include <queue>
using namespace std;
int main() {
  queue<int> q;
  q.push(10);
  q.push(20);
  q.push(30);
  cout << "First Element of Queue: " << q.front() << endl;
  cout << "Last Element of Queue: " << q.back() << endl;
  cout << "Size of Queue: " << q.size() << endl;
  q.pop();
  cout << "First Element of Queue after Pop: " << q.front() << endl;
  cout << "Size of Queue after Pop: " << q.size() << endl;
  return 0;
}

运行上述代码，可以得到以下输出：

First Element of Queue: 10
Last Element of Queue: 30
Size of Queue: 3
First Element of Queue after Pop: 20
Size of Queue after Pop: 2

除了std::queue，开发者还可以通过手动实现队列来理解其工作原理。以下是一个简单的手动实现队列的代码示例：

#include <iostream>
using namespace std;
#define MAX_SIZE 5
class Queue {
  private:
   int arr[MAX_SIZE];
   int front;
   int rear;
  public:
   Queue()
     front = -1;
     rear = -1;
   
   bool is_empty() {
     if (front == -1 && rear == -1)
      return true;
     else
      return false;
   }
   bool is_full() {
     if (rear == MAX_SIZE - 1)
      return true;
     else
      return false;
   }
   void enqueue(int x) {
     if (is_full())
      cout << "Queue is full";
      return;
     else if (is_empty())
      front = 0;
      rear = 0;
     else {
      rear++;
     }
     arr[rear] = x;
   }
   void dequeue() {
     if (is_empty())
      cout << "Queue is empty";
      return;
     else if (front == rear)
      front = -1;
      rear = -1;
     else {
      front++;
     }
   }
   int get_front() {
     return arr[front];
   }
   int get_rear() {
     return arr[rear];
   }
};
int main() {
  Queue q;
  q.enqueue(10);
  q.enqueue(20);
  q.enqueue(30);
  cout << "First Element of Queue: " << q.get_front() << endl;
  cout << "Last Element of Queue: " << q.get_rear() << endl;
  q.dequeue();
  cout << "First Element of Queue after Pop: " << q.get_front() << endl;
  return 0;
}

运行上述代码，可以得到以下输出：

First Element of Queue: 10
Last Element of Queue: 30
First Element of Queue after Pop: 20

通过以上示例，可以看到队列的操作步骤：

1. 入队：将元素插入队列的末尾

2. 出队：移除队列的第一个元素

3. 获取队首元素：获取队列的第一个元素

4. 获取队尾元素：获取队列的最后一个元素

队列是一种常用的数据结构，开发者可以通过C++ STL中的std::queue或手动实现队列来实现各种应用程序。

  
  

评论区