21xrx.com
2025-06-17 20:37:53 Tuesday
文章检索 我的文章 写文章
C++实现顺序队列
2023-06-29 10:22:07 深夜i     19     0
C++ 顺序队列 实现

顺序队列是一种基本的数据结构，它是基于数组实现的一种数据结构，具有先进先出的特点。在C++语言中，可以通过数组来实现顺序队列。本文将简单介绍如何使用C++来实现顺序队列。

顺序队列的基本操作有入队和出队，因此我们需要定义一个具有固定大小的数组，并定义队头和队尾指针来表示队列的状态。具体的实现代码如下：

template<typename T, int MAXSIZE>
class SeqQueue {
public:
  SeqQueue() : front(-1), rear(-1) {}
  ~SeqQueue() {}
  bool enqueue(const T& item);  // 入队
  bool dequeue();        // 出队
  bool isEmpty() const;     // 判断队列是否为空
  bool isFull() const;      // 判断队列是否已满
private:
  T data[MAXSIZE];        // 队列数组
  int front;           // 队头指针
  int rear;           // 队尾指针
};

其中，`enqueue`方法用于入队，`dequeue`方法用于出队，`isEmpty`方法用于判断队列是否为空，`isFull`方法用于判断队列是否已满。

以下是实现代码的具体内容：

template<typename T, int MAXSIZE>
bool SeqQueue<T, MAXSIZE>::enqueue(const T& item) {
  if (isFull()) 无法入队
  
  rear++; // 队尾指针向后移动
  data[rear] = item; // 将元素插入队列尾部
  return true; // 入队成功
}
template<typename T, int MAXSIZE>
bool SeqQueue<T, MAXSIZE>::dequeue() {
  if (isEmpty()) 无法出队
  
  front++; // 队头指针向后移动
  return true; // 出队成功
}
template<typename T, int MAXSIZE>
bool SeqQueue<T, MAXSIZE>::isEmpty() const
  return front == rear; // 队头指针与队尾指针相等即为空队列
template<typename T, int MAXSIZE>
bool SeqQueue<T, MAXSIZE>::isFull() const 队列已满

以上是顺序队列的基本实现，我们可以通过定义一个对象来使用它。

SeqQueue<int, 10> myQueue;
myQueue.enqueue(1); // 入队
myQueue.enqueue(2);
myQueue.dequeue(); // 出队

顺序队列的时间复杂度分析：

入队和出队的时间复杂度为O(1)，因为它们只需要对队头或队尾指针进行操作，不需要移动整个队列。因此，顺序队列是一种高效的队列实现方式。

总结：

本文介绍了如何使用C++语言实现顺序队列，其中包含了顺序队列的定义、入队、出队、判断队列是否为空以及判断队列是否已满等基本操作。顺序队列是一种非常基础的数据结构，通过本文的介绍，读者可以更好地理解顺序队列的实现思路和技术细节，从而更好地掌握数据结构的相关知识。

  
  

评论区