6-3 Deque

2024-05-10 06:12
文章标签 deque

本文主要是介绍6-3 Deque，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

作者 陈越

单位 浙江大学

A "deque" is a data structure consisting of a list of items, on which the following operations are possible:

  • Push(X,D): Insert item X on the front end of deque D.
  • Pop(D): Remove the front item from deque D and return it.
  • Inject(X,D): Insert item X on the rear end of deque D.
  • Eject(D): Remove the rear item from deque D and return it.
    Write routines to support the deque that take O(1) time per operation.

Format of functions:

Deque CreateDeque();
int Push( ElementType X, Deque D );
ElementType Pop( Deque D );
int Inject( ElementType X, Deque D );
ElementType Eject( Deque D );

where Deque is defined as the following:

typedef struct Node *PtrToNode;
struct Node {ElementType Element;PtrToNode Next, Last;
};
typedef struct DequeRecord *Deque;
struct DequeRecord {PtrToNode Front, Rear;
};

Here the deque is implemented by a doubly linked list with a header. Front and Rear point to the two ends of the deque respectively. Front always points to the header. The deque is empty when Front and Rear both point to the same dummy header.
Note: Push and Inject are supposed to return 1 if the operations can be done successfully, or 0 if fail. If the deque is empty, Pop and Eject must return ERROR which is defined by the judge program.

Sample program of judge:

#include <stdio.h>
#include <stdlib.h>#define ElementType int
#define ERROR 1e5
typedef enum { push, pop, inject, eject, end } Operation;typedef struct Node *PtrToNode;
struct Node {ElementType Element;PtrToNode Next, Last;
};
typedef struct DequeRecord *Deque;
struct DequeRecord {PtrToNode Front, Rear;
};
Deque CreateDeque();
int Push( ElementType X, Deque D );
ElementType Pop( Deque D );
int Inject( ElementType X, Deque D );
ElementType Eject( Deque D );Operation GetOp();          /* details omitted */
void PrintDeque( Deque D ); /* details omitted */int main()
{ElementType X;Deque D;int done = 0;D = CreateDeque();while (!done) {switch(GetOp()) {case push: scanf("%d", &X);if (!Push(X, D)) printf("Memory is Full!\n");break;case pop:X = Pop(D);if ( X==ERROR ) printf("Deque is Empty!\n");break;case inject: scanf("%d", &X);if (!Inject(X, D)) printf("Memory is Full!\n");break;case eject:X = Eject(D);if ( X==ERROR ) printf("Deque is Empty!\n");break;case end:PrintDeque(D);done = 1;break;}}return 0;
}/* Your function will be put here */

Sample Input:

Pop
Inject 1
Pop
Eject
Push 1
Push 2
Eject
Inject 3
End

Sample Output:

Deque is Empty!
Deque is Empty!
Inside Deque: 2 3

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

C程序如下：

// 创建一个空的双端队列  
Deque CreateDeque(){  // 分配内存给DequeRecord结构体  Deque p = (Deque)malloc(sizeof(struct DequeRecord));  // 如果内存分配失败，此处应该添加错误处理代码  // 分配内存给队列的第一个（也是唯一的）节点  PtrToNode q = (PtrToNode)malloc(sizeof(struct Node));  // 初始化节点，使其指向自己（空队列的情况）  q->Next = q->Last = NULL;  // 设置Deque的前端和后端都指向这个节点  p->Front = q;  p->Rear = q;  // 返回新创建的Deque  return p;  
}  // 在双端队列的前端添加一个元素  
int Push( ElementType X, Deque D ){  // 分配内存给新节点  PtrToNode q = (PtrToNode)malloc(sizeof(struct Node));  q->Element = X;  // 如果队列为空（只有一个哨兵节点）  if(D->Front == D->Rear){  // 新节点的Next和Last都设置为NULL（因为它是第一个元素）  q->Next = NULL;  // 前一个节点（也就是D->Front）的Next指向新节点  q->Last = D->Front;  D->Front->Next = q;  // 更新Rear指向新节点  D->Rear = q;  }  else{  // 如果队列不为空，将新节点插入到Front之后  q->Next = D->Front->Next;  // 前一个节点（也就是D->Front->Next的前一个节点）的Last指向新节点  D->Front->Next->Last = q;  // 更新Front的Next指向新节点  D->Front->Next = q;  // 新节点的Last指向Front->Next（也就是原来的第一个元素）  q->Last = D->Front->Next;  }  // 总是成功返回1  return 1;  
}  // 从双端队列的前端移除一个元素  
ElementType Pop( Deque D ){  // 如果队列为空，返回错误值  if(D->Front == D->Rear){  return ERROR;  }  // 获取第一个节点（也就是要移除的节点）  PtrToNode p = D->Front->Next;  // 保存要返回的元素  ElementType m = p->Element;  // 更新Front的Next指向下一个节点  D->Front->Next = p->Next;  // 如果队列中只剩下一个节点（也就是哨兵节点），则更新Last指向NULL  if(D->Front->Next == NULL) {  D->Rear = D->Front;  } else {  // 否则，更新新的第一个节点的Last指向Front  D->Front->Next->Last = D->Front;  }  // 释放移除的节点的内存  free(p);  // 返回移除的元素  return m;  
}  // 在双端队列的后端添加一个元素  
int Inject( ElementType X, Deque D ){  // 分配内存给新节点  PtrToNode p = (PtrToNode)malloc(sizeof(struct Node));  p->Element = X;  // 新节点的Last指向原Rear节点  p->Last = D->Rear;  // 原Rear节点的Next指向新节点  D->Rear->Next = p;  // 更新Rear指向新节点  D->Rear = p;  // 总是成功返回1  return 1;  
}  // 从双端队列的后端移除一个元素  
ElementType Eject( Deque D ){  // 如果队列为空，返回错误值  if(D->Front == D->Rear){  return ERROR;  }  // 获取最后一个节点（也就是要移除的节点）  ElementType m = D->Rear->Element;  PtrToNode p = D->Rear;  // 更新原Rear的前一个节点的Next指向NULL（因为Rear是最后一个节点）  D->Rear->Last->Next = NULL;  // 更新Rear指向原Rear的前一个节点  D->Rear = D->Rear->Last;  // 释放移除的节点的内存  free(p);  // 返回移除的元素  return m;  
}

