写在前面：
上一讲，我们用的是数组来实现队列的功能，这一讲我们尝试用链表来实现，其实我认为链表实现比数组实现更容易理解一些。
队列的插入
书接前文，由于上一讲我们已经对队列的定义进行深入的讲解了，我们直接进入代码部分，同样我们也直接实现双端队列的功能。
用链表进行操作其实就用到了之前我们讲的双向链表操作啦，对应到双端队列里就是左插入和右插入，左删除和右删除。为了方便，这里创建了头结点和尾结点，通过头结点和尾结点可以快速进行操作。具体操作和双向链表几乎一样，没有了解过的小伙伴可以看我之前讲的双向链表那一节。
//左插入
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;
}
}如果大家有什么问题的话，欢迎在下方评论区进行讨论哦~
