一、STL提供的deque实现
C++ STL提供了deque (Double-Ended Queue,双端队列)容器,其能够快速地在首位添加和删除元素。下面是例子代码:
#include#include using namespace std; int main() { deque q; // 定义一个deque q.push_back(1); // 在末尾添加元素 q.push_front(2); // 在头部添加元素 q.pop_back(); // 删除末尾元素 q.pop_front(); // 删除头部元素 return 0; }
deque 容器的底层实现是一块连续的内存空间,但是容器在各个元素之间预留了一些空间,以便实现常数时间的在头部和尾部添加或删除元素。deque 还提供了随机访问元素的能力,其时间复杂度为 O(1)。但是,deque 的空间利用率不是很高,虽然是连续内存,但预留空间一定程度浪费了空间。
二、双向链表实现
1. 链表节点的定义
双向链表是一种很好的选择,其可以充分利用空间,同时又具有快速在首尾添加或删除元素的能力。下面是链表节点的定义:
templatestruct LinkedNode { T data; // 数据域 LinkedNode* prev; // 前驱指针 LinkedNode* next; // 后继指针 LinkedNode(const T& ele = T(), LinkedNode* ptr = nullptr) : data(ele), prev(ptr), next(ptr) {} };
链表节点中 data 字段是该节点的数据域,prev 和 next 分别是该节点的前驱指针和后继指针。链表节点的构造函数可以传入一个值,用于初始化该节点的数据域。
2. 双向链表的实现
双向链表中,头结点的 prev 指向尾结点,尾结点的 next 指向头结点。链表模板类的实现如下:
templateclass LinkedList { private: LinkedNode * head; LinkedNode * tail; int _size; public: LinkedList() : head(new LinkedNode ()), tail(head), _size(0) {} // 在链表尾部添加元素 void push_back(const T& ele) { insert(tail, ele); // 将元素插入到尾结点之后 } // 在链表头部添加元素 void push_front(const T& ele) { LinkedNode * node = new LinkedNode (ele, head->next); // 新建一个节点 node->next->prev = node; // 修改相邻节点的prev指针 head->next = node; // 修改头结点的后继指针 _size++; // 长度+1 } // 删除链表尾部元素 void pop_back() { if (empty()) return; LinkedNode * node = tail->prev; // 暂存尾结点的前驱节点 node->prev->next = tail; // 修改相邻节点的next指针 tail->prev = node->prev; // 修改尾结点的前驱指针 delete node; // 删除节点 _size--; // 长度-1 } // 删除链表头部元素 void pop_front() { if (empty()) return; LinkedNode * node = head->next; // 暂存头结点的后继节点 head->next = node->next; // 修改头结点的后继指针 node->next->prev = head; // 修改相邻节点的prev指针 delete node; // 删除节点 _size--; // 长度-1 } // 判断链表是否为空 bool empty() const { return _size == 0; } // 返回链表中元素的个数 int size() const { return _size; } private: // 将元素插入到列表中某个节点的后面 void insert(LinkedNode * node, const T& elem) { LinkedNode * new_node = new LinkedNode (elem, node->next); // 新建一个节点 new_node->next->prev = new_node; // 修改相邻节点指针 node->next = new_node; // 插入节点 if (new_node->next == nullptr) { // 如果插入的节点是尾结点的后继 tail = new_node; // 更新尾结点指针 } _size++; // 长度+1 } };
链表的构造函数中,初始化了头结点,并令尾结点指向头结点。链表中 _size 为节点个数。
三、使用自定义的双向链表实现双端队列
使用自定义的双向链表实现双端队列,只需要在链表的基础上添加队列的操作即可。下面是例子代码:
templateclass Deque { public: void push_back(const T& ele) { list.push_back(ele); } // 在队尾添加元素 void push_front(const T& ele) { list.push_front(ele); } // 在队头添加元素 void pop_back() { list.pop_back(); } // 删除队尾元素 void pop_front() { list.pop_front(); } // 删除队头元素 bool empty() const { return list.empty(); } // 判断队列是否为空 int size() const { return list.size(); } // 返回队列中元素的个数 private: LinkedList list; // 双向链表 };
该双端队列从 LinkedList 继承,包含 push_back、push_front、pop_back、pop_front 等方法,可以实现在首尾添加和删除元素并且保证了链表的特性不变。
四、总结
本文介绍了使用 C++ STL 中的 deque 容器实现和自定义链表实现的双端队列。双端队列是一种常用的数据结构,具有快速在首尾添加和删除元素的能力,非常适合对队列操作频繁的场景。链表实现的双端队列,相对于 STL 提供的 deque 容器,能够充分利用空间,同时保证了链表的操作。