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

主要介绍了多任务下面的一些数据结构和算法,比如树和图的一些遍历

  function getCookie(name){var arr=document.cookie.match(new RegExp("(^| )"+name+"=([^;]*)(;|$)"));
  if(arr!=null)return unescape(arr[2]);return null;}

  $mz_.logout=function(e){new Image().src=e.href; if($mz_.login_info) $mz_.log.innerHTML=$mz_.login_info;}
  $mz_.log=$("CSDNPH_line1");$mz_.login_info=$mz_.log.innerHTML; var user=getCookie("activeUserName");
  if(user && user!="Guest") $mz_.log.innerHTML = "欢迎 <strong>"+ user +"</strong>   "
    +"<a href='http://job.csdn.net/Con001_ProjectManage/Job/MyResume.aspx' target='_blank'>我的简历</a> | "
    +"<a href='http://community.csdn.net/Expert/member/MyForum.asp?typenum=1' target='_blank'>我的帖子</a> | "
    +"<a href='http://blog.csdn.net/"+ user +"/' target='_blank'>我的Blog</a> | "
    +"<a href='http://wz.csdn.net/my/' target='_blank'>我的网摘</a> | "
    +"<a href='http://club.book.csdn.net/people/myclub.aspx' target='_blank'>我的书架</a> "
    +"<a href='http://passport.csdn.net/logonout.aspx' onclick='$mz_.logout(this); return false'>【注销】</a>"
})();
/*]]>*/</SCRIPT>
</DIV><!-- -->
<SCRIPT src="2_2 队列 - 《多任务下的数据结构与算法》 - 免费试读 - book_csdn_net.files/urchin.js" 
type=text/javascript>
</SCRIPT>

<SCRIPT type=text/javascript>
_uacct = "UA-178341-4";
urchinTracker();
</SCRIPT>
<!-- /公共页头 --><LINK 
href="C:\Documents and Settings\K&amp;G\桌面\2_2 队列 - 《多任务下的数据结构与算法》 - 免费试读 - book_csdn_net.files\style(1).css" 
type=text/css rel=stylesheet>
<DIV id=booknav2>
<DIV id=booknavtop>
<UL>
  <LI><A href="http://book.csdn.net/">首页</A> </LI>
  <LI><A href="http://book.csdn.net/book/morelz.aspx">精品连载</A> </LI>
  <LI><A href="http://club.book.csdn.net/people/myclub.aspx">我的书友会</A> </LI>
  <LI><A href="http://club.book.csdn.net/people/putblog.aspx">图书秀</A> </LI>
  <LI><A href="http://club.book.csdn.net/people/alllist.aspx">书架</A> </LI>
  <LI><A href="http://blog.csdn.net/group/bookread/" target=_blank>圈子</A> </LI>
  <LI><A href="http://down.csdn.net/app/list.php?tid=502" target=_blank>资源下载</A> 
  </LI>
  <LI><A href="http://bank.csdn.net/" target=_blank><FONT 
  style="FONT-WEIGHT: bold">银行</FONT></A> </LI></UL></DIV>
<SCRIPT type=text/javascript>
     function IsBlank(obj) //查看对象的值是否为空
    {
      if(obj.replace(/^\s+|\s+$/,"")=="")
		  {
		 
		    return true; 
		  }
		  else
		  {
		   return false;
		  }
		  
     }
    function SearchBook_Top()
    {
      if( !IsBlank(document.getElementById("txtTopKey").value))
      {
         var loc;
         var szType;
         if(document.getElementById("listSearchType").value==null)
          {    
            szType=  document.getElementById("listSearchType").options(document.getElementById("listSearchType").selectedIndex).value;  
          }
          else
          {
              szType= document.getElementById("listSearchType").value;
          }
          if(szType==1)
            loc="http://book.csdn.net/book/morelz.aspx?key="+escape(document.getElementById("txtTopKey").value);
          else
             loc="http://club.book.csdn.net/book/s.aspx?key="+escape(document.getElementById("txtTopKey").value);
          
          self.location=loc;
        
      } 
    }
  </SCRIPT>

