📄 page147.html
字号:
<HTML>
<HEAD>
<TITLE>Queues</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html3724" HREF="page148.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page148.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html3722" HREF="page130.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page130.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html3716" HREF="page146.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page146.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html3726" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html3727" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H1><A NAME="SECTION007200000000000000000">Queues</A></H1>
<P>
In the preceding section we saw that a stack comprises a pile
of objects that can be accessed only at one end--the top.
In this section we examine a similar data structure called a
<em>single-ended queue</em><A NAME=6606> </A>.
Whereas in a stack we add and remove elements at the same end of the pile,
in a single-ended queue we add elements at one end
and remove them from the other.
Since it is always the first item to be put into the queue
that is the first item to be removed,
a queue is a <em>first-in, first-out</em><A NAME=6608> </A>
or <em>FIFO</em><A NAME=6610> </A> data structure.
Figure <A HREF="page147.html#figqueue1" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page147.html#figqueue1"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> illustrates the basic queue operations.
<P>
<P><A NAME="6879"> </A><A NAME="figqueue1"> </A> <IMG WIDTH=575 HEIGHT=200 ALIGN=BOTTOM ALT="figure6612" SRC="img735.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img735.gif" ><BR>
<STRONG>Figure:</STRONG> Basic Queue Operations<BR>
<P>
<P>
Program <A HREF="page147.html#progqueue1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page147.html#progqueue1h"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> gives the <tt>Queue</tt> abstract class definition.
The <tt>Queue</tt> class is derived from the <tt>Container</tt> class.
The <tt>Queue</tt> class interface comprises all the functions inherited
from the base classes plus the three function,
<tt>Head</tt>, <tt>Enqueue</tt>, and <tt>Dequeue</tt>.
<P>
<P><A NAME="6961"> </A><A NAME="progqueue1h"> </A> <IMG WIDTH=575 HEIGHT=143 ALIGN=BOTTOM ALT="program6890" SRC="img736.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img736.gif" ><BR>
<STRONG>Program:</STRONG> <tt>Queue</tt> Class Definition<BR>
<P>
<P>
As we did with stacks,
we will examine two queue implementations--an array-based one and a pointer-based one.
The array-based implementation uses the <tt>Array<T></tt> class
and the pointer-based implementation, the <tt>LinkedList<T></tt> class,
both of which are defined in Chapter <A HREF="page79.html#chapfds" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page79.html#chapfds"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
<P>
<BR> <HR>
<UL>
<LI> <A NAME="tex2html3728" HREF="page148.html#SECTION007210000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page148.html#SECTION007210000000000000000">Array Implementation</A>
<LI> <A NAME="tex2html3729" HREF="page152.html#SECTION007220000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page152.html#SECTION007220000000000000000">Linked List Implementation</A>
<LI> <A NAME="tex2html3730" HREF="page156.html#SECTION007230000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page156.html#SECTION007230000000000000000">Applications</A>
</UL>
<HR><A NAME="tex2html3724" HREF="page148.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page148.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html3722" HREF="page130.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page130.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html3716" HREF="page146.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page146.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html3726" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html3727" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright © 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.
</ADDRESS>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -