⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 2_2 队列 - 《多任务下的数据结构与算法》 - 免费试读 - book_csdn_net.htm

📁 主要介绍了多任务下面的一些数据结构和算法,比如树和图的一些遍历
💻 HTM
📖 第 1 页 / 共 5 页
字号:
🔍
12345 
    <TD 
    style="BORDER-RIGHT: windowtext 1pt solid; PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 62.9pt; BORDER-TOP-COLOR: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 33.75pt; BACKGROUND-COLOR: transparent" 
    width=84>
      <P style="LINE-HEIGHT: 14pt">STL∷deque</P></TD>
    <TD 
    style="BORDER-RIGHT: windowtext 1pt solid; PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 112.1pt; BORDER-TOP-COLOR: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 33.75pt; BACKGROUND-COLOR: transparent" 
    width=149>
      <P style="LINE-HEIGHT: 14pt">STL中的缺省值(4 096字节)</P></TD>
    <TD 
    style="BORDER-RIGHT: windowtext 1pt solid; PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 148.85pt; BORDER-TOP-COLOR: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 33.75pt; BACKGROUND-COLOR: transparent" 
    width=198>
      <P style="LINE-HEIGHT: 14pt">重复20 000次执行插入100个整</P>
      <P style="LINE-HEIGHT: 14pt">数再弹出100个的过程</P></TD>
    <TD 
    style="PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 71.4pt; BORDER-TOP-COLOR: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 33.75pt; BACKGROUND-COLOR: transparent; BORDER-RIGHT-COLOR: #ebe9ed" 
    width=95>
      <P style="LINE-HEIGHT: 14pt; TEXT-ALIGN: center" 
align=center>110</P></TD></TR>
  <TR style="HEIGHT: 33.75pt">
    <TD 
    style="BORDER-RIGHT: windowtext 1pt solid; PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 62.9pt; BORDER-TOP-COLOR: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 33.75pt; BACKGROUND-COLOR: transparent" 
    width=84>
      <P style="LINE-HEIGHT: 14pt">STL∷deque</P></TD>
    <TD 
    style="BORDER-RIGHT: windowtext 1pt solid; PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 112.1pt; BORDER-TOP-COLOR: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 33.75pt; BACKGROUND-COLOR: transparent" 
    width=149>
      <P style="LINE-HEIGHT: 14pt">STL中的缺省值(4 096字节)</P></TD>
    <TD 
    style="BORDER-RIGHT: windowtext 1pt solid; PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 148.85pt; BORDER-TOP-COLOR: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 33.75pt; BACKGROUND-COLOR: transparent" 
    width=198>
      <P style="LINE-HEIGHT: 14pt">插入2 000 000个整数再全部弹出</P></TD>
    <TD 
    style="PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 71.4pt; BORDER-TOP-COLOR: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 33.75pt; BACKGROUND-COLOR: transparent; BORDER-RIGHT-COLOR: #ebe9ed" 
    width=95>
      <P style="LINE-HEIGHT: 14pt; TEXT-ALIGN: center" 
