循环顺序队列

循环顺序队列是一种基于数组实现的队列。与普通队列相比，它可以更高效地利用数组空间。

循环顺序队列的实现思路是将数组看成一个环形结构，队列的头和尾在数组中可以相互追溯。当队列满时，只需将队列尾指针指向数组头部重新开始存储数据。

具体实现中，需要使用队列头指针(front)和队列尾指针(rear)来标记队列的头和尾。队列为空时，front 和 rear 均指向数组第一个元素的前一个位置；队列满时，rear 指向队列尾元素，front 指向队列头元素的下一个位置。

循环顺序队列的主要操作包括入队、出队、判空、判满等。入队操作时，需要判断队列是否已满；出队操作时，需要判断队列是否为空。循环顺序队列的时间复杂度为 O(1)。

以下是循环顺序队列的示意图：

   +---+---+---+---+---+---+---+---+
   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+
         ^               ^
       front           rear

相关问题

编写循环顺序队列和链队列头文件

循环顺序队列头文件：

#ifndef CIRCULAR_QUEUE_H
#define CIRCULAR_QUEUE_H

#define MAX_QUEUE_SIZE 100

typedef struct {
    int data[MAX_QUEUE_SIZE];
    int front;  // 队头指针
    int rear;   // 队尾指针
} CircularQueue;

void init_queue(CircularQueue *queue);
int is_empty(CircularQueue *queue);
int is_full(CircularQueue *queue);
int enqueue(CircularQueue *queue, int value);
int dequeue(CircularQueue *queue);
int get_front(CircularQueue *queue);
int get_rear(CircularQueue *queue);

#endif

链队列头文件：

#ifndef LINKED_QUEUE_H
#define LINKED_QUEUE_H

typedef struct node {
    int data;
    struct node *next;
} QueueNode;

typedef struct {
    QueueNode *front;   // 队头指针
    QueueNode *rear;    // 队尾指针
} LinkedQueue;

void init_queue(LinkedQueue *queue);
int is_empty(LinkedQueue *queue);
int enqueue(LinkedQueue *queue, int value);
int dequeue(LinkedQueue *queue);
int get_front(LinkedQueue *queue);
int get_rear(LinkedQueue *queue);

#endif

写循环顺序队列和链队列头文件

循环顺序队列头文件：

#ifndef CIRCULAR_QUEUE_H
#define CIRCULAR_QUEUE_H

#include <iostream>

template <class T>
class CircularQueue {
private:
    T *data;  // 存储队列元素的数组
    int front;  // 队首指针
    int rear;  // 队尾指针
    int maxSize;  // 队列最大容量

public:
    // 构造函数
    CircularQueue(int size = 10) {
        maxSize = size + 1;  // 队列中预留一个位置不用，所以要加1
        data = new T[maxSize];  // 创建存储队列元素的数组
        front = rear = 0;  // 队首和队尾指针初始化为0
    }

    // 析构函数
    ~CircularQueue() {
        delete[] data;  // 释放存储队列元素的数组所占空间
    }

    // 判断队列是否为空
    bool isEmpty() const {
        return front == rear;
    }

    // 判断队列是否已满
    bool isFull() const {
        return (rear + 1) % maxSize == front;
    }

    // 获取队列中元素个数
    int getSize() const {
        return (rear - front + maxSize) % maxSize;
    }

    // 入队
    bool enqueue(const T &elem) {
        if (isFull()) {  // 队列已满，无法入队
            return false;
        } else {
            data[rear] = elem;  // 将元素放入队尾指向的位置
            rear = (rear + 1) % maxSize;  // 队尾指针后移一位
            return true;
        }
    }

    // 出队
    bool dequeue() {
        if (isEmpty()) {  // 队列为空，无法出队
            return false;
        } else {
            front = (front + 1) % maxSize;  // 队首指针后移一位
            return true;
        }
    }

    // 获取队首元素
    bool getFront(T &elem) const {
        if (isEmpty()) {  // 队列为空
            return false;
        } else {
            elem = data[front];  // 获取队首元素
            return true;
        }
    }
};

#endif  // CIRCULAR_QUEUE_H

链队列头文件：

#ifndef LINKED_QUEUE_H
#define LINKED_QUEUE_H

#include <iostream>

template <class T>
struct Node {
    T data;  // 存储数据元素
    Node<T> *next;  // 指向下一个结点的指针
};

template <class T>
class LinkedQueue {
private:
    Node<T> *front;  // 队首指针
    Node<T> *rear;  // 队尾指针

public:
    // 构造函数
    LinkedQueue() {
        front = rear = nullptr;  // 初始时队首和队尾指针均为空
    }

    // 析构函数
    ~LinkedQueue() {
        Node<T> *p;
        while (front != nullptr) {  // 释放队列中所有结点所占空间
            p = front;
            front = front->next;
            delete p;
        }
    }

    // 判断队列是否为空
    bool isEmpty() const {
        return front == nullptr;
    }

    // 入队
    void enqueue(const T &elem) {
        Node<T> *p = new Node<T>;
        p->data = elem;
        p->next = nullptr;
        if (isEmpty()) {  // 队列为空，插入的结点既是队首又是队尾
            front = rear = p;
        } else {  // 队列不为空，在队尾插入结点
            rear->next = p;
            rear = p;
        }
    }

    // 出队
    bool dequeue() {
        if (isEmpty()) {  // 队列为空
            return false;
        } else {
            Node<T> *p = front;
            front = front->next;
            if (front == nullptr) {  // 队列只有一个元素，出队后队列为空
                rear = nullptr;
            }
            delete p;
            return true;
        }
    }

    // 获取队首元素
    bool getFront(T &elem) const {
        if (isEmpty()) {  // 队列为空
            return false;
        } else {
            elem = front->data;
            return true;
        }
    }
};

#endif  // LINKED_QUEUE_H