Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://www.atnf.csiro.au/computing/software/casacore/casacore-1.2.0/doc/html/Stack_8h_source.html
Дата изменения: Unknown Дата индексирования: Mon Feb 14 19:39:08 2011 Кодировка: Поисковые слова: п п п п п п п п п п п п п п п п п п п п п п п п п п п п п п п р п р п р п р п р п р п р п |
00001 //# Stack.h: Implementation of a stack using the doubly linked list class 00002 //# Copyright (C) 1993,1994,1995,1999,2000 00003 //# Associated Universities, Inc. Washington DC, USA. 00004 //# 00005 //# This library is free software; you can redistribute it and/or modify it 00006 //# under the terms of the GNU Library General Public License as published by 00007 //# the Free Software Foundation; either version 2 of the License, or (at your 00008 //# option) any later version. 00009 //# 00010 //# This library is distributed in the hope that it will be useful, but WITHOUT 00011 //# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 00012 //# FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public 00013 //# License for more details. 00014 //# 00015 //# You should have received a copy of the GNU Library General Public License 00016 //# along with this library; if not, write to the Free Software Foundation, 00017 //# Inc., 675 Massachusetts Ave, Cambridge, MA 02139, USA. 00018 //# 00019 //# Correspondence concerning AIPS++ should be addressed as follows: 00020 //# Internet email: aips2-request@nrao.edu. 00021 //# Postal address: AIPS++ Project Office 00022 //# National Radio Astronomy Observatory 00023 //# 520 Edgemont Road 00024 //# Charlottesville, VA 22903-2475 USA 00025 //# 00026 //# $Id: Stack.h 20551 2009-03-25 00:11:33Z Malte.Marquarding $ 00027 00028 #ifndef CASA_STACK_H 00029 #define CASA_STACK_H 00030 00031 #include <casa/aips.h> 00032 #include <casa/Containers/Link.h> 00033 00034 namespace casa { //# NAMESPACE CASA - BEGIN 00035 00036 extern void throw_empty_Stack_error(const char *msg = 0); 00037 00038 // This class, Stack<t>, defines an implementation of a stack using 00039 // the doubly linked list primitive, Link<t>. It has the standard 00040 // push and pop operations. 00041 // 00042 // <summary> 00043 // A Last-In-First-Out (LIFO) data structure. 00044 // </summary> 00045 // 00046 // <reviewed reviewer="Gareth Hunt" date="94Jan06" tests="tQueue" demos=""> 00047 // </reviewed> 00048 // 00049 // <synopsis> 00050 // A Stack as implemented here is a simple container which can grow with time, 00051 // and which returns its elements (only) in the inverse order which they are 00052 // inserted. That is, the fundamental operations are to push (add) an element 00053 // onto the top of the stack and to pop (remove) an element from the top of 00054 // the stack. As a result, the last element placed on the stack will be the 00055 // first element removed. 00056 // 00057 // <example> 00058 // <srcblock> 00059 // Stack<int> one,two; 00060 // int count = 0; 00061 // one.push(1); // add 00062 // one.push(2); // add 00063 // one.push(3); // add 00064 // one.push(4); // add 00065 // while ( !one.empty() ) { 00066 // cout << one.top() << " "; // top element 00067 // two.push(one.top()); // push = add 00068 // one.pop(); // remove top element 00069 // } 00070 // cout << endl; 00071 // while ( !two.empty() ) { 00072 // one.push(two.top()); 00073 // cout << two.popVal() << " "; // remove and return top 00074 // } 00075 // while ( !one.empty() ) 00076 // count += one.popVal(); 00077 // cout << endl << count << endl;; 00078 // </srcblock> 00079 // This results in the following output: 00080 // <pre> 00081 // 4 3 2 1 00082 // 1 2 3 4 00083 // 10 00084 // </pre> 00085 // <example> 00086 // 00087 // Presently, this implementation is rather simple. It is built directly 00088 // upon the Link class. 00089 // </synopsis> 00090 // 00091 // <motivation> 00092 // A simple stack was needed for the (now deprecated) CanDelete class. 00093 // </motivation> 00094 // 00095 // <todo asof="28OCT94"> 00096 // <li> It is conceivable that an iterator might be useful for this class. 00097 // <li> If this class is ever heavily used, a more space efficient 00098 // implementation may be necessary. 00099 // </todo> 00100 // 00101 template<class elem> class Stack { 00102 private: 00103 // Pointer to the top of the stack. 00104 Link<elem> *topOfStack; 00105 public: 00106 00107 // 00108 // This creates an empty stack. 00109 // 00110 Stack() : topOfStack(0) {} 00111 00112 // 00113 // Create a stack by making a copy of other. 00114 // 00115 Stack(const Stack<elem> &other); 00116 00117 // 00118 // Create a stack which is a copy of other. 00119 // 00120 Stack<elem> &operator=(const Stack<elem> &other); 00121 00122 ~Stack(); 00123 00124 // 00125 // Add an element to the top of the stack. 00126 // 00127 void push(const elem &e) {topOfStack = new Link<elem>(e,0,topOfStack);} 00128 00129 // 00130 // Remove the top element from the top of the stack. 00131 // 00132 void pop() { 00133 if (topOfStack == 0) 00134 throw_empty_Stack_error("Invalid operation (pop) on an empty Stack."); 00135 Link<elem> *tmp = topOfStack; 00136 topOfStack = (*tmp).unlink(); 00137 delete tmp; 00138 } 00139 00140 // 00141 // Remove the top element from the top of the stack, and return it 00142 // 00143 elem popVal() { 00144 if (topOfStack == 0) 00145 throw_empty_Stack_error("Invalid operation (popVal) on an empty Stack."); 00146 Link<elem> *tmp = topOfStack; 00147 elem ret = (*tmp).val(); 00148 topOfStack = (*tmp).unlink(); 00149 delete tmp; 00150 return ret; 00151 } 00152 00153 // 00154 // Retreive the top element on the stack. 00155 // 00156 // <group> 00157 elem &top() { 00158 if (topOfStack == 0) 00159 throw_empty_Stack_error("Invalid operation (top) on an empty Stack."); 00160 return((*topOfStack).val());} 00161 00162 const elem &top() const { 00163 if (topOfStack == 0) 00164 throw_empty_Stack_error("Invalid operation (const top) on an empty Stack."); 00165 return((*topOfStack).val());} 00166 // </group> 00167 00168 // 00169 // Check to see if the stack is empty. 00170 // 00171 Bool empty() const { return(topOfStack ? False : True);} 00172 }; 00173 00174 00175 } //# NAMESPACE CASA - END 00176 00177 #ifndef CASACORE_NO_AUTO_TEMPLATES 00178 #include <casa/Containers/Stack.tcc> 00179 #endif //# CASACORE_NO_AUTO_TEMPLATES 00180 #endif