Leetcode 641. 设计循环双端队列_wwxy261的博客-程序员宝宝

技术标签: 算法  

设计实现双端队列。
你的实现需要支持以下操作:

  • MyCircularDeque(k):构造函数,双端队列的大小为k。
  • insertFront():将一个元素添加到双端队列头部。 如果操作成功返回 true。
  • insertLast():将一个元素添加到双端队列尾部。如果操作成功返回 true。
  • deleteFront():从双端队列头部删除一个元素。 如果操作成功返回 true。
  • deleteLast():从双端队列尾部删除一个元素。如果操作成功返回 true。
  • getFront():从双端队列头部获得一个元素。如果双端队列为空,返回 -1。
  • getRear():获得双端队列的最后一个元素。 如果双端队列为空,返回 -1。
  • isEmpty():检查双端队列是否为空。
  • isFull():检查双端队列是否满了。

示例:

MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
circularDeque.insertLast(1);			        // 返回 true
circularDeque.insertLast(2);			        // 返回 true
circularDeque.insertFront(3);			        // 返回 true
circularDeque.insertFront(4);			        // 已经满了,返回 false
circularDeque.getRear();  				// 返回 2
circularDeque.isFull();				        // 返回 true
circularDeque.deleteLast();			        // 返回 true
circularDeque.insertFront(4);			        // 返回 true
circularDeque.getFront();				// 返回 4
 

 

提示:

  • 所有值的范围为 [1, 1000]
  • 操作次数的范围为 [1, 1000]
  • 请不要使用内置的双端队列库。

使用双向链表实现双端队列

class MyCircularDeque {
private:
	struct Node {

		int val;
		Node* next;
		Node* prev;

		Node(int val) {
			this->val = val;
			next = NULL;
			prev = NULL;
		}

	};

	Node* head;
	Node* tail;
	int size;
	int maxsize;



public:
	/** Initialize your data structure here. Set the size of the deque to be k. */
	MyCircularDeque(int k) {
		size = 0;
		maxsize = k;
		head = new Node(-1);
		tail = head;

	}

	/** Adds an item at the front of Deque. Return true if the operation is successful. */
	bool insertFront(int value) {
		if (size >= maxsize)
			return false;

		Node* node = new Node(value);
		if (head == tail) {
			// 当前队列为空
			head->next = node;
			node->prev = head;
			tail = node;
		}
		else {
			node->next = head->next;
			head->next->prev = node;
			head->next = node;
			node->prev = head;
		}
		size++;
		return true;
	}

	/** Adds an item at the rear of Deque. Return true if the operation is successful. */
	bool insertLast(int value) {
		if (size >= maxsize)
			return false;

		Node* node = new Node(value);
		if (head == tail) {
			// 空队列情况
			head->next = node;
			node->prev = head;
			tail = node;
		}
		else {
			tail->next = node;
			node->prev = tail;
			tail = node;
		}
		size++;
		return true;
	}

	/** Deletes an item from the front of Deque. Return true if the operation is successful. */
	bool deleteFront() {
		if (head==tail)
			return false;

		Node* temp = head->next;
		if (head->next == tail) {
			// 队列中只有一个元素
			
			delete(temp);
			head->next = NULL;
			tail = head;
		}
		else {
            
			head->next = temp->next;
			temp->next->prev = head;
			delete temp;
		}
		size--;
		return true;

	}

	/** Deletes an item from the rear of Deque. Return true if the operation is successful. */
	bool deleteLast() {
		if (head == tail)
			return false;

		Node* temp = tail;
		tail = temp->prev;
		tail->next = NULL;
		delete temp;
		size--;
		return true;

	}

	/** Get the front item from the deque. */
	int getFront() {

		return head->next == NULL ? -1 : head->next->val;

		/*if(head->next==NULL)
			return -1;
		return head->next->val;*/
	}

	/** Get the last item from the deque. */
	int getRear() {

		return head == tail ? -1 : tail->val;
		/*if(head==tail)
			return -1;
		return tail->val;*/
	}

	/** Checks whether the circular deque is empty or not. */
	bool isEmpty() {
		return head == tail;

	}

	/** Checks whether the circular deque is full or not. */
	bool isFull() {
		return size == maxsize;
	}
};

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/wwxy1995/article/details/87884594

智能推荐

自动驾驶地图数据传输协议ADASISv3介绍_adasis v3_武魂殿001的博客-程序员宝宝

1. 什么是 ADASIS v3?ADASIS(Advanced Driver Assistance Systems Interface Specification)直译过来就是 ADAS 接口规格,它要负责的东西其实很简单,就是为自动驾驶车辆提供前方道路交通相关的数据,这些数据被抽象成一个标准化的概念:ADAS Horizon。数据从地图应用来,要传输到车内的 ADAS 软件应用中。我们常见的互联网传输协议是 Http,内容封装协一般是 json、protocol buffer、xml 等等。但汽车中

