21 - 队列 - 循环队列——队列的顺序表示和实现

**队列**

队列是一种线性数据结构，遵循先进先出(FIFO)原则。它允许添加元素到末尾，并从头部取出元素。在本文中，我们将讨论队列的顺序表示和实现。

### 队列的顺序表示队列可以使用数组或链表来实现。下面是队列的基本操作：

* **enqueue(x)**：向队列末尾添加一个新元素x。
* **dequeue()**：从队列头部取出一个元素，并返回它。
* **peek()**：查看队列头部的元素，但不移除它。

### 队列的实现#### 数组实现我们可以使用数组来实现队列。下面是C++代码示例：

cppclass Queue {
private:
 int *data;
 int front, rear, size;

public:
 Queue(int capacity) : data(new int[capacity]), front(0), rear(0), size(0) {}

 ~Queue() { delete[] data; }

 void enqueue(int x) {
 if (size == data.length()) {
 // Handle queue overflow return;
 }
 data[rear++] = x;
 size++;
 }

 int dequeue() {
 if (isEmpty()) {
 // Handle empty queue return -1;
 }
 int x = data[front++];
 size--;
 return x;
 }

 int peek() {
 if (isEmpty()) {
 // Handle empty queue return -1;
 }
 return data[front];
 }

 bool isEmpty() { return size ==0; }
};

cppclass Node {
public:
 int data;
 Node *next;

 Node(int x) : data(x), next(nullptr) {}
};

class Queue {
private:
 Node *head, *tail;

public:
 void enqueue(int x) {
 Node *node = new Node(x);
 if (isEmpty()) {
 head = tail = node;
 } else {
 tail->next = node;
 tail = node;
 }
 }

 int dequeue() {
 if (isEmpty()) {
 // Handle empty queue return -1;
 }
 int x = head->data;
 Node *temp = head;
 head = head->next;
 delete temp;
 return x;
 }

 int peek() {
 if (isEmpty()) {
 // Handle empty queue return -1;
 }
 return head->data;
 }

 bool isEmpty() { return head == nullptr; }
};

cppclass CircularQueue {
private:
 int *data;
 int front, rear, size;

public:
 CircularQueue(int capacity) : data(new int[capacity]), front(0), rear(0), size(0) {}

 ~CircularQueue() { delete[] data; }

 void enqueue(int x) {
 if (size == data.length()) {
 // Handle queue overflow return;
 }
 data[rear++] = x;
 if (rear == data.length()) {
 rear =0;
 }
 size++;
 }

 int dequeue() {
 if (isEmpty()) {
 // Handle empty queue return -1;
 }
 int x = data[front++];
 if (front == data.length()) {
 front =0;
 }
 size--;
 return x;
 }

 int peek() {
 if (isEmpty()) {
 // Handle empty queue return -1;
 }
 return data[front];
 }

 bool isEmpty() { return size ==0; }
};