page130.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 79 行
HTML
79 行
<HTML><HEAD><TITLE>Stacks, Queues, and 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="tex2html2700" HREF="page131.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html2698" HREF="book.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html2692" HREF="page129.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html2702" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION006000000000000000000">Stacks, Queues, and Deques</A></H1><P><A NAME="chapstacks"> </A><P>In this chapter we consider several related abstract data types--stacks, queues, and deques.Each of these can be viewed as a pile of items.What distinguishes each of them is the way in which itemsare added to or removed from the pile.<P>In the case of a <em>stack</em>,items are added to and removed from the top of the pile.Consider the pile of papers on your desk.Suppose you add papers only to the top of the pileor remove them only from the top of the pile.At any point in time,the only paper that is visible is the one on top.What you have is a <em>stack</em>.<P>Now suppose your boss comes alongand asks you to complete a form immediately.You stop doing whatever it is you are doing,and place the form on top of your pile of papers.When you have filled-out the form,you remove it from the top of the stackand return to the task you were workingon before your boss interrupted you.This example illustrates thata <em>stack</em> can be used to keep track of partially completed tasks.<P>A <em>queue</em><A NAME=5005> </A> is a pile in which items are added an one endand removed from the other.In this respect,a queue is like the line of customers waiting to be served by a bank teller.As customers arrive,they join the end of the queuewhile the teller serves the customer at the head of the queue.As a result,a <em>queue</em> is used when a sequence of activities must be doneon a <em>first-come, first-served</em> basis.<P>Finally, a <em>deque</em><A NAME=5009> </A> extends the notion of a queue.In a deque, items can be added to or removed from either end of the queue.In a sense, a deque is the more general abstractionof which the stack and the queue are just special cases.<P>As shown in Figure <A HREF="page130.html#figclasses2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,we view stacks, queues, and deques as containers.This chapter presents a number of different implementation alternativesfor stacks, queues, and deques.All of the concrete classes presented are extensionsof the abstract <tt>Container</tt> class defined in Chapter <A HREF="page111.html#chapadts"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><P><A NAME="5017"> </A><A NAME="figclasses2"> </A> <IMG WIDTH=575 HEIGHT=344 ALIGN=BOTTOM ALT="figure5013" SRC="img657.gif" ><BR><STRONG>Figure:</STRONG> Object class hierarchy.<BR><P><BR> <HR><UL> <LI> <A NAME="tex2html2703" HREF="page131.html#SECTION006100000000000000000">Stacks</A><LI> <A NAME="tex2html2704" HREF="page147.html#SECTION006200000000000000000">Queues</A><LI> <A NAME="tex2html2705" HREF="page158.html#SECTION006300000000000000000">Deques</A><LI> <A NAME="tex2html2706" HREF="page166.html#SECTION006400000000000000000">Exercises</A><LI> <A NAME="tex2html2707" HREF="page167.html#SECTION006500000000000000000">Projects</A></UL><HR><A NAME="tex2html2700" HREF="page131.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html2698" HREF="book.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html2692" HREF="page129.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html2702" 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 + =
减小字号Ctrl + -
显示快捷键?