-
Notifications
You must be signed in to change notification settings - Fork 25
/
ch12s05.html
3 lines (3 loc) · 4.53 KB
/
ch12s05.html
1
2
3
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>5. 环形队列</title><link rel="stylesheet" href="styles.css" type="text/css" /><meta name="generator" content="DocBook XSL Stylesheets V1.73.2" /><link rel="start" href="index.html" title="Linux C编程一站式学习" /><link rel="up" href="ch12.html" title="第 12 章 栈与队列" /><link rel="prev" href="ch12s04.html" title="4. 队列与广度优先搜索" /><link rel="next" href="ch13.html" title="第 13 章 本阶段总结" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">5. 环形队列</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="ch12s04.html">上一页</a> </td><th width="60%" align="center">第 12 章 栈与队列</th><td width="20%" align="right"> <a accesskey="n" href="ch13.html">下一页</a></td></tr></table><hr /></div><div class="sect1" lang="zh-cn" xml:lang="zh-cn"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="id2750902"></a>5. 环形队列</h2></div></div></div><p>比较<a class="xref" href="ch12s03.html#stackqueue.dfs">例 12.3 “用深度优先搜索解迷宫问题”</a>的栈操作和<a class="xref" href="ch12s04.html#stackqueue.bfs">例 12.4 “用广度优先搜索解迷宫问题”</a>的队列操作可以发现，栈操作的<code class="literal">top</code>指针在Push时增大而在Pop时减小，栈空间是可以重复利用的，而队列的<code class="literal">head</code>、<code class="literal">tail</code>指针都在一直增大，虽然前面的元素已经出队了，但它所占的存储空间却不能重复利用。在<a class="xref" href="ch12s04.html#stackqueue.bfs">例 12.4 “用广度优先搜索解迷宫问题”</a>的解法中，出队的元素仍然有用，保存着走过的路径和每个点的前趋，但大多数程序并不是这样使用队列的，一般情况下出队的元素就不再有保存价值了，这些元素的存储空间应该回收利用，由此想到把队列改造成环形队列（Circular Queue）<a id="id2750963" class="indexterm"></a>：把<code class="literal">queue</code>数组想像成一个圈，<code class="literal">head</code>和<code class="literal">tail</code>指针仍然是一直增大的，当指到数组末尾时就自动回到数组开头，就像两个人围着操场赛跑，沿着它们跑的方向看，从<code class="literal">head</code>到<code class="literal">tail</code>之间是队列的有效元素，从<code class="literal">tail</code>到<code class="literal">head</code>之间是空的存储位置，如果<code class="literal">head</code>追上<code class="literal">tail</code>就表示队列空了，如果<code class="literal">tail</code>追上<code class="literal">head</code>就表示队列的存储空间满了。如下图所示：</p><div class="figure"><a id="id2751042"></a><p class="title"><b>图 12.5. 环形队列</b></p><div class="figure-contents"><div><img src="images/stackqueue.circular.png" alt="环形队列" /></div></div></div><br class="figure-break" /><div class="simplesect" lang="zh-cn" xml:lang="zh-cn"><div class="titlepage"><div><div><h3 class="title"><a id="id2751055"></a>习题</h3></div></div></div><p>1、现在把迷宫问题的要求改一下，只要求程序给出最后结论就可以了，回答“<span class="quote">有路能到达终点</span>”或者“<span class="quote">没有路能到达终点</span>”，而不需要把路径打印出来。请把<a class="xref" href="ch12s04.html#stackqueue.bfs">例 12.4 “用广度优先搜索解迷宫问题”</a>改用环形队列实现，然后试验一下解决这个问题至少需要分配多少个元素的队列空间。</p></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="ch12s04.html">上一页</a> </td><td width="20%" align="center"><a accesskey="u" href="ch12.html">上一级</a></td><td width="40%" align="right"> <a accesskey="n" href="ch13.html">下一页</a></td></tr><tr><td width="40%" align="left" valign="top">4. 队列与广度优先搜索 </td><td width="20%" align="center"><a accesskey="h" href="index.html">起始页</a></td><td width="40%" align="right" valign="top"> 第 13 章 本阶段总结</td></tr></table></div></body></html>