📄 page158.html
字号:
<HTML><HEAD><TITLE>Deques</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="tex2html3022" HREF="page159.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3020" HREF="page130.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3014" HREF="page157.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3024" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION006300000000000000000">Deques</A></H1><A NAME="secstacksdeques"> </A><P>In the preceding section we saw that a queue comprises a pile of objectsinto which we insert items at one endand from which we remove items at the other end.In this section we examine an extension of the queuewhich provides a means to insert and remove items at both ends of the pile.This data structure is a <em>deque</em><A NAME=7369> </A>.The word <em>deque</em> is an acronym derivedfrom <em>double-ended queue</em><A NAME=7372> </A>.<A NAME="tex2html275" HREF="footnode.html#7426"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/foot_motif.gif"></A><P>Figure <A HREF="page158.html#figdeque1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> illustrates the basic deque operations.A deque provides three operations which access the head of the queue,<tt>Head</tt>, <tt>EnqueueHead</tt> and <tt>DequeueHead</tt>,and three operations to access the tail of the queue,<tt>Tail</tt>, <tt>EnqueueTail</tt> and <tt>DequeueTail</tt>.<P><P><A NAME="7726"> </A><A NAME="figdeque1"> </A> <IMG WIDTH=575 HEIGHT=200 ALIGN=BOTTOM ALT="figure7381" SRC="img701.gif" ><BR><STRONG>Figure:</STRONG> Basic deque operations.<BR><P><P>Program <A HREF="page158.html#progdequea"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> defines the <tt>Deque</tt> class.The abstract <tt>Deque</tt> class extends the abstract <tt>Container</tt> classdefined in Program <A HREF="page119.html#progcontainera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.Hence, it comprises all of the methods inherited from <tt>Container</tt>plus the methods,<tt>enqueueHead</tt>, <tt>dequeueHead</tt>,<tt>enqueueTail</tt>, and <tt>dequeueTail</tt>,and the properties,<tt>head</tt> and <tt>tail</tt>.<P><P><A NAME="7909"> </A><A NAME="progdequea"> </A> <IMG WIDTH=575 HEIGHT=622 ALIGN=BOTTOM ALT="program7741" SRC="img702.gif" ><BR><STRONG>Program:</STRONG> Abstract <tt>Deque</tt> class.<BR><P><P>The <tt>dequeueHead</tt> method of the <tt>Deque</tt> classis trivial to implement--it simply calls the <tt>dequeue</tt>method inherited from the <tt>Queue</tt> class.Similarly, the <tt>enqueueTail</tt> method simply calls the <tt>enqueue</tt>method inherited from the <tt>Queue</tt> class.<P><BR> <HR><UL> <LI> <A NAME="tex2html3025" HREF="page159.html#SECTION006310000000000000000">Array Implementation</A><LI> <A NAME="tex2html3026" HREF="page162.html#SECTION006320000000000000000">Linked List Implementation</A><LI> <A NAME="tex2html3027" HREF="page165.html#SECTION006330000000000000000">Doubly-Linked and Circular Lists</A></UL><HR><A NAME="tex2html3022" HREF="page159.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3020" HREF="page130.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3014" HREF="page157.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3024" 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 + -