队列可以通过两种常见的实现方式来表示：顺序队列（数组实现）和链式队列（链表实现）。这两种方式在计算机科学中都广泛使用，每种实现方式都有其优势和适用场景。
1. 顺序队列（数组实现）：
顺序队列是使用数组来表示队列的一种实现方式。在顺序队列中，我们使用一个固定大小的数组来存储队列的元素，并使用两个指针 front 和 rear 来标记队列的头部和尾部。
front：指向队列头部的指针，用于出队操作，即删除队列头部元素。rear：指向队列尾部的指针，用于入队操作，即添加新元素到队列尾部。
入队操作：将新元素添加到 rear 指针所指向的位置，并将 rear 指针向后移动一位。若 rear 指针已达到数组的末尾，则说明队列已满，无法再添加新元素。
出队操作：将 front 指针所指向的元素从队列中移除，并将 front 指针向后移动一位。若 front 指针已追上 rear 指针，则说明队列为空，无法继续出队操作。
顺序队列的优点是简单、快速，可以直接通过数组索引访问元素，不需要额外的内存分配。但是由于数组大小固定，可能会导致队列溢出（队列已满无法再添加元素）的问题。
2. 链式队列（链表实现）：
链式队列是使用链表来表示队列的一种实现方式。在链式队列中，我们使用链表来动态地存储队列的元素。
每个节点包含一个元素和一个指向下一个节点的指针。链式队列不会有固定大小的限制，可以根据需要动态地分配内存。
入队操作：将新元素添加到链表的尾部，并更新尾部指针，指向新节点。
出队操作：将链表的头部节点移除，并更新头部指针，指向下一个节点。
链式队列的优点是可以灵活地添加和删除元素，避免了队列溢出的问题。但是相比于顺序队列，链式队列可能会占用更多的内存，因为每个节点需要额外的指针来指向下一个节点。
选择实现方式：
选择队列的实现方式取决于具体的应用场景和需求。如果知道队列的最大容量，并且需要高效地进行入队和出队操作，那么顺序队列可能是更好的选择。但是如果需要动态地添加和删除元素，并且对空间的利用更加灵活，那么链式队列可能是更好的选择。
在实际应用中，如果预估队列的大小并且不会频繁发生扩容，顺序队列可能是更有效的选择。如果队列大小不可预估，或者需要频繁添加和删除元素，链式队列可能更合适。
1. 顺序队列（数组实现）的具体例子：
#include <iostream>
class Queue {
private:
int capacity;
int* queue;
int front;
int rear;
int size;
public:
Queue(int capacity) {
this->capacity = capacity;
queue = new int[capacity];
front = 0;
rear = -1;
size = 0;
}
bool is_empty() {
return size == 0;
}
bool is_full() {
return size == capacity;
}
void enqueue(int item) {
if (is_full()) {
std::cout << "Queue is full. Cannot enqueue." << std::endl;
return;
}
rear = (rear + 1) % capacity;
queue[rear] = item;
size++;
}
int dequeue() {
if (is_empty()) {
std::cout << "Queue is empty. Cannot dequeue." << std::endl;
return -1;
}
int item = queue[front];
front = (front + 1) % capacity;
size--;
return item;
}
~Queue() {
delete[] queue;
}
};
// 创建一个容量为5的顺序队列，并进行入队和出队操作
int main() {
Queue queue(5);
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
std::cout << queue.dequeue() << std::endl; // Output: 10
std::cout << queue.dequeue() << std::endl; // Output: 20
queue.enqueue(40);
queue.enqueue(50);
return 0;
}
2. 链式队列（链表实现）的具体例子：
#include <iostream>
class QueueNode {
public:
int data;
QueueNode* next;
QueueNode(int data) {
this->data = data;
next = nullptr;
}
};
class Queue {
private:
QueueNode* front;
QueueNode* rear;
int size;
public:
Queue() {
front = nullptr;
rear = nullptr;
size = 0;
}
bool is_empty() {
return size == 0;
}
void enqueue(int item) {
QueueNode* newNode = new QueueNode(item);
if (is_empty()) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
size++;
}
int dequeue() {
if (is_empty()) {
std::cout << "Queue is empty. Cannot dequeue." << std::endl;
return -1;
}
int item = front->data;
QueueNode* temp = front;
front = front->next;
delete temp;
size--;
return item;
}
~Queue() {
while (front != nullptr) {
QueueNode* temp = front;
front = front->next;
delete temp;
}
}
};
// 创建一个链式队列，并进行入队和出队操作
int main() {
Queue queue;
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
std::cout << queue.dequeue() << std::endl; // Output: 10
std::cout << queue.dequeue() << std::endl; // Output: 20
queue.enqueue(40);
queue.enqueue(50);
return 0;
}