双端队列（deque，即double-ended queue的缩写）是一种具有队列和栈性质的数据结构，即可以（也只能）在线性表的两端进行插入和删除。若以顺序存储方式实现双端队列，请编写例程实现下列操作

双端队列（deque，即double-ended queue的缩写）是一种具有队列和栈性质的数据结构，即可以（也只能）在线性表的两端进行插入和删除。若以顺序存储方式实现双端队列，则请编写例程实现下列操作。

相关问题

基于视频中的链队列实现双端队列。双端队列（Deque，Double-ended Queue）是一种数据结构，允许在两端（前端和后端）进行插入和删除操作。与传统的队列（只允许在一端插入、另一端删除），双端队列提供了更大的灵活性。

要实现双端队列（deque）基于视频中的链表结构，我们可以使用两个指针，一个指向队列的头部（front），另一个指向尾部（rear）。这种设计通常称为循环链表或环形缓冲区，因为最后一个节点的下一个节点实际上是第一个节点，这样可以方便地在两端进行插入和删除。

以下是一个简单的基于单链表的C语言实现：

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

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct Deque {
    Node* front; // 队首节点
    Node* rear;  // 队尾节点
    int size;   // 队列大小
} Deque;

// 初始化空的双端队列
Deque* deque_init() {
    Deque* dq = (Deque*)malloc(sizeof(Deque));
    dq->front = NULL;
    dq->rear = NULL;
    dq->size = 0;
    return dq;
}

// 插入元素到队尾
void deque_push_back(Deque* dq, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = dq->rear;
    if(dq->rear != NULL)
        dq->rear->next = newNode; // 如果非空，则将当前后继连接新节点
    else
        dq->front = newNode;      // 否则，新节点既是头又是尾
    dq->rear = newNode;
    dq->size++;
}

// 插入元素到队首
void deque_push_front(Deque* dq, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = dq->front;
    if(dq->front != NULL)
        dq->front->prev = newNode; // 如果非空，更新前驱
    else
        dq->rear = newNode;       // 新节点同时成为头和尾
    dq->front = newNode;
    dq->size++;
}

// 删除并返回队尾元素
int deque_pop_back(Deque* dq) {
    if(dq->rear == NULL) {
        printf("Queue is empty.\n");
        return -1; // 或者抛出异常
    }
    int popped_value = dq->rear->data;
    Node* temp = dq->rear;
    if(dq->rear == dq->front) { // 队列只剩一个元素
        dq->front = NULL;
        dq->rear = NULL;
    } else {
        dq->rear = dq->rear->next; // 更新后继
    }
    free(temp);
    dq->size--;
    return popped_value;
}

// 删除并返回队首元素
int deque_pop_front(Deque* dq) {
    if(dq->front == NULL) {
        printf("Queue is empty.\n");
        return -1; // 或者抛出异常
    }
    int popped_value = dq->front->data;
    Node* temp = dq->front;
    if(dq->front == dq->rear) { // 队列只剩一个元素
        dq->front = NULL;
        dq->rear = NULL;
    } else {
        dq->front = dq->front->prev; // 更新前驱
    }
    free(temp);
    dq->size--;
    return popped_value;
}

// 打印队列
void deque_display(Deque* dq) {
    Node* curr = dq->front;
    while(curr != NULL) {
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("\n");
}

// 示例用法
int main() {
    Deque* dq = deque_init();
    deque_push_back(dq, 1);
    deque_push_back(dq, 2);
    deque_push_front(dq, 0);
    deque_display(dq); // 输出: 0 1 2
    printf("Popped from back: %d\n", deque_pop_back(dq)); // 输出: 2
    deque_display(dq); // 输出: 0 1
    printf("Popped from front: %d\n", deque_pop_front(dq)); // 输出: 0
    deque_display(dq); // 输出: 1
    return 0;
}

B3656双端队列（deque）

B3656双端队列（Double Ended Queue，简称 deque）是一种特殊的线性数据结构，它允许在两端进行插入和删除操作，即既可以从头部添加元素（类似于列表的append操作），也可以从尾部添加元素（类似于列表的prepend操作）。此外，deque还支持从头部和尾部删除元素，这使得它在需要频繁在队列的两端进行操作的场景下非常高效。

deque的特点包括：
1. **双向访问**：可以在两端轻松地进行插入和删除操作。
2. **高效的随机访问**：通过索引可以快速访问队列内的任意元素，时间复杂度通常是O(1)。
3. **空间效率**：内部实现通常会尽量减少内存的移动，特别是在元素增删后保持连续存储的情况。

Python标准库中的collections模块提供了一个名为`deque`的数据结构，你可以直接使用它来创建和操作双端队列。例如：

from collections import deque

# 创建一个deque
dq = deque([1, 2, 3])

# 在尾部添加元素
dq.append(4)
# 在头部添加元素
dq.appendleft(0)

# 删除尾部元素
dq.pop()
# 删除头部元素
dq.popleft()