Actividad de Aprendizaje 11 La Pila y la Cola, implementación dinámica - Fernando Cesar Sandoval Padilla

Vista previa del material en texto

UNIVERSIDAD DE GUADALAJARA 
Centro Universitario de Ciencias Exactas e Ingenierías 
 
Estructura de datos I 
Actividad de Aprendizaje 11. La Pila y la Cola, implementación dinámica 
 
 
 
 
 
Alumno: Sandoval Padilla Fernando Cesar 
Docente: Gutiérrez Hernández Alfredo 
Código: 215685409 
Sección: D12 
 
 
 
 
 
 
 
 
 
 10 de Noviembre de 2019 
Resumen personal: 
La realización de esta actividad no tuvo mayor dificultad que intercambiar los arreglos utilizados 
en la actividad anterior para hacer una implementación dinámica. Por otra parte, se utilizaron 
los mismos 3 ejemplos del documento 06_B_Pila_aplicacion que se extrajo de los apuntes de 
estructuras de datos en la pagina 5 del documento, los cuales están presentes en las capturas 
de pantalla. 
Código fuente: 
Main.cpp 
1 #include <iostream> 
2 #include <windows.h> 
3 #include <string.h> 
4 
5 #include "stack.h" 
6 #include "queue.h" 
7 #include "E.h" 
8 
9 using namespace std; 
10 
11 int main() { 
12 char e; 
13 E elem; 
14 E sum,rest,mul,div,pot,para,parc; 
15 e = '+'; 
16 sum.setElement(e); 
17 e = '-'; 
18 rest.setElement(e); 
19 e = '*'; 
20 mul.setElement(e); 
21 e = '/'; 
22 div.setElement(e); 
23 e = '^'; 
24 pot.setElement(e); 
25 e = '('; 
26 para.setElement(e); 
27 e = ')'; 
28 parc.setElement(e); 
29 Stack<E> myStack; 
30 Queue<E> myQueue; 
31 char mychar[1024]; 
32 int lon; 
33 cout << "Ingrese la cadena a comvertir a posfija" << endl; 
34 cin >> mychar; 
35 lon = strlen(mychar); 
36 for(int i(0) ; i <= lon ; i++) { 
37 elem.setElement(mychar[i]); 
38 switch(mychar[i]) { 
39 case '(': 
40 try { 
41 myStack.push(elem); 
42 } catch(Stack<E>::Exception ex) { 
43 cout << ex.what() << endl; 
44 } 
45 break; 
46 case ')': 
47 try { 
48 while(!myStack.isEmpty()){ 
49 if(myStack.getTop() == para ) { 
50 myStack.pop(); 
51 break; 
52 } else { 
53 myQueue.enqueue(myStack.getTop()); 
54 myStack.pop(); 
55 } 
56 } 
57 } catch(Stack<E>::Exception ex) { 
58 cout << ex.what() << endl; 
59 } 
60 break; 
61 case '+': 
62 try { 
63 if(myStack.isEmpty() == true) { 
64 myStack.push(elem); 
65 break; 
66 } 
67 if(myStack.getTop() == para ) { 
68 myStack.push(elem); 
69 break; 
70 } 
71 while(!myStack.isEmpty()) { 
72 if(myStack.getTop() == para ) { 
73 myStack.pop(); 
74 break; 
75 } else { 
76 myQueue.enqueue(myStack.getTop()); 
77 myStack.pop(); 
78 } 
79 } 
80 } catch(Stack<E>::Exception ex) { 
81 cout << ex.what() << endl; 
82 } 
83 case '-': 
84 try { 
85 if(myStack.isEmpty() == true) { 
86 myStack.push(elem); 
87 break; 
88 } 
89 if(myStack.getTop() == para) { 
90 myStack.push(elem); 
91 break; 
92 } 
93 while(!myStack.isEmpty()) { 
94 if(myStack.getTop() == para) { 
95 myStack.pop(); 
96 break; 
97 } else { 
98 myQueue.enqueue(myStack.getTop()); 
99 myStack.pop(); 
100 } 
101 } 
102 } catch(Stack<E>::Exception ex) { 
103 cout << ex.what() << endl; 
104 } 
105 case '*': 
106 try { 
107 if(myStack.isEmpty() == true) { 
108 myStack.push(elem); 
109 break; 
110 } 
111 if(myStack.getTop() == para) { 
112 myStack.push(elem); 
113 break; 
114 } 
115 if( myStack.getTop() == pot or myStack.getTop() == mul or myStack.getTop() == div ) { 
116 myQueue.enqueue(myStack.getTop()); 
117 myStack.pop(); 
118 myStack.push(elem); 
119 } else { 
120 myStack.push(elem); 
121 } 
122 
123 } catch(Stack<E>::Exception ex) { 
124 cout << ex.what() << endl; 
125 } 
126 break; 
127 case '/': 
128 try { 
129 if(myStack.isEmpty() == true) { 
130 myStack.push(elem); 
131 break; 
132 } 
133 if(myStack.getTop() == para) { 
134 myStack.push(elem); 
135 break; 
136 } 
137 if( myStack.getTop() == pot or myStack.getTop() == mul or myStack.getTop() == div ) { 
138 myQueue.enqueue(myStack.getTop()); 
139 myStack.pop(); 
140 myStack.push(elem); 
141 } else { 
142 myStack.push(elem); 
143 } 
144 } catch(Stack<E>::Exception ex) { 
145 cout << ex.what() << endl; 
146 } 
147 break; 
148 case '^': 
149 
150 try { 
151 if(myStack.isEmpty() == true) { 
152 myStack.push(elem); 
153 break; 
154 } 
155 if(myStack.getTop() == para) { 
156 myStack.push(elem); 
157 break; 
158 } 
159 if( myStack.getTop() == pot ) { 
160 myQueue.enqueue(myStack.getTop()); 
161 myStack.pop(); 
162 myStack.push(elem); 
163 } else { 
164 myStack.push(elem); 
165 } 
166 } catch(Stack<E>::Exception ex) { 
167 cout << ex.what() << endl; 
168 } 
169 break; 
170 default: 
171 try { 
172 myQueue.enqueue(elem); 
173 } catch(Stack<E>::Exception ex) { 
174 cout << ex.what() << endl; 
175 } 
176 break; 
177 } 
178 } 
179 try { 
180 while(!myStack.isEmpty()) { 
181 myQueue.enqueue(myStack.getTop()); 
182 myStack.pop(); 
183 } 
184 } catch(Stack<E>::Exception ex) { 
185 cout << ex.what() << endl; 
186 } 
187 cout << "El resultado es: "; 
188 while( !myQueue.isEmpty() ){ 
189 cout << myQueue.getFront(); 
190 myQueue.dequeue(); 
191 } 
192 cout << endl << endl; 
193 gets(mychar); 
194 return 0; 
195 } 
196 
E.h 
1 #ifndef E_H_INCLUDED 
2 #define E_H_INCLUDED 
3 
4 class E { 
5 private: 
6 char element; 
7 public: 
8 void setElement(const char&); 
9 char getElement(); 
10 bool operator == (const E&) const; 
11 bool operator != (const E&) const; 
12 bool operator <= (const E&) const; 
13 bool operator >= (const E&) const; 
14 bool operator > (const E&) const; 
15 bool operator < (const E&) const; 
16 friend std::ostream& operator << (std::ostream&, E&); 
17 }; 
18 
19 void E::setElement(const char& e){ 
20 element = e; 
21 } 
22 
23 char E::getElement(){ 
24 return element; 
25 } 
26 
27 bool E::operator == (const E& e) const { 
28 return element == e.element; 
29 } 
30 
31 bool E::operator != (const E& e) const { 
32 return element != e.element; 
33 } 
34 
35 bool E::operator >= (const E& e) const { 
36 return element >= e.element; 
37 } 
38 
39 bool E::operator > (const E& e) const { 
40 return element > e.element; 
41 } 
42 
43 bool E::operator <= (const E& e) const { 
44 return element <= e.element; 
45 } 
46 
47 bool E::operator < (const E& e) const { 
48 return element < e.element; 
49 } 
50 
51 std::ostream& operator << (std::ostream& os, E& s){ 
52 std::string aux; 
53 aux = s.element; 
54 os << aux; 
55 return os; 
56 } 
57 
58 
59 #endif // E_H_INCLUDED 
queue.h 
1 #ifndef QUEUE_H_INCLUDED 
2 #define QUEUE_H_INCLUDED 
3 
4 #include <string> 
5 #include <exception> 
6 
7 ///Definicion 
8 
9 template <class T> 
10 class Queue { 
11 public: 
12 class Exception: public std::exception 
13 { 
14 private: 
15 std::string msg; 
16 
17 public: 
18 explicit Exception(const char* message) : msg(message) { } 
19 
20 explicit Exception(const std::string& message) : msg(message) { } 
21 
22 virtual ~Exception() throw () { } 
23 
24 virtual const char* what() const throw () { 
25 return msg.c_str(); 
26 } 
27 }; 
28 
29 private: 
30 class Node 
31 { 
32 private: 
33 T* dataPtr; 
34 Node* prev; 
35 Node* next; 
36 
37 public: 
38 class Exception: public std::exception 
39 { 
40 private: 
41 std::string msg; 
42 
43 public: 
44 explicit Exception(const char* message) : msg(message) { } 
45 
46 explicit Exception(const std::string& message) : msg(message) { } 
47 
48 virtual ~Exception() throw () { } 
49 
50 virtual const char* what() const throw () { 
51 return msg.c_str(); 
52 } 
53 }; 
54 Node(); 
55 Node(const T&); 
56 
57 ~Node(); 
58 
59 T* getDataPtr(); 
60 T& getData(); 
61 Node* getPrev() const; 
62 Node* getNext() const; 
63 
64 void setDataPtr(T*); 
65 void setData(const T&); 
66 void setPrev(Node*); 
67 void setNext(Node*); 
68 }; 
69 
70 Node* headerPtr; 
71 
72 void copyAll(const Queue&); 
73 
74 void deleteAll(); 
75 
76 public: 
77 
78 Queue(); 
79 Queue(const Queue&); 
80 
81 ~Queue(); 
82 
83 bool isEmpty() const; 
84 
85 void enqueue(constT&); 
86 T dequeue(); 
87 
88 T& getFront(); 
89 
90 Queue& operator = (const Queue&); 
91 }; 
92 
93 ///Implementacion 
94 
95 using namespace std; 
96 
97 ///Node 
98 
99 template <class T> 
100 Queue<T>::Node::Node() : dataPtr(nullptr), prev(nullptr), next(nullptr) { } 
101 
102 template <class T> 
103 Queue<T>::Node::Node(const T& e) : dataPtr(new T(e)), prev(nullptr), next(nullptr) 
104 { 
105 if(dataPtr == nullptr) 
106 { 
107 throw Exception(" Memoria no disponible, creando nodo"); 
108 } 
109 } 
110 
111 template <class T> 
112 Queue<T>::Node::~Node() 
113 { 
114 dataPtr = nullptr; 
115 } 
116 
117 template <class T> 
118 T* Queue<T>::Node::getDataPtr() 
119 { 
120 return dataPtr; 
121 } 
122 
123 template <class T> 
124 T& Queue<T>::Node::getData() 
125 { 
126 return *dataPtr; 
127 } 
128 
129 template <class T> 
130 typename Queue<T>::Node* Queue<T>::Node::getPrev() const 
131 { 
132 return prev; 
133 } 
134 
135 template <class T> 
136 typename Queue<T>::Node* Queue<T>::Node::getNext() const 
137 { 
138 return next; 
139 } 
140 
141 template <class T> 
142 void Queue<T>::Node::setDataPtr(T* p) 
143 { 
144 dataPtr = p; 
145 } 
146 
147 template <class T> 
148 void Queue<T>::Node::setData(const T& e) 
149 { 
150 if(dataPtr == nullptr and (dataPtr = new T(e)) == nullptr) 
151 { 
152 throw Exception(" Memoria no disponible, Node::setData."); 
153 } 
154 
155 else 
156 { 
157 *dataPtr = e; 
158 } 
159 
160 } 
161 
162 template <class T> 
163 void Queue<T>::Node::setPrev(Queue<T>::Node* p) 
164 { 
165 prev = p; 
166 } 
167 
168 template <class T> 
169 void Queue<T>::Node::setNext(Queue<T>::Node* p) 
170 { 
171 next = p; 
172 } 
173 
174 ///Queue 
175 
176 ///private 
177 
178 template <class T> 
179 void Queue<T>::copyAll(const Queue<T>& l) 
180 { 
181 if(!l.isEmpty()){ 
182 Node* aux(l.headerPtr->getNext()); 
183 Node* newNode; 
184 while(aux != l.headerPtr) 
185 { 
186 try { 
187 if(newNode = new Node(aux->getData()) == nullptr) 
188 { 
189 throw Exception(" Memoria no disponible, copyAll"); 
190 } 
191 } catch (typename Queue<T>::Node::Exception ex) 
192 { 
193 throw Exception(ex.what()); 
194 } 
195 } 
196 
197 } 
198 } 
199 
200 template <class T> 
201 void Queue<T>::deleteAll() 
202 { 
203 Node* aux; 
204 
205 while(headerPtr->getNext() != headerPtr); 
206 { 
207 aux = headerPtr->getNext(); 
208 
209 headerPtr->setNext(aux->getNext()); 
210 
211 delete aux; 
212 } 
213 
214 headerPtr->setPrev(headerPtr); 
215 } 
216 
217 ///public 
218 
219 template <class T> 
220 Queue<T>::Queue() : headerPtr(new Node) 
221 { 
222 if(headerPtr == nullptr) 
223 { 
224 throw Exception(" La memoria no esta disponible, creando la Queue."); 
225 } 
226 
227 headerPtr->setPrev(headerPtr); 
228 headerPtr->setNext(headerPtr); 
229 } 
230 
231 template <class T> 
232 Queue<T>::Queue(const Queue<T>& l) : Queue() 
233 { 
234 copyAll(l); 
235 } 
236 
237 template <class T> 
238 Queue<T>::~Queue() 
239 { 
240 deleteAll(); 
241 
242 delete headerPtr; 
243 } 
244 
245 template <class T> 
246 Queue<T>& Queue<T>::operator = (const Queue<T>& l) 
247 { 
248 deleteAll(); 
249 
250 copyAll(l); 
251 
252 return *this; 
253 } 
254 
255 template <class T> 
256 bool Queue<T>::isEmpty() const 
257 { 
258 return headerPtr->getNext() == nullptr; 
259 } 
260 
261 template <class T> 
262 void Queue<T>::enqueue(const T& e) 
263 { 
264 Node* aux; 
265 
266 try { 
267 aux = new Node(e); 
268 } catch(typename Queue<T>::Node::Exception ex) { 
269 throw Exception(ex.what()); 
270 } 
271 
272 if(aux == nullptr) 
273 { 
274 throw Exception(" Memoria no disponible, enqueue."); 
275 } 
276 
277 aux->setPrev(headerPtr->getPrev()); 
278 aux->setNext(headerPtr); 
279 
280 headerPtr->getPrev()->setNext(aux); 
281 headerPtr->setPrev(aux); 
282 } 
283 
284 template <class T> 
285 T Queue<T>::dequeue() 
286 { 
287 if(isEmpty()) 
288 { 
289 throw Exception(" Insuficiencia de datos, dequeue."); 
290 } 
291 
292 T result(headerPtr->getNext()->getData()); 
293 
294 Node* aux(headerPtr->getNext()); 
295 
296 aux->getPrev()->setNext(aux->getNext()); 
297 aux->getNext()->setPrev(aux->getPrev()); 
298 
299 delete aux; 
300 
301 return result; 
302 } 
303 
304 template <class T> 
305 T& Queue<T>::getFront() 
306 { 
307 if(isEmpty()) 
308 { 
309 throw Exception(" Insuficiencia de dato, getFront"); 
310 } 
311 
312 return headerPtr->getNext()->getData(); 
313 } 
314 
315 #endif // QUEUE_H_INCLUDED 
316 
stack.h 
1 #ifndef STACK_H_INCLUDED 
2 #define STACK_H_INCLUDED 
3 
4 #include <string> 
5 #include <exception> 
6 
7 ///Definicion 
8 
9 template <class T> 
10 class Stack 
11 { 
12 public: 
13 class Exception: public std::exception 
14 { 
15 private: 
16 std::string msg; 
17 
18 public: 
19 explicit Exception(const char* message) : msg(message) { } 
20 
21 explicit Exception(const std::string& message) : msg(message) { } 
22 
23 virtual ~Exception() throw () { } 
24 
25 virtual const char* what() const throw () { 
26 return msg.c_str(); 
27 } 
28 }; 
29 
30 private: 
31 class Node 
32 { 
33 private: 
34 T data; 
35 Node* next; 
36 
37 public: 
38 Node(); 
39 Node(const T&); 
40 
41 T& getData(); 
42 Node* getNext() const; 
43 
44 void setData(const T&); 
45 void setNext(Node*); 
46 }; 
47 
48 Node* anchor; 
49 
50 void copyAll(const Stack&); 
51 
52 void deleteAll(); 
53 
54 public: 
55 
56 Stack(); 
57 Stack(const Stack&); 
58 
59 ~Stack(); 
60 
61 bool isEmpty() const; 
62 
63 void push(const T&); 
64 T pop(); 
65 
66 T& getTop(); 
67 
68 Stack& operator = (const Stack&); 
69 }; 
70 
71 ///Implementacion 
72 
73 using namespace std; 
74 
75 ///Node 
76 
77 template <class T> 
78 Stack<T>::Node::Node() : next(nullptr) { } 
79 
80 template <class T> 
81 Stack<T>::Node::Node(const T& e) : data(e), next(nullptr) { } 
82 
83 template <class T> 
84 T& Stack<T>::Node::getData() 
85 { 
86 return data; 
87 } 
88 
89 template <class T> 
90 typename Stack<T>::Node* Stack<T>::Node::getNext() const 
91 { 
92 return next; 
93 } 
94 
95 template <class T> 
96 void Stack<T>::Node::setData(const T& e) 
97 { 
98 data = e; 
99 } 
100 
101 template <class T> 
102 void Stack<T>::Node::setNext(Stack<T>::Node* p) 
103 { 
104 next = p; 
105 } 
106 
107 ///Stack 
108 
109 ///private 
110 
111 template <class T>///Copiar Stack 
112 void Stack<T>::copyAll(const Stack<T>& l) 
113 { 
114 Node* aux(l.anchor); 
115 Node* lastInserted(nullptr); 
116 Node* newNode; 
117 
118 while(aux != nullptr) 
119 { 
120 newNode = new Node(aux->getData()); 
121 
122 if(newNode == nullptr) 
123 { 
124 throw Exception("Memoria no disponible, copyAll"); 
125 } 
126 
127 if(lastInserted == nullptr) 
128 { 
129 anchor = newNode; 
130 } 
131 else 
132 { 
133 lastInserted->setNext(newNode); 
134 } 
135 
136 lastInserted = newNode; 
137 
138 aux = aux->getNext(); 
139 } 
140 } 
141 
142 template <class T>///Borrar todo 
143 void Stack<T>::deleteAll() 
144 { 
145 Node* aux; 
146 
147 while(anchor != nullptr) 
148 { 
149 aux = anchor; 
150 
151 anchor = anchor->getNext(); 
152 
153 delete aux; 
154 } 
155 } 
156 
157 ///public 
158 
159 template <class T>///Constructor 
160 Stack<T>::Stack() : anchor(nullptr) { } 
161 
162 template <class T>///Constructor copia 
163 Stack<T>::Stack(const Stack<T>& l) : anchor(nullptr) 
164 { 
165 copyAll(l); 
166 } 
167 
168 template <class T>///Desconstructor 
169 Stack<T>::~Stack() 
170 { 
171 deleteAll(); 
172 } 
173 
174 template <class T>///Operador de igual 
175 Stack<T>& Stack<T>::operator = (const Stack<T>& l) 
176 { 
177 deleteAll(); 
178 
179 copyAll(l); 
180 
181 return *this; 
182 } 
183 
184 template <class T>///Si esta vacia la lista 
185 boolStack<T>::isEmpty() const 
186 { 
187 return anchor == nullptr; 
188 } 
189 
190 template <class T>///Insertar Dato 
191 void Stack<T>::push(const T& e) 
192 { 
193 Node* aux(new Node(e)); 
194 
195 if(aux == nullptr) 
196 { 
197 throw Exception(" Memoria no disponible, push"); 
198 } 
199 
200 aux->setNext(anchor); 
201 
202 anchor = aux; 
203 } 
204 
205 template <class T>///Eliminar Dato 
206 T Stack<T>::pop() 
207 { 
208 if(isEmpty()) 
209 { 
210 throw Exception(" Insuficiencia de datos, pop"); 
211 } 
212 
213 T result(anchor->getData()); 
214 
215 Node* aux(anchor); 
216 
217 anchor = anchor->getNext(); 
218 
219 delete aux; 
220 
221 return result; 
222 
223 } 
224 
225 template <class T>///Recuperar posicion 
226 T& Stack<T>::getTop() 
227 { 
228 if(isEmpty()) 
229 { 
230 throw Exception(" Insuficiencia de datos, getTop"); 
231 } 
232 
233 return anchor->getData(); 
234 } 
235 
236 #endif // STACK_H_INCLUDED 
 
Capturas de pantalla: