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++——stack、queue的实现及deque的介绍

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现
阅读更多...
C++提高编程三(vector容器、deque容器）

C++提高编程三(vector容器、deque容器）

文章目录 vector容器vector赋值操作vector容量和大小vector插入和删除vector数据存取vector互换容器vector预留空间deque容器构造函数deque赋值操作deque大小操作deque 插入和删除deque 数据存取deque 排序 vector容器 vector容器数据结构和数组相似，也称为单端数组。区别在于数组是静态空间，vector可以
阅读更多...
0902，DEQUE，LIST，VECTOR

0902，DEQUE，LIST，VECTOR

目录 01_vector.cc 02_vector.cc 作业 01STL包括哪些组件？各自具有哪些特点？ 02 序列式容器包括哪些？他们之间有哪些异同？ 03 下面程序有什么错误？ 04 创建和初始化vector的方法，每种都给出一个实例？当然也可以把deque与list写出来 05 如果c1与c2是两个容器，下面的比较操作有什么限制？if(c1 < c2) 06 STL中的s
阅读更多...
c++重拾STL之 队列：queue、deque

c++重拾STL之 队列：queue、deque

queue 头文件#include<queue> queue模板类两个模板参数：一个是元素类型，一个是容器类型，容器类型默认为deque类型。 1、定义queue对象： queue<int> q1; queue<BTNode*> q2 2、queue的基本操作 入队： q.push(x); 入到队尾出队：q.pop(); 弹出队列第一个元素，**注意，pop出队只是删除队头元素，并不会返
阅读更多...
[STL --stack_queue详解]stack、queue，deque,priority_queue

[STL --stack_queue详解]stack、queue，deque,priority_queue

stack stack介绍 1、stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。 2、stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。  stack的使用 常用操作： push尾部插
阅读更多...
【python笔记】deque()、list()、heapq主要区别

【python笔记】deque()、list()、heapq主要区别

内部实现 1、deque() deque是Python中的一个双端队列，位于collections模块中。 数据结构： deque 是一个双端队列，其内部实现基于一个双向链表。 这意味着元素不是连续存储在内存中的，而是分布在多个节点中，每个节点包含元素本身以及指向其前一个和后一个节点的链接。动态扩容： 虽然 deque 不需要像 list 那样复制整个数组来扩容，但它仍然需要管理链表的节点，并在
阅读更多...
std::vector,std::deque,std…

std::vector,std::deque,std…

原文地址：std::vector,std::deque,std::list的区别的使用 作者：xpddk vector    表示一段连续的内存区域，每个元素被顺序存储在这段内存中，对vector的随机访问效率很高，但对非末尾元素的插入和删除则效率非常低。 deque    也表示N段连续的内存区域组成，但与vector不同的是它支持高效地在其首部插入和删除元素，它通过两级
阅读更多...
C++系列-STL容器之deque

C++系列-STL容器之deque

STL容器之deque deque概括deque与vector内存管理的区别vector内存分配方式deque内存分配方式 deque与vector随机访问效率的区别deque与vector插入和删除操作的区别deque与vector适用场景 deque的构造函数deque的构造函数举例 deque的赋值操作deque容器的大小操作deque容器的插入和删除两端插入和删除指定位置删除操作 d
阅读更多...
STL容器deque 的常用功能和操作

STL容器deque 的常用功能和操作

在 C++ 的标准模板库（STL）中，std::deque（双端队列）是一种非常灵活且高效的容器。它允许在两端进行快速的插入和删除操作，非常适合需要在两端频繁操作的数据结构场景。与 std::vector 不同，std::deque 不是一个连续内存块的容器，而是由多个内存块构成，这使得它在两端操作时非常高效。 目录 deque的常见创建方式 deque常用成员函数  std::
阅读更多...
【C/C++笔记】从一个文件中讲取未知数目的整数。对这些整数排序，然后把它们输出到标准输出设备。选用vector、deque 还是 list？

【C/C++笔记】从一个文件中讲取未知数目的整数。对这些整数排序，然后把它们输出到标准输出设备。选用vector、deque 还是 list？

从一个文件中讲取未知数目的整数。对这些整数排序，然后把它们输出到标准输出设备。选用vector、deque 还是 list？ 在这个场景中，我们需要从一个文件中读取未知数目的整数，然后对这些整数进行排序并输出到标准输出设备。 选择 std::vector 理由 高效读取: 对于从文件中读取大量数据的情况，std::vector 可以一次性读取整个文件到一个大的连续的内存块中，这通常比逐个插
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2