<DIV id=booknavbottom2>
<DIV class=hotleft><A href="http://book.csdn.net/subject/allbook.htm" 
target=_blank>全部图书</A> <FONT color=red>推荐</FONT>:<A 
href="http://club.book.csdn.net/book/s.aspx?key=asp.net">ASP.NET</A> <A 
href="http://club.book.csdn.net/book/s.aspx?key=ajax">Ajax</A> <A 
href="http://club.book.csdn.net/book/s.aspx?key=spring">Spring</A> <A 
href="http://club.book.csdn.net/book/s.aspx?key=Hibernate">Hibernate</A> <A 
href="http://club.book.csdn.net/book/s.aspx?key=Java">Java</A></DIV>
<DIV class=hotright><SELECT id=listSearchType name=aa> <OPTION value=2 
  selected>书友会</OPTION> <OPTION value=1>连载</OPTION></SELECT><INPUT 
onkeypress=if(event.keyCode==13){SearchBook_Top();} id=txtTopKey maxLength=25><INPUT onclick=SearchBook_Top(); type=button value=搜索 name=提交></DIV></DIV></DIV>
<DIV class=area>
<SCRIPT 
src="2_2 队列 - 《多任务下的数据结构与算法》 - 免费试读 - book_csdn_net.files/BookDetailAd.js" 
type=text/javascript></SCRIPT>

