📄 page149.html
字号:
<HTML><HEAD><TITLE>Instance Attributes</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html2927" HREF="page150.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html2925" HREF="page148.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html2919" HREF="page148.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html2929" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION006211000000000000000">Instance Attributes</A></H3><P><tt>QueueAsArray</tt> objects comprise three instance attributes--<tt>_array</tt>, <tt>_head</tt>, and <tt>_tail</tt>.The first, <tt>_array</tt>, is an arraythat is used to hold the contents of the queue.The objects contained in the queuewill be held in a contiguous range of array elementsas shown in Figure <A HREF="page149.html#figqueue2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (a).The instance attributes <tt>_head</tt> and <tt>_tail</tt>denote the left and right ends, respectively, of this range.<P><P><A NAME="6573"> </A><A NAME="figqueue2"> </A> <IMG WIDTH=575 HEIGHT=347 ALIGN=BOTTOM ALT="figure6291" SRC="img690.gif" ><BR><STRONG>Figure:</STRONG> Array implementation of a queue.<BR><P><P>In general, the region of contiguous elements will not necessarilyoccupy the leftmost array positions.As elements are deleted at the head,the position of the left end will change.Similarly, as elements are added at the tail,the position of the right end will change.In some circumstances, the contiguous region of elementswill wrap around the ends of the array as shown in Figure <A HREF="page149.html#figqueue2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (b).<P>As shown in Figure <A HREF="page149.html#figqueue2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,the leftmost element is <tt>_array[_head]</tt>,and the rightmost element is <tt>_array[_tail]</tt>.When the queue contains only one element, <IMG WIDTH=99 HEIGHT=10 ALIGN=BOTTOM ALT="tex2html_wrap_inline60795" SRC="img691.gif" > as shown in Figure <A HREF="page149.html#figqueue2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (c).<P>Finally, Figure <A HREF="page149.html#figqueue2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (b) shows that if the queue is empty,the <tt>_head</tt> position will actually be to the rightof the <tt>_tail</tt> position.However, this is also the situation which arises when the queueis completely full!The problem is essentially this:Given an array of length <I>n</I>,then <IMG WIDTH=99 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60799" SRC="img692.gif" > and <IMG WIDTH=99 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60801" SRC="img693.gif" >.Therefore, the difference between the <tt>_head</tt> and <tt>_tail</tt>satisfies <IMG WIDTH=193 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60803" SRC="img694.gif" >.Since there are only <I>n</I> distinct differences,there can be only <I>n</I> distinct queue lengths, 0, 1, ..., <I>n</I>-1.It is not possible to distinguish the queue which is emptyfrom the queue which has <I>n</I> elementssolely on the basis of the <tt>_head</tt> and <tt>_tail</tt> instance attributes.<P>There are two options for dealing with this problem:The first is to limit the number of elements in the queue to be at most <I>n</I>-1.The second is to use another instance attribute, <tt>_count</tt>,to keep track explicitly of the actual number of elements in the queuerather than to infer the numberfrom the <tt>_head</tt> and <tt>_tail</tt> variables.The second approach has been adopted in the implementation given below.<P><HR><A NAME="tex2html2927" HREF="page150.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html2925" HREF="page148.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html2919" HREF="page148.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html2929" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -