顺序队列和链队列的区别

顺序队列和链队列是两种常见的队列实现方式，它们的主要区别在于底层数据结构和操作的效率。

1. 顺序队列：
顺序队列使用数组作为底层数据结构，通过数组的连续存储空间来实现队列的操作。队列的头部和尾部分别对应数组的起始位置和末尾位置。入队操作时，将元素插入到队尾，并更新尾指针；出队操作时，将头部元素删除，并更新头指针。顺序队列的优点是随机访问元素快速，但插入和删除操作需要移动元素，效率较低。

2. 链队列：
链队列使用链表作为底层数据结构，通过节点之间的指针链接来实现队列的操作。队列的头部和尾部分别对应链表的头节点和尾节点。入队操作时，创建新节点并插入到链表末尾，并更新尾指针；出队操作时，删除头节点，并更新头指针。链队列的优点是插入和删除操作简单高效，但访问元素需要遍历链表，效率较低。

相关问题

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

循环顺序队列头文件：

#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