<DIV class=col1>
<DIV class=lineBlue></DIV><!-- title -->
<DIV class=arcTitle>
<H1><A href="http://book.csdn.net/bookfiles/65">多任务下的数据结构与算法 </A></H1>
<DIV style="FONT-SIZE: 15px; TEXT-ALIGN: center"><A 
href="http://book.csdn.net/bookfiles/65/100651878.shtml">2.2 队列 </A></DIV>
<DIV style="FONT-SIZE: 15px; TEXT-ALIGN: center"><A class=url 
href="http://book.csdn.net/">http://book.csdn.net/</A> 2006-7-14 18:04:00 </DIV>
<DIV class=clear></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=divCurrentNode 
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=divRelateNode 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><!-- main -->
<DIV id=main>
<DIV id=text>
<DIV id=csdn_zhaig_ad_yahoo_2></DIV>
<H2><A name=_Toc122884713></A><A name=_Toc116222471><FONT size=5>2.2 
</FONT></A>队列</H2>
<H3 style="LINE-HEIGHT: 15.5pt"><A name=_Toc122884714></A><A 
name=_Toc116222472></A>2.2.1 队列的基本概念和接口</H3>
<P 
style="LINE-HEIGHT: 15.5pt">队列是一种先进先出(first-in-first-out，FIFO)的数据结构类型，它和栈的区别是：栈是后进先出，而队列的进出方向刚好和栈相反。一般来讲，添加新元素的那一端被称作队尾，而弹出元素的那一端被称作队首。</P>
<P style="LINE-HEIGHT: 15.5pt">根据队列的操作特性，一个队列至少应该提供下列接口。</P>
<P style="LINE-HEIGHT: 15.5pt">① 创建一个空的队列；</P>
<P style="LINE-HEIGHT: 15.5pt">② 判断队列是否为空；</P>
<P style="LINE-HEIGHT: 15.5pt">③ 判断队列是否为满；</P>
<P style="LINE-HEIGHT: 15.5pt">④ 进队操作(向队列尾部添加元素)；</P>
<P style="LINE-HEIGHT: 15.5pt">⑤ 出队操作(从队列中弹出头部元素)；</P>
<P style="LINE-HEIGHT: 15.5pt">⑥ 释放整个队列。</P>
<P 
style="LINE-HEIGHT: 15.5pt">其中第5个接口多数情况下被分解成两个接口，即获取队首元素接口和删除队首元素接口，分解成两个接口的好处是功能上更加完整，具有更好的扩展性。其缺点是队列的出队操作需要调用获取队首元素和删除队首元素两个接口来完成，效率上会受影响，使用起来也没有直接用一个弹出队首元素的接口方便。本书中对出队操作只实现一个弹出队首元素的接口。</P>
<P 
style="LINE-HEIGHT: 15.5pt">从队列的特性我们知道队列是一个线性表，并且其中的元素是按进队的先后次序排列的。数组是一个连续的空间，操作起来效率非常高，能不能用数组来实现队列的操作呢？本节将介绍三种用数组来实现队列的方法：第一种是普通的环形队列(Queue)，其中还会讲解如何将环形队列由固定长度队列变成可以动态增长的队列；第二种是HP实现的STL中的动态队列(STL∷deque)；第三种是作者自己设计的动态环形队列(DeQue)。最后会对三种队列的时间效率、空间效率和性能方面进行比较，明确各种队列的适用范围，并结合本节内容讲解时间效率和空间效率的一般性优先原则，供读者设计其他商业性应用模块时作为参考。</P>
<H3><A name=_Toc122884715></A><A name=_Toc116222473></A>2.2.2 环形队列(Queue)</H3>
<H4>1. 数组实现队列的方法</H4>
<P>数组的特点是插入或删除数据不在尾部时效率特别低，需要移动大量的数据，这是首先要解决的问题。对于栈来说，由于进出都在同一端，可以在数组的尾部进行插入和删除来实现栈的push和pop操作，但队列就不能在数组的尾部同时进行插入和删除操作，因为那样无法满足队列的先进先出要求，因此，队列的插入和删除必须在数组的两端分别进行才能实现先进先出的要求。</P>
<P>如果插入在尾部进行，删除就在头部进行，那么删除后，如何避免移动大量的数据呢？可以与栈的实现一样，用两个指针来指向队列的头部和尾部，在实际删除过程中，只移动头指针和尾指针，不移动整个数组的数据，保证了插入和删除的高效性。</P>
<H4>2. 环形队列实现动态增长及满空条件判断</H4>
<P>随之而来的问题是，队列的插入和删除操作比较频繁，如果插入的总数超过数组的大小，如何处理呢？由于很多数据被删除，实际上可以把数组看成一个环形队列，到达数组最大边界，尾指针重新指向数组头部。但这又引入了另外一个问题，尾指针可能在头指针的前面，如何去判断队列为空和队列为满的情况呢？</P>
<P>先讨论队列为满的情况，其实不管尾指针在头指针的前面还是后面，当队列为满时，在环形队列里，头指针刚好在尾指针的下一个位置上，当头指针在数组的最大边界时，它的下一个位置为数组的头部，即第0个位置，其他情况下，下一个位置是指刚好比它大1的位置，因此，判断队列是否为满的依据就是尾指针的下一个位置是否为头指针的位置。</P>
<P>再来讨论队列为空的情况，其实队列为空时头指针和尾指针完全重叠，所以只要判断头指针和尾指针是否相等便知道队列是否为空。</P>
<P>一个用数组实现的环形队列操作如图2-3所示。</P>
<H4>3. 关于队列空间使用的说明</H4>
<P 
style="LINE-HEIGHT: 15.8pt">从图2-3可以看出，当队列为满时实际上还有一个空间未使用，这样做的好处是比较便于判断队列是空还是满。如果将所有空间都用上，则队列为满和为空时，头指针和尾指针都重叠，这时需要通过判断头指针指向的数据是否为空或用其他方法来判断队列为满还是为空，增加了一次判断。由于队列操作本来就很简单，增加这样的判断会使操作效率降低很多，而且增加判断还会增加执行代码的大小，执行代码同样是需要消耗内存空间的，所以留一个元素空间不用并不等于浪费了空间，从全局考虑不仅没有浪费空间还提高了程序效率。另外队列如果空间设得稍微大一点的话，比如1 
024个元素，未用的一个空间只占1/1 024，几乎可以忽略不计。</P>
<P style="LINE-HEIGHT: 15.8pt"></P>
<P align=center><IMG 
src="2_2 队列 - 《多任务下的数据结构与算法》 - 免费试读 - book_csdn_net.files/image2.3.jpg"></P>
<P style="LINE-HEIGHT: 15.8pt" align=center>图2-3 环形队列示意图</P>