赞
踩
单向队列仅能从队列的头部删除元素、在队列的尾部添加元素。与其相比,双向队列的灵活性更好,可以在头尾执行元素的添加或删除。
一般编程语言中有已实现的双向队列,双向队列的一般操作有:
注意:上面的方法名不一定是双向队列的正确的成员函数名,只是便于理解。
使用编程语言内部的双向队列有以下代码:
- //初始化双向队列
- deque<int> deque;
-
- //入队
- deque.push_back(2);//队尾加入元素
- deque.push_back(3);
- deque.push_front(7);//队首加入元素
- deque.push_front(8);
-
- //此时双向队列:8 7 2 3
-
- //访问双向队列的元素
- int front =deque.front();//队首元素
- int back = deque.back();//队尾元素
-
- //元素出队
- deque.pop_front();//队首元素出队,此时双向队列:7 2 3
- deque.pop_back();//队尾元素出队,此时双向队列: 7 2
-
- //获取双向队列的长度
- int size=deque.size();
-
- //判断双向队列是否为空
- bool empty = deque.empty();
双向队列的实现与队列比较类似,同样可以使用数组或者链表实现底层数据结构。
1.基于数组的实现
-
- class ArrayDeque{
- private:
- vector<int> nums;//储存双向队列的数组
- int front;//队首指针,指向队首元素
- int queSize;//双向队列的长度
-
- public:
- //构造函数,初始化双向队列
- ArrayDeque(int capacity){
- nums.resize(capacity);//由于本数组使用的内置动态数组,直接使用成员函数初始化数组容量
- front = queSize=0;
- }
-
- //析构函数不再需要,因为内置动态数组一般内存会自动释放,手动开辟的数组空间需要手动释放
-
- //获取双向队列的容量(容量是最大可以存多少个元素)
- int capacity(){
- return nums.size();
- }
-
- //获取双向队列的长度(长度是目前存了多少元素)
- int size(){
- return queSize;
- }
-
- //判断双向队列是否为空
- bool isEmpty(){
- return queSize==0;
- }
-
- //计算环形数组的索引
- int index(int i){
- //通过取余操作实现数组首尾相连
- //当i越过数组尾部后,回到头部
- //当i越过数组头部后,回到尾部
- return (i+capacity())%capacity();
- }
-
- //队首入队
- void pushFirst(int num){
- if(queSize==capacity()){
- cout<<"双向队列已满"<<endl;
- return;
- }
- //队首指针向左移动一位
- //通过取余操作实现front越过数组头部回到数组尾部
- front = index(front - 1);
- //将num添加至队首
- nums[front]=num;
- queSize++;
- }
-
- //队尾入队
- void pushLast(int num){
- if(queSize==capacity()){
- cout<<"双向队列已满"<<endl;
- return;
- }
- //队尾指针向右移动一位
- int rear = index(front+queSize);
- //将num添加至队尾
- nums[rear]=num;
- queSize++;
- }
-
-
- //获取队首元素
- int peekFirst(){
- if(isEmpty()) throw out_of_range("双向队列是空");
- return nums[front];
- }
-
- //获取队尾元素
- int peekLast(){
- if(isEmpty()) throw out_of_range("双向队列是空");
- //计算队尾元素索引
- int last =index(front+queSize-1);
- return nums[last];
- }
-
- //队首出队
- int popFirst(){
- int num=peekFirst();
-
- //队首元素向右移动一位
- front=index(front+1);
-
- queSize--;
- return num;
- }
-
- //队尾出队
- int popLast(){
- int num=peekLast();
- queSize--;
- return num;
- }
-
- //返回数组用于打印
- vector<int> toVector(){
- //仅转换有效长度范围内的队列元素
- vector<int> res(queSize);
- for(int i =0, j=front;i<queSize;i++,j++){
- res[i]=nums[index(j)];
- }
- return res;
- }
-
- };
2.基于双向链表实现
- struct DoublyListNode{
- int val;
- DoublyListNode* next;
- DoublyListNode* prev;
- DoublyListNode(int val): val(val),prev(nullptr),next(nullptr){}
- };
-
- //基于双向链表实现的双向队列
- class LinkedListDeque{
- private:
- DoublyListNode *front, *rear;//头节点front,尾节点rear
- int queSize=0;
-
- public:
- //构造函数
- LinkedListDeque(): front(nullptr),rear(nullptr){}
-
- //析构函数
- ~LinkedListDeque(){
- //遍历链表,删除节点,释放内存
- DoublyListNode* pre, *cur=front;
- while(cur!=nullptr){
- pre=cur;
- cur=cur->next;
- delete pre;
- }
- }
-
- //获取双向队列的长度
- int size(){
- return queSize;
- }
-
- //判断双向队列是否为空
- bool isEmpty(){
- return size()==0;
- }
-
- //入队操作
- void push(int num, bool isFront){
- DoublyListNode *node=new DoublyListNode(num);
- //若链表为空,则令front和rear都指向node
- if(isEmpty()) front = rear = node;
-
- //队首入队操作
- else if (isFront){
- //将node添加至链表头部
- front->prev=node;
- node->next=front;
- front=node;//更新头节点
- }else{
- //队尾入队操作
- //将node添加至链表尾部
- rear->next=node;
- node->prev=rear;
- rear=node;//更新尾节点
- }
- queSize++;//更新队列长度
- }
-
-
- //队首入队
- void pushFirst(int num){
- push(num,true);
- }
-
- //队尾入队
- void pushLast(int num){
- push(num,false);
- }
-
-
- //出队操作
- int pop(bool isFront){
- if(isFront) throw out_of_range("队列为空");
- int val;
-
- //队首出队操作
- if(isFront){
- val=front->val;//暂存头节点值
- //删除头节点
- DoublyListNode* fNext = front->next;
- if(fNext!=nullptr){
- fNext->prev=nullptr;
- front->next=nullptr;
- }
- delete front;
- front=fNext;//更新头节点;
-
- }else{
- //队尾出队操作
- val=rear->val;//暂存尾节点值
- //删除尾节点
- DoublyListNode *rPrev=rear->prev;
- if(rPrev!=nullptr){
- rPrev->next=nullptr;
- rear->prev=nullptr;
- }
- delete rear;
- rear=rPrev;//更新尾节点
-
- }
- queSize--;//更新队列长度
- return val;
- }
- //队首出队
- int popFirst(){
- return pop(true);
- }
-
- //队尾出队
- int popLast(){
- return pop(false);
- }
-
- //访问队首元素
- int peekFirst(){
- if(isEmpty()) throw out_of_range( " 双向队列为空");
- return front->val;
- }
-
- //访问队尾元素
- int peekLast(){
- if(isEmpty()) throw out_of_range( " 双向队列为空");
- return rear->val;
- }
-
- //返回数组用于打印
- vector<int> toVector(){
- DoublyListNode* node=front;
- vector<int> res(size());
- for(int i=0;i<res.size();i++){
- res[i]=node->val;
- node=node->next;
- }
- return res;
- }
- };
声明:本人所写内容全部参考hello-algo,仅用于个人复习。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。