C++ 实现队列和循环队列

本文将提供 C++ 实现队列和循环队列的示例代码，并详细解释其原理和操作。

1. 队列

队列是一种先进先出 (FIFO) 的数据结构，类似于排队买票，先排队的人先买到票。

1.1 代码实现

#include <iostream>
using namespace std;

// 队列的节点
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 队列类
class Queue {
private:
    ListNode* head;
    ListNode* tail;
public:
    // 构造函数
    Queue() {
        head = NULL;
        tail = NULL;
    }

    // 入队
    void enqueue(int x) {
        ListNode* newNode = new ListNode(x);
        if (tail == NULL) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }

    // 出队
    void dequeue() {
        if (head == NULL) {
            cout << 'Queue is empty.' << endl;
        } else {
            ListNode* temp = head;
            head = head->next;
            delete temp;
            if (head == NULL) {
                tail = NULL;
            }
        }
    }

    // 获取队头元素
    int front() {
        if (head == NULL) {
            cout << 'Queue is empty.' << endl;
            return -1;
        } else {
            return head->val;
        }
    }

    // 判断队列是否为空
    bool isEmpty() {
        return head == NULL;
    }
};

1.2 操作说明

• 入队 (enqueue): 在队尾插入一个新节点。
• 出队 (dequeue): 删除队头节点。
• 获取队头元素 (front): 返回队头节点的值。
• 判断队列是否为空 (isEmpty): 判断队头指针是否为空。

2. 循环队列

循环队列是一种特殊的队列，它利用数组的循环特性来实现，避免了传统队列中由于队头和队尾指针移动到数组边界而导致的内存浪费。

2.1 代码实现

// 循环队列类
class CircularQueue {
private:
    int* arr;
    int head;
    int tail;
    int capacity;
public:
    // 构造函数
    CircularQueue(int size) {
        arr = new int[size];
        head = -1;
        tail = -1;
        capacity = size;
    }

    // 入队
    void enqueue(int x) {
        if (isFull()) {
            cout << 'Queue is full.' << endl;
        } else {
            if (isEmpty()) {
                head = 0;
            }
            tail = (tail + 1) % capacity;
            arr[tail] = x;
        }
    }

    // 出队
    void dequeue() {
        if (isEmpty()) {
            cout << 'Queue is empty.' << endl;
        } else {
            if (head == tail) {
                head = -1;
                tail = -1;
            } else {
                head = (head + 1) % capacity;
            }
        }
    }

    // 获取队头元素
    int front() {
        if (isEmpty()) {
            cout << 'Queue is empty.' << endl;
            return -1;
        } else {
            return arr[head];
        }
    }

    // 判断队列是否为空
    bool isEmpty() {
        return head == -1;
    }

    // 判断队列是否已满
    bool isFull() {
        return (tail + 1) % capacity == head;
    }
};

2.2 操作说明

• 入队 (enqueue): 在队尾插入一个新元素。
• 出队 (dequeue): 删除队头元素。
• 获取队头元素 (front): 返回队头元素。
• 判断队列是否为空 (isEmpty): 判断队头指针是否为空。
• 判断队列是否已满 (isFull): 判断队尾指针加1取模容量是否等于队头指针。

3. 示例代码

int main() {
    // 测试队列
    Queue q1;
    q1.enqueue(1);
    q1.enqueue(2);
    q1.enqueue(3);
    cout << q1.front() << endl; // 输出1
    q1.dequeue();
    cout << q1.front() << endl; // 输出2
    q1.dequeue();
    cout << q1.front() << endl; // 输出3
    q1.dequeue();
    cout << q1.isEmpty() << endl; // 输出1

    // 测试循环队列
    CircularQueue q2(3);
    q2.enqueue(1);
    q2.enqueue(2);
    q2.enqueue(3);
    cout << q2.front() << endl; // 输出1
    q2.dequeue();
    cout << q2.front() << endl; // 输出2
    q2.dequeue();
    cout << q2.front() << endl; // 输出3
    q2.dequeue();
    cout << q2.isEmpty() << endl; // 输出1

    return 0;
}

4. 总结

本文详细介绍了 C++ 中队列和循环队列的实现原理，并提供了完整的代码示例。通过代码示例，您可以学习如何使用 C++ 创建队列和循环队列，以及如何进行入队、出队、获取队头元素、判断队列是否为空等操作。