align=center>125</P></TD></TR>
  <TR style="HEIGHT: 33.75pt">
    <TD 
    style="BORDER-RIGHT: windowtext 1pt solid; PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 62.9pt; BORDER-TOP-COLOR: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 33.75pt; BACKGROUND-COLOR: transparent" 
    width=84>
      <P style="LINE-HEIGHT: 14pt">DeQue</P></TD>
    <TD 
    style="BORDER-RIGHT: windowtext 1pt solid; PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 112.1pt; BORDER-TOP-COLOR: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 33.75pt; BACKGROUND-COLOR: transparent" 
    width=149>
      <P style="LINE-HEIGHT: 14pt">环形队列大小128，map大小16</P></TD>
    <TD 
    style="BORDER-RIGHT: windowtext 1pt solid; PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 148.85pt; BORDER-TOP-COLOR: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 33.75pt; BACKGROUND-COLOR: transparent" 
    width=198>
      <P style="LINE-HEIGHT: 14pt">插入2 000 000个整数再全部弹出</P></TD>
    <TD 
    style="PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 71.4pt; BORDER-TOP-COLOR: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 33.75pt; BACKGROUND-COLOR: transparent; BORDER-RIGHT-COLOR: #ebe9ed" 
    width=95>
      <P style="LINE-HEIGHT: 14pt; TEXT-ALIGN: center" align=center>78</P></TD></TR>
  <TR style="HEIGHT: 33.75pt">
    <TD 
    style="BORDER-RIGHT: windowtext 1pt solid; PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 62.9pt; BORDER-TOP-COLOR: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 33.75pt; BACKGROUND-COLOR: transparent" 
    width=84>
      <P style="LINE-HEIGHT: 14pt">DeQue</P></TD>
    <TD 
    style="BORDER-RIGHT: windowtext 1pt solid; PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 112.1pt; BORDER-TOP-COLOR: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 33.75pt; BACKGROUND-COLOR: transparent" 
    width=149>
      <P style="LINE-HEIGHT: 14pt">环形队列大小1 024，map大小16</P></TD>
    <TD 
    style="BORDER-RIGHT: windowtext 1pt solid; PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 148.85pt; BORDER-TOP-COLOR: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 33.75pt; BACKGROUND-COLOR: transparent" 
    width=198>
      <P style="LINE-HEIGHT: 14pt">插入2 000 000个整数再全部弹出</P></TD>
    <TD 
    style="PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 71.4pt; BORDER-TOP-COLOR: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 33.75pt; BACKGROUND-COLOR: transparent; BORDER-RIGHT-COLOR: #ebe9ed" 
    width=95>
      <P style="LINE-HEIGHT: 14pt; TEXT-ALIGN: center" align=center>78</P></TD></TR>
  <TR style="HEIGHT: 33.75pt">
    <TD 
    style="BORDER-RIGHT: windowtext 1pt solid; PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 62.9pt; BORDER-TOP-COLOR: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 33.75pt; BACKGROUND-COLOR: transparent" 
    width=84>
      <P style="LINE-HEIGHT: 14pt">DeQue</P></TD>
    <TD 
    style="BORDER-RIGHT: windowtext 1pt solid; PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 112.1pt; BORDER-TOP-COLOR: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 33.75pt; BACKGROUND-COLOR: transparent" 
    width=149>
      <P style="LINE-HEIGHT: 14pt">环形队列大小128，map大小16</P></TD>
    <TD 
    style="BORDER-RIGHT: windowtext 1pt solid; PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 148.85pt; BORDER-TOP-COLOR: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 33.75pt; BACKGROUND-COLOR: transparent" 
    width=198>
      <P style="LINE-HEIGHT: 14pt">重复20 000次执行插入100个整</P>
      <P style="LINE-HEIGHT: 14pt">数再弹出100个的过程 </P></TD>
    <TD 
    style="PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 71.4pt; BORDER-TOP-COLOR: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 33.75pt; BACKGROUND-COLOR: transparent; BORDER-RIGHT-COLOR: #ebe9ed" 
    width=95>
      <P style="LINE-HEIGHT: 14pt; TEXT-ALIGN: center" 
  align=center>62</P></TD></TR></TBODY></TABLE></DIV>
<P 
style="LINE-HEIGHT: 15.8pt">需要注意的是，以上数据是在Windows操作系统上测出，由于是分时系统，测试时会受操作系统其他进程的影响，另外由于Malloc函数在系统内存碎片不同情况下所消耗的时间是不一样的，每次测出的时间可能都会有差异，因此时间值并不很精确，是测试多次后，取其出现频率最高的一个时间值。</P>
<H4 style="LINE-HEIGHT: 15.8pt">3. 测试结果分析</H4>
<P 
style="LINE-HEIGHT: 15.8pt">从上面测试结果可以看出，DeQue在队列中的元素总数低于其中的环形队列大小时，所花时间和Queue没有发生扩大及拷贝时的时间是一样的，DeQue在不断地分配和释放环形队列时，所花的时间为78ms，是DeQue在没有发生分配和释放环形队列时的1.26倍。STL∷deque效率是最低的了，主要原因是STL中使用了模板，如果改写成不使用模板，则应该和DeQue在不断分配和释放环形队列时所花的时间差不多。因此可以看出，使用多个环形队列来组成一个动态队列效果是最好的。虽然Queue在预先设定成很大值时效率很高，但是队列使用的空间一直是按最大的需求来设定的，实际上大部分情况下队列中的元素总数远小于最大值，会浪费很多空间，另外当空间不够时需要分配内存进行拷贝操作，在队列满时的插入耗时很大。</P>
<H3 style="LINE-HEIGHT: 15.8pt"><A name=_Toc122884719></A>2.2.6 各种队列的适用范围</H3>
<P 
style="LINE-HEIGHT: 15.8pt">Queue、STL∷deque、DeQue三个队列可以说各有特点，从时间效率上看，虽然有些差别，但它们的效率都是非常高的，实际上它们有不同的适用范围。</P>
<P 
style="LINE-HEIGHT: 15.8pt">Queue在到达最高峰后，空间不会减少，所以它占用的内存一直是按最大值来分配的，它的优点是作为固定长度的队列使用时，时间效率非常高，一旦队列大小超过预先分配的长度，就会出现重新分配内存并复制的情况，因此Queue的平均性能不是很好，它适用于队列最大空间不是很大的情况，具体大小取决于系统对内存使用的限制。</P>
<P>STL∷deque从算法上看非常符合队列的操作特性，当队列使用的空间用完后，只是简单地重新分配一块内存，但不会发生内存复制现象，因此它的平均性能比Queue好多了，空间使用上也比Queue好多了。它的空间使用是根据队列的大小动态进行调整的，不会出现到了高峰之后内存却一直被占用不释放的问题。其缺点是队列交替进行插入和弹出操作时，还是一直在分配和释放内存，和Queue比起来还需要一个额外的map，因此这种队列适用于队列元素较多的情况。</P>
<P>可以说DeQue是和STL∷deque的HP实现非常接近的一个队列，它的特点中很多地方和STL∷deque差不多，区别是DeQue多需要一些额外的空间，在队列交替进行插入和弹出操作时，DeQue不会出现分配和释放内存的情况，有很好的内存性能，因此DeQue适用于内存性能要求较高的场合。从空间的使用和时间效率方面综合考虑，DeQue是较优的队列，特别是在多任务环境下，许多服务器软件都是长时间运行的，对内存使用有很高的要求，此时用DeQue就有明显的优势。</P>
<H3><A name=_Toc122884720></A>2.2.7 关于时间效率和空间效率的原则</H3>
<P>本节中有两个地方涉及时间效率和空间效率的均衡，一个是环形队列的设计上，有一个元素空间未用；另一个是动态环形队列DeQue的设计上，相对STL∷deque多用了很多辅助的空间。那么到底什么情况下应该让空间效率优先呢？什么情况下应该让时间效率优先呢？在设计过程中总是有许多的软件人员为此烦恼，本书给出以下两条空间效率优先和时间效率优先原则作为参考。</P>
<P>设某模块消耗的全部空间大小为N，运行固定数量元素的全部操作时间为T，假设增加n个空间能够减少的运行时间为t，或者说减少n个空间会增加的运行时间为t，则有：</P>
<P>空间效率优先原则 如果 n / N &gt; K t / T，则应该考虑采用空间效率优先，即此时应该降低时间效率来提高空间效率。</P>
<P>时间效率优先原则 如果 n / N &lt; K t / T，则应该考虑采用时间效率优先，即此时应该降低空间效率来增加时间效率。</P>
<P>其中，K为常数，K的取值取决于对时间效率和空间效率的需求， 
一般情况下K可以取值为1，在内存受限的系统中，对空间效率比较敏感，K可以取大一些，而对空间没有太大限制的系统中则K的取值可小一些。</P>
<P>本节的DeQue设计中，当环形队列大小为1 024时，n / N = 
0.5%，而当队列元素总数小于DeQue中的环形队列大小时效率则提高了26％左右，显然符合时间效率优先原则。</P>
<P 
style="LINE-HEIGHT: 15.8pt">本节主要介绍了用数组来实现队列的设计和实现，这些都是在单任务下的实现，队列的多任务实现会放到第8章中进行介绍。另外队列也可以用链表来实现，用链表实现队列将在第3章中进行介绍，并会和本节实现的队列进行性能、效率等方面的对比分析。</P></DIV><!-- page -->
<DIV class=page style="TEXT-ALIGN: center"><A 
href="http://book.csdn.net/bookfiles/65/100651877.shtml">上一页</A>&nbsp;&nbsp;&nbsp;<A 
href="http://book.csdn.net/bookfiles/65/index.html">首页</A>&nbsp;&nbsp;&nbsp;<A 
href="http://book.csdn.net/bookfiles/65/100651879.shtml">下一页</A> </DIV>
<DIV 
style="BORDER-RIGHT: #0b5f98 1px solid; BORDER-TOP: #0b5f98 1px solid; MARGIN: 0px auto; BORDER-LEFT: #0b5f98 1px solid; WIDTH: 700px; BORDER-BOTTOM: #0b5f98 1px solid">
<DIV 
style="PADDING-RIGHT: 1px; PADDING-LEFT: 1px; FLOAT: left; PADDING-BOTTOM: 1px; WIDTH: 16px; COLOR: white; PADDING-TOP: 1px; BACKGROUND-COLOR: #0b5f98">图书导读 
</DIV>
<DIV 
style="PADDING-LEFT: 2px; FLOAT: right; WIDTH: 670px; LINE-HEIGHT: 16pt; TEXT-ALIGN: left"><!--导读-->
<H1 id=divCurrentNode2 
style="PADDING-LEFT: 2px; FONT-SIZE: 12px; WIDTH: 100%; COLOR: #b83507; TEXT-ALIGN: left">当前章节:<A 
href="http://book.csdn.net/bookfiles/65/100651878.shtml"><FONT color=red>2.2 队列 
</FONT></A></H1>
<DIV id=divRealteNod2 style="PADDING-LEFT: 2px">
<DIV style="FLOAT: left; WIDTH: 49%">·<A 
href="http://book.csdn.net/bookfiles/65/100651875.shtml">1.4 多任务介绍 </A></DIV>
<DIV style="FLOAT: right; WIDTH: 49%">·<A 
href="http://book.csdn.net/bookfiles/65/100651876.shtml">1.5 软件设计简介</A></DIV>
<DIV style="FLOAT: left; WIDTH: 49%">·<A 
href="http://book.csdn.net/bookfiles/65/100651877.shtml">2.1 栈 </A></DIV>
<DIV style="FLOAT: right; WIDTH: 49%">·<A 
href="http://book.csdn.net/bookfiles/65/100651879.shtml">2.3 排序表 </A></DIV>
<DIV style="FLOAT: left; WIDTH: 49%">·<A 
href="http://book.csdn.net/bookfiles/65/100651880.shtml">2.4 实例：HOOK管理功能的实现 
</A></DIV>
<DIV style="FLOAT: right; WIDTH: 49%">·<A 
href="http://book.csdn.net/bookfiles/65/100652553.shtml">5.1.1 
普通树的描述方法</A></DIV></DIV></DIV></DIV>
<DIV class=clear> </DIV></DIV>
<DIV class=todayCommend style="WIDTH: 100%">
<DIV class=title>
<H5>同类图书推荐</H5></DIV>
<DIV class="blank6 clear"></DIV>
<DIV class=content id=divSameSort>
<LI style="FLOAT: left; WIDTH: 20%"><A title="数据挖掘原理与应用—— SQL Server 2005数据库" 
href="http://book.csdn.net/bookfiles/242/"><IMG height=112 
src="2_2 队列 - 《多任务下的数据结构与算法》 - 免费试读 - book_csdn_net.files/TS00124727__.jpg" 
width=80 border=0></A>
<P><A title="数据挖掘原理与应用—— SQL Server 2005数据库" 
href="http://book.csdn.net/bookfiles/242/">数据挖掘原理与应用—...</A></P></LI>
<LI style="FLOAT: left; WIDTH: 20%"><A title="Oracle PL/SQL 专家指南" 
href="http://book.csdn.net/bookfiles/241/"><IMG height=112 
src="2_2 队列 - 《多任务下的数据结构与算法》 - 免费试读 - book_csdn_net.files/TS00124725__.jpg" 
width=80 border=0></A>
<P><A title="Oracle PL/SQL 专家指南" 
href="http://book.csdn.net/bookfiles/241/">Oracle PL/SQL 专家指...</A></P></LI>
<LI style="FLOAT: left; WIDTH: 20%"><A title="Microsoft SQL Server2005开发指南" 
href="http://book.csdn.net/bookfiles/240/"><IMG height=112 
src="2_2 队列 - 《多任务下的数据结构与算法》 - 免费试读 - book_csdn_net.files/TS00124697__.jpg" 
width=80 border=0></A>
<P><A title="Microsoft SQL Server2005开发
12345

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -