写在前面：
上一讲，我们用的是数组来实现队列的功能，这一讲我们尝试用链表来实现，其实我认为链表实现比数组实现更容易理解一些。

队列的插入

书接前文，由于上一讲我们已经对队列的定义进行深入的讲解了，我们直接进入代码部分，同样我们也直接实现双端队列的功能。

用链表进行操作其实就用到了之前我们讲的双向链表操作啦，对应到双端队列里就是左插入和右插入，左删除和右删除。为了方便，这里创建了头结点和尾结点，通过头结点和尾结点可以快速进行操作。具体操作和双向链表几乎一样，没有了解过的小伙伴可以看我之前讲的双向链表那一节。

//左插入
void left_insert(int key) {
    if (Size == maxSize) {
        cout << "该队列已满" << endl;
    }
    else {
        Node* new_node = new Node;
        new_node->val = key;            
        new_node->right = head->right;        
        new_node->left = head;
        head->right = new_node;
        new_node->right->left = new_node;
        Size++;
    }
}

//右插入
void right_insert(int key) {
    if (Size == maxSize) {
        cout << "该队列已满" << endl;
    }
    else {
        Node* new_node = new Node;
        new_node->val = key;
        new_node->right = last;
        new_node->left = last->left;
        last->left = new_node;
        new_node->left->right = new_node;
        Size++;
    }
}

队列的删除

删除操作也分为左删除和右删除，删除操作同样用到的是双向链表的功能。

//右删除
void right_delete() {
    if (Size == 0) {
        cout << "该队列为空" << endl;
    }
    else {
        Node* free_node = last->left;
        free_node->left->right = last;
        last->left = free_node->left;
        delete[]free_node;
        Size--;
    }
}

//左删除
void left_delete() {
    if (Size == 0) {
        cout << "该队列为空" << endl;
    }
    else {
        Node* free_node = head->right;
        free_node->right->left = head;
        head->right = free_node->right;
        delete[]free_node;
        Size--;
    }
}

全部代码

#include<bits/stdc++.h>
using namespace std;

//结点的定义
struct Node {
    int val;
    Node* right;
    Node* left;
};

Node* head;    //头指针
Node* last;    //尾指针
int Size;    //队列中当前元素数量
int maxSize;//队列最大容纳元素数量

void init_node();
void right_insert(int);
void left_insert(int);
void right_delete();
void left_delete();
void show();

int main() {
    init_node();
    right_insert(1);
    left_insert(2);
    right_insert(3);
    left_insert(4);
    right_insert(5);
    left_insert(6);
    show();
    right_delete();
    left_delete();
    show();
    right_delete();
    left_delete();
    right_delete();
    left_delete();
    show();
}

//初始化结点
void init_node() {
    head = new Node;
    last = new Node;
    head->right = last;
    last->left = head;
    head->left = NULL;
    last->right = NULL;
    Size = 0;
    maxSize = 5;
}

//左插入
void left_insert(int key) {
    if (Size == maxSize) {
        cout << "该队列已满" << endl;
    }
    else {
        Node* new_node = new Node;
        new_node->val = key;            
        new_node->right = head->right;        
        new_node->left = head;
        head->right = new_node;
        new_node->right->left = new_node;
        Size++;
    }
}

//右插入
void right_insert(int key) {
    if (Size == maxSize) {
        cout << "该队列已满" << endl;
    }
    else {
        Node* new_node = new Node;
        new_node->val = key;
        new_node->right = last;
        new_node->left = last->left;
        last->left = new_node;
        new_node->left->right = new_node;
        Size++;
    }
}

//右删除
void right_delete() {
    if (Size == 0) {
        cout << "该队列为空" << endl;
    }
    else {
        Node* free_node = last->left;
        free_node->left->right = last;
        last->left = free_node->left;
        delete[]free_node;
        Size--;
    }
}

//左删除
void left_delete() {
    if (Size == 0) {
        cout << "该队列为空" << endl;
    }
    else {
        Node* free_node = head->right;
        free_node->right->left = head;
        head->right = free_node->right;
        delete[]free_node;
        Size--;
    }
}

void show() {
    if (Size == 0) {
        cout << "队列为空" << endl;
    }
    else {
        Node* temp = head->right;
        for (int i = 0; i < Size; i++) {
            cout << temp->val << " ";
            temp = temp->right;
        }
        cout << endl;
    }
}

如果大家有什么问题的话，欢迎在下方评论区进行讨论哦~