计算机网络无线局域网设计,无线校园网设计全攻略_Zoe Vian的博客-程序员宝宝

随着无线局域网技术和无线产品的成熟,无线网络为校园网建设提出了新的可行的思路。无线局域网标准IEEE802.11g、b 能够与现有的计算机网络进行平滑无缝的连接,并能与现有的计算机网络和终端设备互联,与有线网络资源具有良好的兼容性和整合性。高校无线校园网现状据一项调查表明,截至目前,我国已经有15.1%的高校建有无线校园网,但绝大多数都属于试验性质,并没有广泛开放给学生使用。同时有36.2%的高校...

JDK1.8安装与环境变量的配置win7、win10都适用_手写的从前98的博客-程序员宝宝

1、下载java下载地址 https://www.oracle.com/technetwork/java/javase/downloads/index.html2、安装双击java安装包进行安装,过程如下。1)

CCFCSP201604-2俄罗斯方块_KgdYsg的博客-程序员宝宝

题目 http://118.190.20.162/view.page?gpid=T41问题描述   俄罗斯方块是俄罗斯人阿列克谢·帕基特诺夫发明的一款休闲游戏。   游戏在一个15行10列的方格图上进行,方格图上的每一个格子可能已经放置了方块,或者没有放置方块。每一轮,都会有一个新的由4个小方块组成的板块从方格图的上方落下,玩家可以操作板块左右移动放到合适的位置,当板块中某一个方块的下边缘与方

在windows 7 下安装oracle 10g数据库(转载+亲身经历)_weixin_30532759的博客-程序员宝宝

这几天装oracle我要痛苦死了,还好最后装成功了!到网上查了很多资料,整理如下:注意:安装前一定要把网断掉、防火墙关掉!!!!1.因为oracle 10g暂时没有与win7兼容的版本,我们可以通过对安装软件中某些文件的修改达到安装的目地。a)打开“\Oracle 10G \stage\prereq\db”路径,找到refhost.xml文件,打开,向其中添加如下代码并保存。&lt...

随便推点

成功解决CatBoostError: Invalid type for cat_feature cat_features must be integer or string, real number_一个处女座的程序猿的博客-程序员宝宝_catboosterror: invalid type for cat_feature[non-de

成功解决_catboost.CatBoostError: Invalid type for cat_feature[non-default value idx=0,feature_idx=0]=8.365 : cat_features must be integer or string, real number values and NaN values should be converted to string.成功解决CatBoostError: Invalid type for cat_feat

PHP 实现对象的持久层,数据库使用MySQL_weixin_33901641的博客-程序员宝宝

http://www.xuebuyuan.com/1236808.html心血来潮,做了一下PHP的对象到数据库的简单持久层。不常用PHP,对PHP也不熟,关于PHP反射的大部分内容都是现学的。目前功能比较弱,只是完成一些简单的工作,对象之间的关系还没法映射,并且对象的成员只能支持string或者integer两种类型的。成员变量的值也没有转义一下。。。下面就贴一下代码:首...

微信公众号JS-SDK开发_JiuShanCunMonkeyKing的博客-程序员宝宝_微信js开发

日常开发中,有时候会使用到微信的js,所以我们需要做JS-SDK开发,在这里记录一下JS-SDK开发过程在后台配置好JS安全域名,此处域名和上面网页授权的域名一致。配置完成后,在前端需要使用微信JS的页面上请求后台去验证签名是否正确,如果正确,后台返回签名等信息,然后前端再使用签名等信息调用wx.config,在wx.config里面jsApiList[]里面的就是我们需要用到的微信J...

python 100以内3的倍数,如何在Python中找到1000以下的3或5的所有倍数的和?_TKSJ的博客-程序员宝宝

Not sure if I should've posted this on math.stackexchange instead, but it includes more programming so I posted it here.The question seems really simple, but I've sat here for at least one hour now no..._1671465600

Python基础--01简介_小绅士的跟屁虫~的博客-程序员宝宝

一、解释器Python解释器作用:运行文件下载Python解释器下载地址https://www.python.org/downloads/release/python-372/二、PycharmPycharm的作用Pycharm是一种Python IDE(集成开发环境),带有一整套可以帮助用户在使用Python语言开发时提高其效率的工具,内部集成的功能如下:– Proj...

android平台下OpenGL ES 3.0绘制立方体的几种方式_handy周的博客-程序员宝宝_android opengles绘制正方体

绘制图元OpenGL ES中有5个绘制图元的API调用:glDrawArrays、gIDrawElements、glDrawRangeHonents、 glDrawArraysInstanced和glDrawElementsInstanced。glDrawArrays用元素索引为first到first+count-1的元素指定的顶点绘制mode指定的图元。调用glDrawArrays(GL...

推荐文章

热门文章

相关标签