数据结构–双端队列

双端队列（Double-ended Queue，简称Deque）是一种具有队列和栈特性的数据结构，可以在队列的两端进行插入和删除操作。双端队列允许从前端和后端同时进行插入和删除操作，因此可以称为“两端都可以进出的队列”。

双端队列的特点包括：

1. 可以在队列的头部和尾部进行插入和删除操作。
2. 元素的插入和删除操作可以分别称为入队和出队操作。
3. 可以实现先进先出（FIFO）和后进先出（LIFO）两种操作方式。
4. 可以用于实现栈、队列以及其他需要在两端进行插入和删除操作的场景。

双端队列的常见操作包括：

1. 在队列头部插入元素（头部入队）：将元素插入到队列头部。
2. 在队列尾部插入元素（尾部入队）：将元素插入到队列尾部。
3. 从队列头部删除元素（头部出队）：删除队列头部的元素并返回。
4. 从队列尾部删除元素（尾部出队）：删除队列尾部的元素并返回。
5. 获取队列头部的元素：返回队列头部的元素，但不删除。
6. 获取队列尾部的元素：返回队列尾部的元素，但不删除。
7. 判断队列是否为空：判断队列中是否有元素。
8. 获取队列中的元素个数：返回队列中元素的个数。

双端队列的实现方式有多种，包括使用数组、链表等数据结构。具体的实现方式可以根据不同的需求和场景选择合适的方式。

常用操作代码实现

#include <stdio.h>
#include <stdlib.h>

// 定义双端队列节点结构体
typedef struct Node {
    int data;           // 数据域
    struct Node* next;  // 指针域，指向下一个节点
} Node;

// 定义双端队列结构体
typedef struct Deque {
    Node* front;  // 队头指针
    Node* rear;   // 队尾指针
} Deque;

// 初始化双端队列
Deque* initializeDeque() {
    Deque* deque = (Deque*)malloc(sizeof(Deque));
    deque->front = NULL;
    deque->rear = NULL;
    return deque;
}

// 判断双端队列是否为空
int isEmpty(Deque* deque) {
    return (deque->front == NULL);
}

// 在队头插入元素
void insertFront(Deque* deque, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;

    if (isEmpty(deque)) {
        deque->front = newNode;
        deque->rear = newNode;
    } else {
        newNode->next = deque->front;
        deque->front = newNode;
    }
}

// 在队尾插入元素
void insertRear(Deque* deque, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;

    if (isEmpty(deque)) {
        deque->front = newNode;
        deque->rear = newNode;
    } else {
        deque->rear->next = newNode;
        deque->rear = newNode;
    }
}

// 从队头删除元素
int deleteFront(Deque* deque) {
    if (isEmpty(deque)) {
        printf("Deque is empty.\n");
        return -1;
    }

    int value = deque->front->data;
    Node* temp = deque->front;
    deque->front = deque->front->next;

    if (deque->front == NULL) {
        deque->rear = NULL;
    }

    free(temp);
    return value;
}

// 从队尾删除元素
int deleteRear(Deque* deque) {
    if (isEmpty(deque)) {
        printf("Deque is empty.\n");
        return -1;
    }

    int value = deque->rear->data;
    Node* temp = deque->rear;
    Node* current = deque->front;

    while (current->next != deque->rear) {
        current = current->next;
    }

    deque->rear = current;
    deque->rear->next = NULL;
    free(temp);
    return value;
}

// 获取队头元素
int getFront(Deque* deque) {
    if (isEmpty(deque)) {
        printf("Deque is empty.\n");
        return -1;
    }

    return deque->front->data;
}

// 获取队尾元素
int getRear(Deque* deque) {
    if (isEmpty(deque)) {
        printf("Deque is empty.\n");
        return -1;
    }

    return deque->rear->data;
}

// 打印双端队列元素
void printDeque(Deque* deque) {
    Node* current = deque->front;

    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }

    printf("\n");
}

int main() {
    Deque* deque = initializeDeque();

    insertFront(deque, 1);  // 队头插入元素1
    insertFront(deque, 2);  // 队头插入元素2
    insertRear(deque, 3);   // 队尾插入元素3

    printDeque(deque);      // 输出：2 1 3

    deleteFront(deque);     // 从队头删除元素
    printDeque(deque);      // 输出：1 3

    deleteRear(deque);      // 从队尾删除元素
    printDeque(deque);      // 输出：1

    printf("Front element: %d\n", getFront(deque));  // 输出队头元素：1
    printf("Rear element: %d\n", getRear(deque));    // 输出队尾元素：1

    return 0;
}

知识点回顾与重要考点