循环队列和链队列的时间复杂度

循环队列和链队列都是队列的实现方式，它们的时间复杂度如下：

循环队列：
- 入队操作的时间复杂度为O(1)；
- 出队操作的时间复杂度为O(1)；
- 获取队头元素的时间复杂度为O(1)；
- 获取队列长度的时间复杂度为O(1)。

链队列：
- 入队操作的时间复杂度为O(1)；
- 出队操作的时间复杂度为O(1)；
- 获取队头元素的时间复杂度为O(1)；
- 获取队列长度的时间复杂度为O(1)。

因此，两种队列的时间复杂度都比较优秀，都能够满足一般情况下的需求。但在某些特殊情况下，比如需要经常进行插入或删除操作时，链队列可能会更适合一些。而对于需要经常进行获取队头元素或者获取队列长度的操作，循环队列则会更加高效。

相关问题

循环队列进队出队的时间复杂度

循环队列的进队和出队的时间复杂度均为O(1)级别，即常数时间。这是因为循环队列通过维护队首front和队尾tail索引，实现了在队列头尾的快速操作。当出队时，只需要将队首索引front向后移动一位即可，无需移动数据位置；当入队时，只需要将队尾索引tail向后移动一位即可，如果到达数组底部，则通过取余回到数组前端。因此，循环队列的性能比普通队列更高。

举个例子，假设循环队列的长度为n，当前队列中有m个元素，队首索引为front，队尾索引为tail，则进队和出队的时间复杂度均为O(1)级别，即常数时间。

进队操作的时间复杂度为O(1)：
- 如果队列已满，需要扩容，时间复杂度为O(n)；
- 如果队列未满，只需要将元素插入到队尾，将tail向后移动一位即可，时间复杂度为O(1)。

出队操作的时间复杂度为O(1)：
- 如果队列为空，无法出队，时间复杂度为O(1)；
- 如果队列非空，只需要将队首元素弹出，将front向后移动一位即可，时间复杂度为O(1)。

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

循环顺序队列头文件：

#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