📄 chapter3_1.htm
字号:
<html><!-- #BeginTemplate "/Templates/article_template.dwt" -->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="keywords" content="algorithm, data structure, contest, programming, 算法, 数据结构, 程序设计, 竞赛">
<meta name="description" content="discussing the algorithm and data structure of computer programming, as well as all kinds of programming contest.">
<meta name="description" content="讨论程序设计的算法与数据结构，各类程序设计竞赛试题解析和参赛经验介绍。">
<!-- #BeginEditable "doctitle" -->
<title>用循环数组实现队列</title>
<!-- #EndEditable -->
<script id="header" language="JavaScript" src="../../../lib/header.js"></script>
<!-- #BeginEditable "javascript" -->
<script language="JavaScript">
var previous = "chapter3.htm";
var next = "chapter3_2.htm";
</script>
<!-- #EndEditable -->
</head>
<body bgcolor="#FFFFFF">
<div id="content">
<!-- #BeginEditable "MainContent" -->
<h3>用循环数组实现队列<a name="imp-array"></a></h3>
<p>我们可以将队列<a href="../list/chapter3_1.htm">当作一般的表用数组加以实现</a>，但这样做的效果并不好。尽管我们可以用一个游标last来指示队尾，使得Enqueue运算可在<i>O</i>(1)时间内完成，但是在执行Dequeue时，为了删除队头元素，必须将数组中其他所有元素都向前移动一个位置。这样，当队列中有n个元素时，执行Dequeue就需要<i>O</i>(n)时间。</p>
<p>为了提高运算的效率，我们用另一种方法来表达数组中各单元的位置关系。设想数组Q[1..MaxLength]中的单元不是排成一行，而是围成一个圆环，即Q[1]接在Q[MaxLength]的后面。这种意义下的数组称为<font face="楷体_GB2312">循环数组</font>，如图2所示。</p>
<blockquote>
<p align="center"><img border="0" src="images/img10.gif" width="457" height="250"></p>
<p align="center">图2 用循环数组实现队列</p>
</blockquote>
<p>用循环数组实现队列时，我们将队列中从队头到队尾的元素按顺时针方向存放在循环数组中一段连续的单元中。当需要将新元素入队时，可将队尾游标Q.rear按顺时针方向移一位，并在新的队尾游标指示的单元中存入新元素。出队操作也很简单，只要将队头游标Q.front依顺时针方向移一位即可。容易看出，用循环数组来实现队列可以在<i>O</i>(1)时间内完成Enqueue和Dequeue运算。执行一系列的入队与出队运算，将使整个队列在循环数组中按顺时针方向移动。</p>
<p>在图2中，我们直接用队头游标Q.front指向队头元素所在的单元，用队尾游标Q.rear指向队尾元素所在的单元。另外，我们也可以用队头游标Q.front指向队头元素所在单元的前一个单元，或者用队尾游标Q.rear指向队尾元素所在单元的下一个单元的方法来表示队列在循环数组中的位置，如图3所示。</p>
<blockquote>
<p align="center"><img border="0" src="images/img9.gif" width="355" height="234"></p>
<p align="center"><img border="0" src="images/img8.gif" width="361" height="230"></p>
<p align="center"> </p>
<p align="center">图3 循环数组中的队头与队尾游标</p>
</blockquote>
<p>在循环数组中，不论用哪一种方式来指示队头与队尾元素，我们都要解决一个细节问题，即如何表示满队列和空队列。图4给出一个例子，MaxLength=6，队列中已有3个元素。我们用上述3种方法来指示队头和队尾元素，分别如图4(a)、(b)和(c)所示。</p>
<blockquote>
<p align="center"><img border="0" src="images/img5.gif" width="249" height="181"></p>
<p align="center">(a)</p>
<p align="center"><img border="0" src="images/img19.gif" width="246" height="174"></p>
<p align="center">(b)</p>
<p align="center"><img border="0" src="images/img18.gif" width="271" height="175"></p>
<p align="center">(c)</p>
<p align="center">图4 循环数组中的队列</p>
</blockquote>
<p>现在，有3个元素a<sub>4</sub>,a<sub>5</sub>,a<sub>6</sub>相继入队，使队列呈"满"的状态，则如图5相应的(a),(b)和(c)所示。</p>
<blockquote>
<p align="center"><img border="0" src="images/img6.gif" width="289" height="182"></p>
<p align="center">(a)</p>
<p align="center"><img border="0" src="images/img17.gif" width="248" height="177"></p>
<p align="center">(b)</p>
<p align="center"><img border="0" src="images/img16.gif" width="242" height="169"></p>
<p align="center">(c)</p>
<p align="center">图5 队列满的情形</p>
</blockquote>
<p>如果在图4中，3个元素a<sub>1</sub>,a<sub>2</sub>,a<sub>3</sub>相继出队，使队列呈"空"的状态，则如图6相应的(a),(b)和(c)所示。</p>
<blockquote>
<p align="center"><img border="0" src="images/img4.gif" width="272" height="170"></p>
<p align="center">(a)</p>
<p align="center"><img border="0" src="images/img15.gif" width="187" height="176"></p>
<p align="center">(b)</p>
<p align="center"><img border="0" src="images/img14.gif" width="250" height="180"></p>
<p align="center">(c)</p>
<p align="center">图6 队列空的情形</p>
</blockquote>
<p>比较图5和图6我们看到，不论采用哪一种方式指示队头和队尾元素，都需要附加说明或约定才能区分满队列和空队列。</p>
<p>通常有两种处理方法来解决这个问题。其一是另设一个布尔量来注明队列是空还是满。二是约定当循环数组中元素个数达到MaxLength-1时队列为“满”，使得队列满和队列空时的队头和队尾游标的相对位置不同，从而满队列和空队列得以区分。例如，在图4中，当元素a<sub>4</sub>和a<sub>5</sub>相继入队后，就便队列呈“满”的状态，如图7所示。比较图7和图6，显然只要测试头和队尾游标的相对位置便可区分出满队列和空队列。</p>
<blockquote>
<p align="center"><img border="0" src="images/img13.gif" width="204" height="216"></p>
<p align="center">(a)</p>
<p align="center"><img border="0" src="images/img12.gif" width="208" height="224"></p>
<p align="center">(b)</p>
<p align="center"><img border="0" src="images/img11.gif" width="200" height="200"></p>
<p align="center">(c)</p>
<p align="center">图7 改进后的队列满的情形</p>
</blockquote>
<p>为确定起见，这里采用图2的方式定义Q.front和Q.rear，另采用上述的第二种处理法区分满队列和空队列。</p>
<p>这样，队列的类型QueueType说明为：</p>
<div align="center">
<center>
<table border="0" width="90%" style="font-size: 10pt" bgcolor="#E0E0E0" cellpadding="5">
<tr>
<td width="100%">
<p style="margin-top: 5; margin-bottom: 5">type</p>
<p style="margin-top: 5; margin-bottom: 5">TPosition=integer;</p>
<p style="margin-top: 5; margin-bottom: 5">QueueType = record</p>
<p style="margin-top: 5; margin-bottom: 5">
Elements:array[1..MaxLength] of ElementType;</p>
<p style="margin-top: 5; margin-bottom: 5">
front,rear:TPosition;</p>
<p style="margin-top: 5; margin-bottom: 5">
end;
</td>
</tr>
</table>
</center>
</div>
<blockquote>
<p>那么，在用循环数组实现的队列中，队列的5种基本运算可实现如下。其中∧表示空元素，要根据不同的元素类型来确定。</p>
</blockquote>
<div align="center">
<center>
<table border="0" width="90%" cellpadding="5" style="font-size: 10pt">
<tr>
<td width="100%" bgcolor="#E0E0E0">
<p style="margin-top: 5; margin-bottom: 5"><b>函数</b> Front(Q)</p>
<p style="margin-top: 5; margin-bottom: 5"><b>功能</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">这是一个函数，函数值返回队列Q的队头元素。用<a href="../list/chapter2.htm">一般的表运算</a>可将Front(Q)表示为Retrieve(First(Q),Q)。如果队列为空则返回空元素∧。</p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>实现</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">Function Front(var Q:QueueType):ElementType;</p>
<p style="margin-top: 5; margin-bottom: 5">begin</p>
<p style="margin-top: 5; margin-bottom: 5"> if Empty(Q) then
return(∧)</p>
<p style="margin-top: 5; margin-bottom: 5">
else return(Q.Elements[Q.front]);</p>
<p style="margin-top: 5; margin-bottom: 5">end;</p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>说明</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">显然</p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>复杂性</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">显然为<i>O</i>(1)。</p>
</blockquote>
</td>
</tr>
<tr>
<td width="100%" bgcolor="#E0E0E0">
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -