双端队列

作者在 2008-10-28 17:08:38 发布以下内容
双端队列(JAVA)
双端队列就是一个两端都是结尾的队列队列的每一瑞都可以插入数据项和移除数据项。这些方法可以叫作insertLeft()和insertRight(),以及removeLeft()和removeRight()。如果严格禁止调用insertLeft()和removeLeft()方法(或禁用右段的操作),双端队列功能就和一样。禁止调用insertLeft()和removeRight()(或相反的另一对方法),它的功能就和队列一样了。双端队列队列相比,是一种多用途的数据结构,在容器类库中有时会用双端队列来提供队列两种功能。
数据结构 | 阅读 9490 次
文章评论,共1条
vfdff(作者)
2008-10-28 17:13
1
STL学习之——vector和deque<br />
http://blog.chinaunix.net/u1/51602/showart_1138909.html<br />
<br />
依据标准模板库(STL)-由惠普公司提供。<br />
基于ANSI/ISO标准C++,在windows平台(C++ Builder\Visual C++)和Unix平台(G++)测试通过。<br />
<br />
vector(向量):是一个灵巧的数组,自动调整大小,并提供方法在任意位置插入和删除元素,而且向量是模板化的,将int类型元素插入int类型向量的方法和将string类型元素插入string类型向量的方法是完全相同的。有了向量之后可能再也不想用数组了。<br />
向量比数组使用起来方便的多,向量是一个有限序列(连续存储)特色如下:<br />
<br />
给出序列中任何项的下标,可以在常数时间内完成访问或修改该下标对应的项。<br />
在向量尾部插入元素平均只需要常数时间,其中worstTime(n)是O(n),n代表序列中项的数量。<br />
对序列尾部进行的删除操作,worstTime(n)是常数。<br />
任意的插入和删除,worstTime(n)和averageTime(n)都是是O(n)<br />
实例:<br />
&nbsp;&nbsp;&nbsp; vector&lt;string&gt;words;<br />
&nbsp;&nbsp;&nbsp; string word;<br />
&nbsp;&nbsp;&nbsp; for (int i = 0; i &lt; 5; i++)<br />
&nbsp;&nbsp;&nbsp; {<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cin &gt;&gt; word;<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;words.push_back (word);<br />
&nbsp;&nbsp;&nbsp; } // reading in words<br />
&nbsp;&nbsp;&nbsp; words.erase (words.begin());<br />
&nbsp;&nbsp;&nbsp; words.pop_back();<br />
&nbsp;&nbsp;&nbsp; for (unsigned i = 0; i &lt; words.size(); i++)<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cout &lt;&lt; words [i] &lt;&lt; endl;<br />
<br />
deque(双端队列):队列(double end queue双端队列)和向量很相似,但是实现细节上有较大的差别。<br />
双端队列是一个有限序列,特色如下:<br />
<br />
给出序列中任何项的下标,可以在常数时间内完成访问或修改该下标对应的项(与向量相同)。<br />
平均情况下,在序列头或尾部插入只耗费常数时间,但是worstTime(n)是O(n),n代表序列中项的数量。(与向量不同,向量在头部插入代价比较大)<br />
对序列尾部进行的插入和删除操作,worstTime(n)是常数。<br />
任意的插入和删除,worstTime(n)和averageTime(n)都是是O(n)<br />
由此可见,双端队列对象可以在他自身的首尾快速的插入和删除,而向量对象只有在尾部才能快速的插入和删除。deque类比vector类多了两个方法:<br />
//在双端队列的开头插入一个x的拷贝,averageTime(n)是常数,worstTime(n)是O(n)<br />
void push_front(const T&amp; x);<br />
//删除双端队列开头的项,worstTime(n)是常数<br />
void pop_front();<br />
实例:<br />
&nbsp;&nbsp;&nbsp; deque&lt;string&gt;words;<br />
&nbsp;&nbsp;&nbsp; string word;<br />
&nbsp;&nbsp;&nbsp; for (int i = 0; i &lt; 5; i++)<br />
&nbsp;&nbsp;&nbsp; {<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cin &gt;&gt; word;<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;words.push_back (word);<br />
&nbsp;&nbsp;&nbsp; } // for<br />
&nbsp;&nbsp;&nbsp; words.pop_front( );<br />
&nbsp;&nbsp;&nbsp; words.pop_back( );<br />
&nbsp;&nbsp;&nbsp; for (unsigned i = 0; i &lt; words.size(); i++)<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cout &lt;&lt; words [i] &lt;&lt; endl;<br />
总结:<br />
除非大多数操作都位于或者接近容器的开头,否则向量是比双端队列快的。向量比数组功能强大的多。向量自动调整大小,当超出当前容量时候就创建一个双倍大小的数组,并把向量copy到这个大的数组里。更大的优势在于插入和删除。
游客请输入验证码
浏览1936642次