<!--
    Licensed to the Apache Software  Foundation (ASF) under one or more
    contributor  license agreements.  See  the NOTICE  file distributed
    with  this  work  for  additional information  regarding  copyright
    ownership.   The ASF  licenses this  file to  you under  the Apache
    License, Version  2.0 (the  License); you may  not use  this file
    except in  compliance with the License.   You may obtain  a copy of
    the License at

    http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the  License is distributed on an  "AS IS" BASIS,
    WITHOUT  WARRANTIES OR CONDITIONS  OF ANY  KIND, either  express or
    implied.   See  the License  for  the  specific language  governing
    permissions and limitations under the License.

    Copyright 1999-2007 Rogue Wave Software, Inc.
-->

<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&lt;()</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&nbsp;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>