这篇关于6-3 Deque的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/975658。

相关文章

C++面试八股文：std::deque用过吗？

C++面试八股文：std::deque用过吗？

100编程书屋_孔夫子旧书网 某日二师兄参加XXX科技公司的C++工程师开发岗位第26面： 面试官：deque用过吗？ 二师兄：说实话，很少用，基本没用过。 面试官：为什么？ 二师兄：因为使用它的场景很少，大部分需要性能、且需要自动扩容的时候使用vector，需要随机插入和删除的时候可以使用list。 面试官：那你知道STL中的stack是如何实现的吗？ 二师兄：默认情况下，stack使
阅读更多...
【简易版tinySTL】 deque容器

【简易版tinySTL】 deque容器

文章目录 基本概念功能思路数据结构循环数组实现 代码实现deque.htest.cpp 代码详解变量push_frontpush_backpop_front、pop_backoperator[]clearprintElementsresize 本实现版本 和 C++ STL标准库实现版本的区别： 基本概念 功能： 双端数组，可以对头端进行插入删除操作 deque与vector
阅读更多...
c++编程（18）——deque的模拟实现（2）容器篇

c++编程（18）——deque的模拟实现（2）容器篇

欢迎来到博主的专栏——c++编程 博主ID：代码小豪 文章目录 deque的数据结构deque的构造默认构造填充构造 deque的其他操作deque的插入、删除push_back和push_frontpop_back和pop_frontclear、erase和insert操作 传送门 在上一篇中，我们已经实现了deque最核心的部分，即deque的迭代器，在deque容器当中，迭
阅读更多...
【C++提高编程-05】----C++之Deque容器实战

【C++提高编程-05】----C++之Deque容器实战

🎩 欢迎来到技术探索的奇幻世界👨‍💻 📜 个人主页：@一伦明悦-CSDN博客 ✍🏻 作者简介： C++软件开发、Python机器学习爱好者 🗣️ 互动与支持：💬评论      👍🏻点赞      📂收藏     👀关注+ 如果文章有所帮助，欢迎留下您宝贵的评论， 点赞加收藏支持我，点击关注，一起进步！ 前言       Deque（双端队列）是C++ STL中
阅读更多...
【C++】stack、queue和deque的使用

【C++】stack、queue和deque的使用

💗个人主页💗 ⭐个人专栏——C++学习⭐ 💫点击关注🤩一起学习C语言💯💫 目录 导读 一、stack 1. stack介绍 2. stack使用 二、queue 1. queue介绍 2. queue使用 三、deque 1. deque介绍 2. deque的迭代器 3. deque使用 四、三者关系 1. STL标准库中stack和queue的底层
阅读更多...
C++:SLT容器--＞deque

C++:SLT容器--＞deque

C++:SLT容器-->deque 1. 构造函数2. deque 赋值操作3. deque 大小操作4. deque 插入和删除5. deque 容器数据存取6. deque 排序操作 双端数组，可以对头部和尾部进行插入删除操作 ==需要导入头文件#include <deque>== 1. 构造函数 deque deqT; // 默认构造函数 deque(be
阅读更多...
C++迈向精通：STL的Deque复现

C++迈向精通：STL的Deque复现

C++迈向精通：STL的Deque复现 最近忙着写一个其他的小玩意，好久没更新博客了，手痒更新一下： 本期来讲一讲C++中的STL中的deque的底层实现原理。 deque的地位 STL中的deque的地位很高 主要原因是由于泛型思想和对于其他容器的影响， 因为queue以及stack都是基于deque实现的。 实现deque需要思考的几点 这次我没有向上篇博客一样提前查看 deque
阅读更多...
C++中的priority_queue和deque以及适配器

C++中的priority_queue和deque以及适配器

C++中的priority_queue和deque 一丶 priority_queue1.1 priority_queue的介绍1.2 priority_queue的使用1.3 priority_queue的模拟实现 二丶 deque2.1 deque的简单介绍2.2 deque的缺陷2.3 为什么要选择deque作为stack和queue的迭代器 三丶 容器适配器3.1 什么是适配器3.2
阅读更多...
贪心+树状数组，CF1579E2 - Array Optimization by Deque

贪心+树状数组，CF1579E2 - Array Optimization by Deque

一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 1579E2 - Array Optimization by Deque 二、解题报告 1、思路分析 很好想也很好证明的贪心 因为添加的顺序是确定的，我们每次只需决策放左边还是放右边 x放左边，那么贡献就是右边比x小的个数 x放右边，那么贡献就是左边比x大的个数
阅读更多...
【STL源码剖析】deque 的使用

【STL源码剖析】deque 的使用

别院深深夏席清，石榴开遍透帘明。 树阴满地日当午，梦觉流莺时一声。 目录 deque 的结构 deque 的迭代器剖析 deque 的使用 ​编辑 deque 的初始化 deque 的容量操作 deque 的访问操作  在 pos 位置插入另一个向量的 [forst，last] 间的数据​编辑 删除 [first，last] 之间的元素 assign的用法 deque 的优缺点
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2