00001 // Stack implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 00004 // Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the 00008 // terms of the GNU General Public License as published by the 00009 // Free Software Foundation; either version 2, or (at your option) 00010 // any later version. 00011 00012 // This library is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 00017 // You should have received a copy of the GNU General Public License along 00018 // with this library; see the file COPYING. If not, write to the Free 00019 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 00020 // USA. 00021 00022 // As a special exception, you may use this file as part of a free software 00023 // library without restriction. Specifically, if other files instantiate 00024 // templates or use macros or inline functions from this file, or you compile 00025 // this file and link it with other files to produce an executable, this 00026 // file does not by itself cause the resulting executable to be covered by 00027 // the GNU General Public License. This exception does not however 00028 // invalidate any other reasons why the executable file might be covered by 00029 // the GNU General Public License. 00030 00031 /* 00032 * 00033 * Copyright (c) 1994 00034 * Hewlett-Packard Company 00035 * 00036 * Permission to use, copy, modify, distribute and sell this software 00037 * and its documentation for any purpose is hereby granted without fee, 00038 * provided that the above copyright notice appear in all copies and 00039 * that both that copyright notice and this permission notice appear 00040 * in supporting documentation. Hewlett-Packard Company makes no 00041 * representations about the suitability of this software for any 00042 * purpose. It is provided "as is" without express or implied warranty. 00043 * 00044 * 00045 * Copyright (c) 1996,1997 00046 * Silicon Graphics Computer Systems, Inc. 00047 * 00048 * Permission to use, copy, modify, distribute and sell this software 00049 * and its documentation for any purpose is hereby granted without fee, 00050 * provided that the above copyright notice appear in all copies and 00051 * that both that copyright notice and this permission notice appear 00052 * in supporting documentation. Silicon Graphics makes no 00053 * representations about the suitability of this software for any 00054 * purpose. It is provided "as is" without express or implied warranty. 00055 */ 00056 00057 /** @file stl_stack.h 00058 * This is an internal header file, included by other library headers. 00059 * You should not attempt to use it directly. 00060 */ 00061 00062 #ifndef _STACK_H 00063 #define _STACK_H 1 00064 00065 #include <bits/concept_check.h> 00066 #include <debug/debug.h> 00067 00068 _GLIBCXX_BEGIN_NAMESPACE(std) 00069 00070 /** 00071 * @brief A standard container giving FILO behavior. 00072 * 00073 * @ingroup Containers 00074 * @ingroup Sequences 00075 * 00076 * Meets many of the requirements of a 00077 * <a href="tables.html#65">container</a>, 00078 * but does not define anything to do with iterators. Very few of the 00079 * other standard container interfaces are defined. 00080 * 00081 * This is not a true container, but an @e adaptor. It holds 00082 * another container, and provides a wrapper interface to that 00083 * container. The wrapper is what enforces strict 00084 * first-in-last-out %stack behavior. 00085 * 00086 * The second template parameter defines the type of the underlying 00087 * sequence/container. It defaults to std::deque, but it can be 00088 * any type that supports @c back, @c push_back, and @c pop_front, 00089 * such as std::list, std::vector, or an appropriate user-defined 00090 * type. 00091 * 00092 * Members not found in "normal" containers are @c container_type, 00093 * which is a typedef for the second Sequence parameter, and @c 00094 * push, @c pop, and @c top, which are standard %stack/FILO 00095 * operations. 00096 */ 00097 template<typename _Tp, typename _Sequence = deque<_Tp> > 00098 class stack 00099 { 00100 // concept requirements 00101 typedef typename _Sequence::value_type _Sequence_value_type; 00102 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 00103 __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept) 00104 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) 00105 00106 template<typename _Tp1, typename _Seq1> 00107 friend bool 00108 operator==(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&); 00109 00110 template<typename _Tp1, typename _Seq1> 00111 friend bool 00112 operator<(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&); 00113 00114 public: 00115 typedef typename _Sequence::value_type value_type; 00116 typedef typename _Sequence::reference reference; 00117 typedef typename _Sequence::const_reference const_reference; 00118 typedef typename _Sequence::size_type size_type; 00119 typedef _Sequence container_type; 00120 00121 protected: 00122 // See queue::c for notes on this name. 00123 _Sequence c; 00124 00125 public: 00126 // XXX removed old def ctor, added def arg to this one to match 14882 00127 /** 00128 * @brief Default constructor creates no elements. 00129 */ 00130 explicit 00131 stack(const _Sequence& __c = _Sequence()) 00132 : c(__c) { } 00133 00134 /** 00135 * Returns true if the %stack is empty. 00136 */ 00137 bool 00138 empty() const 00139 { return c.empty(); } 00140 00141 /** Returns the number of elements in the %stack. */ 00142 size_type 00143 size() const 00144 { return c.size(); } 00145 00146 /** 00147 * Returns a read/write reference to the data at the first 00148 * element of the %stack. 00149 */ 00150 reference 00151 top() 00152 { 00153 __glibcxx_requires_nonempty(); 00154 return c.back(); 00155 } 00156 00157 /** 00158 * Returns a read-only (constant) reference to the data at the first 00159 * element of the %stack. 00160 */ 00161 const_reference 00162 top() const 00163 { 00164 __glibcxx_requires_nonempty(); 00165 return c.back(); 00166 } 00167 00168 /** 00169 * @brief Add data to the top of the %stack. 00170 * @param x Data to be added. 00171 * 00172 * This is a typical %stack operation. The function creates an 00173 * element at the top of the %stack and assigns the given data 00174 * to it. The time complexity of the operation depends on the 00175 * underlying sequence. 00176 */ 00177 void 00178 push(const value_type& __x) 00179 { c.push_back(__x); } 00180 00181 /** 00182 * @brief Removes first element. 00183 * 00184 * This is a typical %stack operation. It shrinks the %stack 00185 * by one. The time complexity of the operation depends on the 00186 * underlying sequence. 00187 * 00188 * Note that no data is returned, and if the first element's 00189 * data is needed, it should be retrieved before pop() is 00190 * called. 00191 */ 00192 void 00193 pop() 00194 { 00195 __glibcxx_requires_nonempty(); 00196 c.pop_back(); 00197 } 00198 }; 00199 00200 /** 00201 * @brief Stack equality comparison. 00202 * @param x A %stack. 00203 * @param y A %stack of the same type as @a x. 00204 * @return True iff the size and elements of the stacks are equal. 00205 * 00206 * This is an equivalence relation. Complexity and semantics 00207 * depend on the underlying sequence type, but the expected rules 00208 * are: this relation is linear in the size of the sequences, and 00209 * stacks are considered equivalent if their sequences compare 00210 * equal. 00211 */ 00212 template<typename _Tp, typename _Seq> 00213 inline bool 00214 operator==(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 00215 { return __x.c == __y.c; } 00216 00217 /** 00218 * @brief Stack ordering relation. 00219 * @param x A %stack. 00220 * @param y A %stack of the same type as @a x. 00221 * @return True iff @a x is lexicographically less than @a y. 00222 * 00223 * This is an total ordering relation. Complexity and semantics 00224 * depend on the underlying sequence type, but the expected rules 00225 * are: this relation is linear in the size of the sequences, the 00226 * elements must be comparable with @c <, and 00227 * std::lexicographical_compare() is usually used to make the 00228 * determination. 00229 */ 00230 template<typename _Tp, typename _Seq> 00231 inline bool 00232 operator<(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 00233 { return __x.c < __y.c; } 00234 00235 /// Based on operator== 00236 template<typename _Tp, typename _Seq> 00237 inline bool 00238 operator!=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 00239 { return !(__x == __y); } 00240 00241 /// Based on operator< 00242 template<typename _Tp, typename _Seq> 00243 inline bool 00244 operator>(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 00245 { return __y < __x; } 00246 00247 /// Based on operator< 00248 template<typename _Tp, typename _Seq> 00249 inline bool 00250 operator<=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 00251 { return !(__y < __x); } 00252 00253 /// Based on operator< 00254 template<typename _Tp, typename _Seq> 00255 inline bool 00256 operator>=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 00257 { return !(__x < __y); } 00258 00259 _GLIBCXX_END_NAMESPACE 00260 00261 #endif /* _STACK_H */