C++数据结构的队列详解

队列是什么？

队列是一种先进先出（First In First Out, FIFO）的数据结构，类似于现实生活中的排队等待服务。

队列中的数据按照先进先出的原则被处理。新的元素只能被插入在队列的末尾，而旧的元素只能从队列的开头被删除。因此，队列的末尾称为队尾，队列的开头被称为队头。

队列的实现方式

数组实现方式

队列可以使用数组实现，在这种实现方式中，队列是一个固定大小的数组，插入和删除操作会改变队列的头和尾指针。

// C++数组实现队列的代码样例

class Queue {
    int* arr;       // 存储队列元素的数组
    int front;      // 队头指针
    int rear;       // 队尾指针
    int capacity;   // 队列的大小
    int count;      // 队列中元素的个数

public:
    // Constructor
    Queue(int size) {
        arr = new int[size];
        capacity = size;
        front = 0;
        rear = -1;
        count = 0;
    }

    // Destructor
    ~Queue() {
        delete[] arr;
    }

    // Enqueue operation
    void enqueue(int item) {
        if (isFull()) {
            cout << "Queue is full!" << endl;
            return;
        }

        rear = (rear + 1) % capacity;   // 尾指针移到队列结尾
        arr[rear] = item;
        count++;
    }

    // Dequeue operation
    void dequeue() {
        if (isEmpty()) {
            cout << "Queue is empty!" << endl;
            return;
        }

        front = (front + 1) % capacity; // 头指针向队列头移动
        count--;
    }

    // Check if queue is full
    bool isFull() {
        return count == capacity;
    }

    // Check if queue is empty
    bool isEmpty() {
        return count == 0;
    }
};

// 示例1
int main() {
    Queue queue(5);
    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);
    queue.dequeue();
    queue.enqueue(4);
    queue.enqueue(5);
    queue.enqueue(6);

    return 0;
}

// 示例2
int main() {
    Queue queue(5);
    queue.enqueue(1);
    queue.enqueue(2);
    queue.dequeue();
    queue.enqueue(3);
    queue.dequeue();
    queue.enqueue(4);

    return 0;
}

链表实现方式

另一种常用的实现方式是使用链表来实现队列。队列的头和尾可以使用指针进行追踪，这种方式可以处理变长队列，因为动态分配内存。

// C++链表实现队列的代码样例

class QueueNode {
public:
    int data;
    QueueNode* next;

    QueueNode(int data) {
        this->data = data;
        next = NULL;
    }
};

class Queue {
public:
    QueueNode *front, *rear;

    Queue() {
        front = rear = NULL;
    }

    // Enqueue operation
    void enqueue(int x) {
        QueueNode* temp = new QueueNode(x);

        if (rear == NULL) {
            front = rear = temp;
            return;
        }

        rear->next = temp;
        rear = temp;
    }

    // Dequeue operation
    void dequeue() {
        if (front == NULL) {
            return;
        }

        QueueNode* temp = front;
        front = front->next;

        if (front == NULL) {
            rear = NULL;
        }

        delete temp;
    }

    // Check if queue is empty
    bool isEmpty() {
        return (front == NULL && rear == NULL);
    }
};

// 示例1
int main() {
    Queue q;
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    q.dequeue();
    q.dequeue();
    q.enqueue(4);
    q.enqueue(5);
    q.enqueue(6);

    return 0;
}

// 示例2
int main() {
    Queue q;
    q.enqueue(1);
    q.enqueue(2);
    q.dequeue();
    q.enqueue(3);
    q.dequeue();
    q.enqueue(4);

    return 0;
}

总结

队列是一种非常有用的数据结构，可以使用数组或链表进行实现。它们允许我们以一种自然的方式对一些元素进行排队和处理。队列的基本操作是enqueue和dequeue。队列的另一个重要特性是先进先出，这意味着队列中元素的处理顺序始终按照它们被插入的顺序。这种数据结构非常适合实现不间断服务（如操作系统中的进程管理）。