| <HTML> |
| <HEAD> |
| <TITLE>Overview</TITLE> |
| <LINK REL=StyleSheet HREF="../rw.css" TYPE="text/css" TITLE="Apache stdcxx Stylesheet"></HEAD> |
| <BODY BGCOLOR=#FFFFFF> |
| <A HREF="10.html"><IMG SRC="images/bprev.gif" WIDTH=20 HEIGHT=21 ALT="Previous file" BORDER=O></A><A HREF="noframes.html"><IMG SRC="images/btop.gif" WIDTH=56 HEIGHT=21 ALT="Top of Document" BORDER=O></A><A HREF="booktoc.html"><IMG SRC="images/btoc.gif" WIDTH=56 HEIGHT=21 ALT="Contents" BORDER=O></A><A HREF="tindex.html"><IMG SRC="images/bindex.gif" WIDTH=56 HEIGHT=21 ALT="Index page" BORDER=O></A><A HREF="10-2.html"><IMG SRC="images/bnext.gif" WIDTH=25 HEIGHT=21 ALT="Next file" BORDER=O></A><DIV CLASS="DOCUMENTNAME"><B>Apache C++ Standard Library User's Guide</B></DIV> |
| <H2>10.1 Overview</H2> |
| <A NAME="idx183"><!></A> |
| <P>Most people have a good intuitive understanding of the <B><I><A HREF="../stdlibref/stack.html">stack</A></I></B> and <B><I><A HREF="../stdlibref/queue.html">queue</A></I></B> data abstractions based on experience with everyday objects. An excellent example of a stack is a pile of papers on a desk, or a stack of dishes in a cupboard. In both cases, the important characteristic is that the item on the top is most easily accessed. The easiest way to add a new item to the collection is to place it above all the current items in the stack. In this manner, an item removed from a stack is the item that has been most recently inserted into the stack; for example, the top piece of paper in the pile, or the top dish in the stack.</P> |
| <P>An everyday example of a queue, on the other hand, is a bank teller line, or a line of people waiting to enter a theater. Here new additions are made to the back of the queue, as new people enter the line, while items are removed from the front of the structure, as patrons enter the theater. The removal order for a queue is the opposite of that for a stack. In a queue, the item that is removed is the element that has been present in the queue for the longest period of time.</P> |
| <P>Among some groups of developers, a stack is referred to as a LIFO structure, and a queue is called a FIFO structure. The abbreviation <I>LIFO</I> stands for <I>Last In, First Out</I>. This means the first entry removed from a stack is the last entry that was inserted. The term <I>FIFO</I>, on the other hand, is short for <I>First In, First Out</I>. This means the first element removed from a queue is the first element that was inserted into the queue.</P> |
| <A NAME="idx184"><!></A> |
| <P>In the C++ Standard Library, both <B><I><A HREF="../stdlibref/stack.html">stack</A></I></B>s and <B><I><A HREF="../stdlibref/queue.html">queue</A></I></B>s are <I>adaptors</I>, built on top of other containers that actually hold the values. A <B><I>stack</I></B> can be built out of a <B><I><A HREF="../stdlibref/vector.html">vector</A></I></B>, a <B><I><A HREF="../stdlibref/list.html">list</A></I></B>, or a <B><I><A HREF="../stdlibref/deque.html">deque</A></I></B>, while a <B><I>queue</I></B> can be built on top of either a <B><I>list</I></B> or a <B><I>deque</I></B>. Elements held by either a <B><I>stack</I></B> or <B><I>queue</I></B> must recognize both <SAMP>operator<()</SAMP> and<SAMP> operator==()</SAMP>.</P> |
| <P>Because neither <B><I>stacks</I></B> nor <B><I>queues</I></B> define iterators, it is not possible to examine the elements of the collection except by removing the values one by one. The fact that these structures do not implement iterators also implies that most of the generic algorithms described in <A HREF="IV.html">Part IV</A> cannot be used with either data structure.</P> |
| |
| <BR> |
| <HR> |
| <A HREF="10.html"><IMG SRC="images/bprev.gif" WIDTH=20 HEIGHT=21 ALT="Previous file" BORDER=O></A><A HREF="noframes.html"><IMG SRC="images/btop.gif" WIDTH=56 HEIGHT=21 ALT="Top of Document" BORDER=O></A><A HREF="booktoc.html"><IMG SRC="images/btoc.gif" WIDTH=56 HEIGHT=21 ALT="Contents" BORDER=O></A><A HREF="tindex.html"><IMG SRC="images/bindex.gif" WIDTH=56 HEIGHT=21 ALT="Index page" BORDER=O></A><A HREF="10-2.html"><IMG SRC="images/bnext.gif" WIDTH=20 HEIGHT=21 ALT="Next file" BORDER=O></A> |
| |
| <!-- Google Analytics tracking code --> |
| <script src="http://www.google-analytics.com/urchin.js" type="text/javascript"> |
| </script> |
| <script type="text/javascript"> |
| _uacct = "UA-1775151-1"; |
| urchinTracker(); |
| </script> |
| <!-- end of Google Analytics tracking code --> |
| |
| </BODY> |
| </HTML> |
