📄 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>栈的数组实现</h3>
<p>由于栈是一个特殊的表，我们可以用数组来实现栈。考虑到栈运算的特殊性，我们用一个数组elements[1..maxlength]来表示一个栈时，将栈底固定在数组的底部，即elements[1]为最早入栈的元素，并让栈向数组上方(下标增大的方向)扩展。同时，我们用一个游标top来指示当前栈顶元素所在的单元。当top=0时，表示这个栈为一个空栈。在一般情况下，elements中的元素序列elements[top],elements[top-1],..,elements[1]就构成了一个栈。这种结构如图2所示。</p>
<p align="center"><img border="0" src="images/img2.gif" width="340" height="225"></p>
<p align="center">图2 用数组实现栈</p>
<p>利用上述结构，我们可以形式地定义栈类型TStack如下：</p>
<div align="center">
<center>
<table border="0" width="90%" cellpadding="5" bgcolor="#E0E0E0">
<tr>
<td width="100%">
<p style="margin-top: 5; margin-bottom: 5">Type</p>
<p style="margin-top: 5; margin-bottom: 5"> TStack=Record</p>
<p style="margin-top: 5; margin-bottom: 5">
top:integer;</p>
<p style="margin-top: 5; margin-bottom: 5">
element:array[1..maxlength] of TElement;</p>
<p style="margin-top: 5; margin-bottom: 5">
End;</p>
</td>
</tr>
</table>
</center>
</div>
<p>在这种表示法下，栈的5种基本运算可实现如下。</p>
<div align="center">
<center>
<table border="1" width="90%" cellpadding="5" bordercolor="#FFFFFF" style="font-size: 10pt">
<tr>
<td width="100%" bgcolor="#E0E0E0">
<p style="margin-top: 5; margin-bottom: 5"><b>procedure</b> MakeNull(Var
S:TStack);</p>
<p style="margin-top: 5; margin-bottom: 5">begin</p>
<p style="margin-top: 5; margin-bottom: 5"> S.top:=0;</p>
<p style="margin-top: 5; margin-bottom: 5">end;</p>
</td>
</tr>
<tr>
<td width="100%" bgcolor="#E0E0E0">
<p style="margin-top: 5; margin-bottom: 5"><b>function</b> Empty(var
S:Stack):Boolean;</p>
<p style="margin-top: 5; margin-bottom: 5">begin</p>
<p style="margin-top: 5; margin-bottom: 5"> return(S.top=0);</p>
<p style="margin-top: 5; margin-bottom: 5">end;
</td>
</tr>
<tr>
<td width="100%" bgcolor="#E0E0E0">
<p style="margin-top: 5; margin-bottom: 5"><b>finction</b> Top(var S:TStack):TElement;</p>
<p style="margin-top: 5; margin-bottom: 5">begin</p>
<p style="margin-top: 5; margin-bottom: 5"> if Empty(S) then Error('The
stack is empty.')</p>
<p style="margin-top: 5; margin-bottom: 5">
else return(S.element[S.top]);</p>
<p style="margin-top: 5; margin-bottom: 5">end;
</td>
</tr>
<tr>
<td width="100%" bgcolor="#E0E0E0">
<p style="margin-top: 5; margin-bottom: 5"><b>procedure</b> Pop(var
S:TStack);</p>
<p style="margin-top: 5; margin-bottom: 5">begin</p>
<p style="margin-top: 5; margin-bottom: 5"> if Empty(S) then Error('The
stack is empty.')</p>
<p style="margin-top: 5; margin-bottom: 5">
else dec(S.top); {S.top减1}</p>
<p style="margin-top: 5; margin-bottom: 5">end;
</td>
</tr>
<tr>
<td width="100%" bgcolor="#E0E0E0">
<p style="margin-top: 5; margin-bottom: 5"><b>procedure</b> Push(x:TElement;var
S:TStack);</p>
<p style="margin-top: 5; margin-bottom: 5">begin</p>
<p style="margin-top: 5; margin-bottom: 5"> if S.top=maxlength
then Error('The stack is full.')</p>
<p style="margin-top: 5; margin-bottom: 5">
else begin</p>
<p style="margin-top: 5; margin-bottom: 5">
inc(S.top); {S.top增1}</p>
<p style="margin-top: 5; margin-bottom: 5">
S.elements[S.top]:=x;</p>
<p style="margin-top: 5; margin-bottom: 5">
end;</p>
<p style="margin-top: 5; margin-bottom: 5">end;
</td>
</tr>
</table>
</center>
</div>
<p>以上每种操作的复杂性为<i>O</i>(1)。</p>
<p>在一些问题中，可能需要同时使用多个同类型的栈。为了使每个栈在算法运行过程中不会溢出， 要为每个栈顶置一个较大的栈空间。这样做往往造成空间的浪费。实际上，在算法运行的过程中，各个栈一般不会同时满，很可能有的满而有的空。因此，如果我们让多个栈共享同一个数组，动态地互相调剂，将会提高空间的利用率，并减少发生栈上溢的可能性。
假设我们让程序中的两个栈共享一个数组S[1..n]。利用栈底位置不变的特性，我们可以将两个栈的栈底分别设在数组S的两端，然后各自向中间伸展，如图3所示。这两个S栈的栈顶初值分别为0和n+1。只有当两个栈的栈顶相遇时才可能发生上溢。由于两个栈之间可以余缺互补，因此每个栈实际可用的最大空间往往大于n/2。</p>
<p align="center"><img border="0" src="images/img3.gif" width="222" height="224"></p>
<p align="center">图3 共享同一个数组的两个栈</p>
<!-- #EndEditable -->
</div>
<script src='../../../lib/footer.js'>
</script>
</body>
<!-- #EndTemplate --></html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -