双端队列 订阅
deque(double-ended queue,双端队列)是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出,相比list增加[]运算符重载。 展开全文
deque(double-ended queue,双端队列)是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出,相比list增加[]运算符重载。
信息
全    名
double-ended queue
类    型
具有队列和栈的性质的数据结构
中文名
双端队列
外文名
deque
deque基本含义
deque (double-ended queue,双端队列)是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行。双端队列是限定插入和删除操作在表的两端进行的线性表。这两端分别称做端点1和端点2。也可像栈一样,可以用一个铁道转轨网络来比喻双端队列。在实际使用中,还可以有输出受限的双端队列(即一个端点允许插入和删除,另一个端点只允许插入的双端队列)和输入受限的双端队列(即一个端点允许插入和删除,另一个端点只允许删除的双端队列)。而如果限定双端队列从某个端点插入的元素只能从该端点删除,则该双端队列就蜕变为两个栈底相邻的栈了。
收起全文
精华内容
下载资源
问答
  • 双端队列

    2021-07-10 19:17:33
    一、双端队列的定义 二、双端队列代码实现 1、定义节点 2、队首入队 3、队尾入队 4、队首出队 5、队尾出队 6、输出队列 7、主函数 8、最终效果展示 一、双端队列的定义 双端队列(deque,全名double-...

    目录

    一、双端队列的定义

    二、双端队列代码实现 

    1、定义节点

    2、队首入队

    3、队尾入队

    4、队首出队

    5、队尾出队

    6、输出队列

    7、主函数

    8、最终效果展示


    一、双端队列的定义

    双端队列(deque,全名double-ended queue)是一种具有队列和栈的性质的数据结构。双端队列的队首和队尾都满足栈先进后出的原则。它队首和队尾都支持入队和出队的操作。

    双端队列图:

     

     


    二、双端队列代码实现 

    注意:从双端队列图可以看出不管是队头还是队尾都符合栈先进后出的原则。

    1、定义节点

    public  class Node{
    		private String element;
    		private Node prev;
    		private Node next;
    		 Node(Node prev,String element,Node next) {
    			this.prev =prev;
    			this.element=element;
    			this.next=next;
    		}
    	}
    	private Node first;//第一个节点
    	private Node last;//最后一个节点

    2、队首入队

    public void First_Push(String elem) {
    		Node firsts=first;//将首节点赋值给firsts
    		Node node=new Node(null,elem,firsts);//调用node创建新节点
    		first=node;//新节点赋值给第一个节点
    		if(firsts == null) {//判断首节点是否是null如果是就把新节点赋值给尾节点
    			last=node;
    		}else {//首节点非空则把首节点的前指针指向新创建的节点实现队首插入的效果
    			firsts.prev=node;
    		}
    	}

    3、队尾入队

    	public void Last_Push(String elem) {
    		Node lasts=last;//将尾节点赋值给lasts
    		Node node = new Node(lasts,elem,null);//调用node创建新节点
    		last =node;//新节点赋值给最后一个节点
    		if(lasts == null) {//判断尾节点是否是null如果是就把新节点赋值给首节点
    			first=node;
    		}else {//尾节点非空则把尾节点的后指针指向新创建的节点实现队尾插入的效果
    			lasts.next = node;
    		}
    	}

    4、队首出队

    	public String First_Pop() {
    		if(first == null)return null;//如果队首是空则表示该队列没有任何数据返回null
    		Node firsts =first;//将第一个节点赋值给firsts
    		String element =firsts.element;//将第一个节点的数据赋值给element
    		Node next = firsts.next;//将第一个节点的下一位赋值给next节点
    		firsts.element = null;
            firsts.next = null;
            first=next;//将下一个节点赋值给第一个节点实现出队的效果
            if (next == null)//如果下一个节点是空则直接将最后一个节点赋值为null
                last = null;
            else
                next.prev = null;//如果下一个节点非空,则把该节点前指针指向null
            return element;
    	}

    5、队尾出队

    public String Lats_Pop() {
            if (last == null) return null;//如果队尾是空则表示该队列没有任何数据返回null
            Node lasts = last;//将最后一个节点赋值给lasts
            String element = lasts.element;//将最后一个节点的数据赋值给element
            Node prev = lasts.prev;
            lasts.element = null;
            lasts.prev = null;
            last = prev;//将前一个节点赋值给最后一个节点实现出队的效果
            if (prev == null)//如果前一个节点是空则直接将第一个节点赋值为null
                first = null;
            else
                prev.next = null;//如果前一个节点非空,则把该节点后指针指向null
            return element;
        }

    6、输出队列

     public void print() {
    		 Node firsts =first;
    	        while (firsts !=null){
    	            System.out.print(firsts.element);
    	            if(firsts.next!=null)System.out.print("->");
    	            firsts = firsts.next;
    	        }
    	    }

    7、主函数

    public static void main(String[] args) {
    		DoubleEndsQueue deq = new DoubleEndsQueue();
    		deq.First_Push("1");
    		deq.Last_Push("3");
    		deq.First_Push("2");
    		deq.First_Push("5");
    		System.out.print("入队之后的队列:");
    		deq.print();
    		System.out.println();
    		String pop=deq.First_Pop();
    		System.out.println("弹出"+pop);
    		deq.print();
    		
    	}

    8、最终效果展示

     

     

    展开全文
  • 彻底搞懂双端队列及输入/输出受限的双端队列

    千次阅读 多人点赞 2020-04-17 19:27:42
    文章目录双端队列相关概念双端队列应用设有一个双端队列,元素进入该队列的顺序是1,2,3,4试分别求出满足下列条件的输出序列。1.不可能通过输入受限的双端队列输出的序列是?2.不可能通过输出受限的双端队列输出的...

    双端队列相关概念

    双端队列:两端都可以进行入队和出队操作的队列。
    栈:限制其一端既不允许插入也不允许删除。
    普通队列:限制其一端不允许插入,而限制另一端不允许删除。

    在这里插入图片描述
    输入限制的双端队列:限制一端只能进行删除操作,而另一端不做限制,也就是说插入(输入)操作受到了限制。
    在这里插入图片描述

    输出限制的双端队列:限制一端只能进行插入操作,而另一端不做限制,也就是说删除(输出)操作受到了限制。
    在这里插入图片描述

    双端队列应用

    设有一个双端队列,元素进入该队列的顺序是1,2,3,4试分别求出满足下列条件的输出序列。
    1.不可能通过输入受限的双端队列输出的序列是?

    先使左端既不能输入,也不能输出,即成了一个栈,看此时不可能的输出序列有10种。
    在这里插入图片描述
    现在把左端的限制重新放开,就可以导出这10种中的一部分,剩下的就是不可导出的部分了。
    在这里插入图片描述
    下面一第一组1、4、2、3输出序列为例说明:

    在这里插入图片描述

    注:其中I代表输入操作,OL代表从左端输出,OR代表从右端输出。

    显然第一组是可以输出的,其他同理就不在此赘述了。
    下面再以第八组4、2、1、3为例说明:
    在这里插入图片描述
    显然4输出后,无论从左端还是右端都无法输出2,所以这组不可输出。
    同理第九组也不可输出。
    所以最后不可能通过输入受限的双端队列输出的序列是第八组4、2、1、3和第九组4、2、3、1

    2.不可能通过输出受限的双端队列输出的序列是?

    与第一问同理,先使左端既不能输入,也不能输出,即成了一个栈,看此时不可能的输出序列有10种。
    在这里插入图片描述
    下面还是以第一组1、4、2、3输出序列为例说明:
    在这里插入图片描述
    由于2先于3出队,而且只能从右端输出,所以3只能从左端入队。
    显然第一组是可以输出的,其他同理就不在此赘述了。
    下面再以第七组4、1、3、2为例说明:

    在这里插入图片描述
    显然1输出后,本应先输出的3却只能跟在2后边输出,所以这组不可输出。
    同理第九组也不可输出。
    所以最后不可能通过输出受限的双端队列输出的序列是第七组4、1、3、2和第九组4、2、3、1

    3.既不能由输入受限的双端队列得到,也不能由输出受限的双端队列的输出序列?

    只有第九组4、2、3、1

    展开全文
  • 关于双端队列的基本概念和什么叫受限双端队列,请戳双端队列与受限双端队列。 本文主要通过一个经典的习题来分享一下受限双端队列的入队和出队情况。 设有一个双端队列,输入序列为1,2,3,4,试分别求出以下条件的...

    目录

    1、左边完全受限的双端队列(右边完全受限的双端队列一样)

    2、输入受限的双端队列(队首在后端)

    3、输出受限的双端队列(前端相当于栈,后端相当于队列,就是头挨着的意思,序列从中间分开,两边必须是向端方向单调递增。)


    关于双端队列的基本概念和什么叫受限双端队列,请戳双端队列与受限双端队列

    本文主要通过一个经典的习题来分享一下受限双端队列的入队和出队情况。


    设有一个双端队列,输入序列为1,2,3,4,试分别求出以下条件的输出序列。
    (1)能由输入受限的双端队列得到,但不能由输出受限的双端队列得到的输出序列
    (2)不能由输入受限的双端队列得到,但能由输出受限的双端队列得到的输出序列
    (3)既不能由输入受限的双端队列得到,又不能由输出受限的双端队列得到的输出序列

     

    看完是不是有点想打人,那我们从容易到简单把这个题拆分来说一说。

     

    设有一个双端队列,元素进入该队列的顺序是1,2,3,4,试分别求出满足下列条件的输出序列。

    1、左边完全受限的双端队列(右边完全受限的双端队列一样)

    就相当于一个栈,栈底是左端,栈顶是右端,输出序列我们暂时记为A1,A2,A3,A4。

    最重要的结论来了,当Ai = N (i,N为1到4的正整数),比Ai先入栈的元素在输出序列中的顺序必须和入栈顺序相反,依次出栈。

    比如输出为3,*,*,*;  则后面三个未知序列中不允许出现1在2前面输出。  因为以3开头说明3是第一个出栈的元素,而1只能在2出栈之后才有可能出栈

    这个规律是顺延到后面的每一位,比如输出为1。*,*,*。则后面三个数字剩余2,3,4这三个数,如果4在头,那后面两位只能是3,2,不能是2,3这种(好绕,不知道我有没有说清楚,没搞清楚的多读两遍,琢磨琢磨)

    所以不可能的序列就有

    4,1,2,3

    4,1,3,2

    4,2,1,3

    4,2,3,1

    4,3,1,2

    3,1,2,4

    3,1,4,2

    3,4,1,2

    2,4,1,3

    1,4,2,3

    总共有10种。则满足的序列为剩余的 4!- 10 = 14种。

    2、输入受限的双端队列(队首在后端)

    我们的队列入队还是只有一端入队,为1,2,3,4;出队是可以两端任意出队。

    我们在第一步的基础上只需要分析,第一种不能出队的那10种情况现在哪些可以了就行。

    4,1,2,3    √

    4,1,3,2    √

    4,2,1,3    4先出队,说明是等完全入队之后才开始出队,所以只能走4后面只能跟1或者3   ×

    4,2,3,1    ×

    4,3,1,2    √

    3,1,2,4     √

    3,1,4,2     √

    3,4,1,2     √

    2,4,1,3    因为入队顺序是1,2,3,4,;所以如果2是第一个出队,只能是从右边出队,而且是在2入队之后,3入队之前这个时间点。 √

    1,4,2,3    完全入队之后左右间隔出队即可 √

    综上所述,输入受限的双端队列的可能的出队序列个数为 4!- 2 = 22;

    3、输出受限的双端队列(前端相当于栈,后端相当于队列,就是头挨着的意思,序列从中间分开,两边必须是向端方向单调递增。)

    与第二个输入受限的双端队列类似,我们输出受限的双端队列也建立在第一个左边完全受限的双端队列的基础上再进行分析。

    4,1,2,3    4开头说明4和1分别是前后端的队首,假定4在前端队首,而1,2,3依次从后端入队,则输出顺序正好满足√

    4,1,3,2    次序列要成立,4必须入前端,3,2可以入后端,但是1就没地方入队了,所以此序列有误。

    4,2,1,3    4,2,1| 3  √

    4,2,3,1     错误,还是那个道理,序列从中间分开,两边必须是向端方向单调递增。

    4,3,1,2    4,3 | 1,2

    3,1,2,4    //3往下的就不再解释

    3,1,4,2

    3,4,1,2

    2,4,1,3

    1,4,2,3

    综上所述,输出受限的双端队列的可能的出队序列个数为 4!- 2 = 22;

     

    看到这儿上面那个题也就不用说了吧,最后一个输出受限的双端队列,切记两端队列的头是挨着的,在中间,切记,切记!!!

     

     

     

    你,总要埋头去做一些事情,不是吗

     

     

     

     

     

     

     

     

    展开全文
  • 基于顺序表实现的顺序双端队列 基于链表实现的链式双端队列 一、说明 思路大致与队列相同,增添了从头部入队、尾部出队等操作。 再次感叹delete的耗时 二、基于顺序表实现的顺序双端队列 1、Deque.h #...
    • 说明
    • 基于顺序表实现的顺序双端队列
    • 基于链表实现的链式双端队列

    一、说明

    思路大致与队列相同,增添了从头部入队、尾部出队等操作。

    再次感叹delete的耗时

    二、基于顺序表实现的顺序双端队列

    1、Deque.h

    #include<iostream>
    using namespace std;
    #ifndef _Deque
    #define _Deque
    namespace wangzhe
    {
    	template<typename E>
    	class Deque
    	{
    		private:
    		        void operator = (const Deque&) {}
    		        Deque(const Deque&) {}
    		public:
    			Deque() {}
    			virtual ~Deque() {}
    			virtual void clear() =0;
    			virtual void Push_back(const E&) =0;
    			virtual void Push_front(const E&) =0;
    			virtual E Pop_back() =0;
    			virtual E Pop_front() =0;
    			virtual const E& frontValue() const =0;
    			virtual const E& backValue() const =0;
    			virtual int length() const =0;
    	};
    }
    #endif

    2、ADeque.h

    #include<iostream>
    using namespace std;
    #include"Deque.h"
    #ifndef _ADeque
    #define _ADeque
    namespace wangzhe
    {
    	template<typename E>
    	class ADeque:public Deque<E>
    	{
    		private:
    			int maxSize;//最大容量
    		        int front;//头 
    		        int rear;//尾 
    		        E *listArray;//表 
    		public:
    			ADeque(int size) ;//构造函数 
    			~ADeque() ;//析构函数 
    			void clear() ;//清空元素 
    			void Push_back(const E& it) ;//从尾部入队 
    			void Push_front(const E& it) ;//从头部入队 
    			E Pop_back() ;//从尾部出队 
    			E Pop_front() ;//从头部出队 
    			const E& frontValue() const ;//返回头部元素值 
    			const E& backValue() const ;//返回尾部元素值 
    			int length() const ;//元素个数 
    	};
    }
    #endif

    3、ADeque.cpp

    #include<iostream>
    using namespace std;
    #include"ADeque.h"
    namespace wangzhe
    {
    	template<typename E>
    	ADeque<E>::ADeque(int size)
    	{
    		maxSize=size+1;
    		front=1;
    		rear=0;
    		listArray=new E[maxSize];
    	}
    	
    	template<typename E>
    	ADeque<E>::~ADeque()
    	{
    		delete [] listArray;
    	}
    	
    	template<typename E>
    	void ADeque<E>::clear()
    	{
    		rear=0;
    		front=1;
    	}
    	
    	template<typename E>
    	void ADeque<E>::Push_back(const E& it)
    	{
    		if((rear+2)%maxSize==front)
    		{
    			cout<<"Deque is full"<<endl;
    			return;
    		}
    		rear=(rear+1)%maxSize;
    		listArray[rear]=it;
    	}
    	
    	template<typename E>
    	void ADeque<E>::Push_front(const E& it)
    	{
    		if((rear+2)%maxSize==front)
    		{
    			cout<<"Deque is full"<<endl;
    			return;
    		}
    		front=(front-1)%maxSize;
    		listArray[front]=it;
    	}
    	
    	template<typename E>
    	E ADeque<E>::Pop_back()
    	{
    		if(length()==0)
    		{
    			cout<<"Deque is empty"<<endl;
    			return -1;//以-1作为出错的返回值,不严谨 
    		}
    		E it=listArray[rear];
    		rear=(rear-1)%maxSize;
    		return it;
    	}
    	
    	template<typename E>
    	E ADeque<E>::Pop_front()
    	{
    		if(length()==0)
    		{
    			cout<<"Deque is empty"<<endl;
    			return -1;//以-1作为出错的返回值,不严谨 
    		}
    		E it=listArray[front];
    		front=(front+1)%maxSize;
    		return it;
    	}
    	
    	template<typename E>
    	const E& ADeque<E>::frontValue() const
    	{
    		if(length()==0)
    		{
    			cout<<"Queue is empty"<<endl;
    			return -1;//以-1作为出错的返回值,不严谨 
    		}
    		return listArray[front];
    	}
    	
    	template<typename E>
    	const E& ADeque<E>::backValue() const
    	{
    		if(length()==0)
    		{
    			cout<<"Queue is empty"<<endl;
    			return -1;//以-1作为出错的返回值,不严谨 
    		}
    		return listArray[rear];
    	}
    	
    	template<typename E>
    	int ADeque<E>::length() const
    	{
    		return ((rear+maxSize)-front+1)%maxSize;
    	}
    }

    4、main.cpp

    #include <iostream>
    using namespace std;
    /* run this program using the console pauser or add your own getch, system("pause") or input loop */
    #include"ADeque.h"
    #include"ADeque.cpp"
    using namespace wangzhe;
    int main(int argc, char** argv) 
    {
    	ADeque<int> a(5);
    	a.Push_back(9);
    	cout<<a.frontValue()<<endl ;
    	a.Push_front(8); 
    	cout<<a.frontValue()<<endl ;
    	a.Push_back(2);
    	cout<<a.backValue()<<endl ;
    	a.Push_back(3);
    	a.Push_back(4);
    	a.Push_back(5);
    	a.Push_back(6);
    	cout<<a.length() <<endl;
    	return 0;
    }

     

    三、基于链表实现的链式双端队列

    1、Link.h

    #include <iostream>
    using namespace std;
    #ifndef _Link
    #define _Link
    namespace wangzhe
    {
    	template<typename E> 
    	class Link
    	{
    	    public:
    		    E element;
    			Link *next;
    			Link(const E& elemval,Link* nextval =NULL)
    			{
    			    element=elemval;
    				next=nextval;	
    			}	
    			Link(Link* nextval=NULL)
    			{
    				next=nextval;
    			}
    	};
    }
    #endif

    2、Deque.h

    同顺序表

    3、LDeque.h

    #include<iostream>
    using namespace std;
    #include"Link.h"
    #include"Deque.h"
    #ifndef _LDeque
    #define _LDeque
    namespace wangzhe
    {
    	template<typename E>
    	class LDeque:public Deque<E>
    	{
    		private:
    			Link<E>* front;
    			Link<E>* rear;
    			int size;
    		public:
    			LDeque() ;//构造函数 
    			~LDeque() ;//析构函数 
    			void clear() ;//清空元素 
    			void Push_back(const E& it) ;//从尾部入队 
    			void Push_front(const E& it) ;//从头部入队 
    			E Pop_back() ;//从尾部出队 
    			E Pop_front() ;//从头部出队 
    			const E& frontValue() const ;//返回头部元素值 
    			const E& backValue() const ;//返回尾部元素值 
    			int length() const ;//元素个数 
    	};
    }
    #endif

    4、LDeque.cpp

    #include<iostream>
    using namespace std;
    #include"LDeque.h"
    namespace wangzhe
    {
    	template<typename E>
    	LDeque<E>::LDeque()
    	{
    		front=rear=new Link<E>();
    		size=0;
    	}
    	
    	template<typename E>
    	LDeque<E>::~LDeque()
    	{
    		clear();
    		delete front;
    	}
    	
    	template<typename E>
    	void LDeque<E>::clear()
    	{
    		/*while(front->next!=NULL)
    		{
    			rear=front->next;
    			delete rear;
    		}
    		rear=front;*/
    		rear=front;
    		front->next=NULL;
    		size=0;
    	}
    	
    	template<typename E>
    	void LDeque<E>::Push_back(const E& it)
    	{
    		rear=rear->next=new Link<E>(it,NULL);
    		size++;
    	}
    	
    	template<typename E>
    	void LDeque<E>::Push_front(const E& it)
    	{
    		front->next=new Link<E>(it,front->next);
    		size++;
    	}
    	
    	template<typename E>
    	E LDeque<E>::Pop_front()
    	{
    		if(size==0)
    		{
    			cout<<"Queue is empty"<<endl;
    			return -1;//以-1作为出错的返回值,不严谨 
    		}
    		Link<E>* temp=front->next;
    		E it=temp->element;
    		front->next=temp->next;
    		if(rear==temp) rear=front;
    		//delete temp;
    		size--;
    		return it;
    	}
    	
    	template<typename E>
    	E LDeque<E>::Pop_back()
    	{
    		if(size==0)
    		{
    			cout<<"Queue is empty"<<endl;
    			return -1;//以-1作为出错的返回值,不严谨 
    		}
    		E it=rear->element;
    		Link<E>* temp=front->next;
    		while(temp->next!=rear) 
    		{
    			temp=temp->next;
    		}
    		//delete rear;
    		rear=temp;
    		size--;
    		return it;
    	}
    	
    	template<typename E>
    	const E& LDeque<E>::frontValue() const
    	{
    		if(size==0)
    		{
    			cout<<"Queue is empty"<<endl;
    			return -1;//以-1作为出错的返回值,不严谨
    		}
    		return front->next->element;
    	}
    	
    	template<typename E>
    	const E& LDeque<E>::backValue() const
    	{
    		if(size==0)
    		{
    			cout<<"Queue is empty"<<endl;
    			return -1;//以-1作为出错的返回值,不严谨
    		}
    		return rear->element;
    	}
    	
    	template<typename E>
    	int LDeque<E>::length() const
    	{
    		return size;
    	}
    }

    5、main.cpp

    同顺序表

    展开全文
  • 队列 双端队列 双端队列接口 (Deque Interface) In Java, the Deque interface is under java.util.Deque and it is a subtype of java.util.Queue interface. A Deque is a double-ended queue that means ...
  • 双端队列:使用两个旋转列表的快速边界双端队列
  • 双端队列,是一种具有队列和栈的性质的数据结构 双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队 双端队列的实现 操作: Deque()创建一个空的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 39,668
精华内容 15,867
关键字:

双端队列