Ftf6

República Bolivariana de Venezuela
Ministerio del Poder Popular Para la Educación Superior
Universidad Bicentenaria de Aragua
Escuela de Ingeniería de Sistemas
Núcleo – Apure
Prof. Bachiller:
ING. Robert Espinoza Gonzales Vicente
C.I: 19250593
BIRUACA. DICIEMBRE DEL 2009
Pilas
Las pilas son unas de las estructuras de datos más usadas dentro de la programación. Lasestructuras de datos son, como su nombre lo indica, estructuras que guardan datos. Las pilas son aquellas que solo tienen 2 operaciones, Push (Inserción) y Pop (Eliminación) la cual solo se puede efectuar por un extremo llamado Top. Pero no son solamente eso, ya que también tienen operaciones básicas para acceder e insertar nuevos datos, lo que las hace eficientes y muy útiles al crear cierto tipode programas.
Operaciones.
Una pila cuenta con 2 operaciones imprescindibles: apilar y desapilar:
Crear: se crea la pila vacía.
Apilar: se añade un elemento a la pila.
Desapilar: se elimina el elemento frontal de la pila.
Cima: devuelve el elemento que está en la cima de la pila.
Vacía: devuelve cierto si la pila está vacía o falso en caso contrario.Implementación de la Pila a través de un Algoritmo Lógico.
La biblioteca de plantillas de C++ estándar proporciona una "pila" clase templated que se limita a sólo apilar/desapilar operaciones. Java contiene una biblioteca de la clase Pila que es una especialización de Vector. Esto podría ser considerado como un defecto, porque el diseño heredado get () de Vector método LIFO ignora lalimitación de la Pila.
Ejemplo:
ifndef PILA define PILA // define la pila template
class Pila {
private:
struct Nodo {
T elemento;
Nodo* siguiente; // coloca el nodo en la segunda posicion
}* ultimo;
unsigned int elementos;
public:
Pila() {
elementos = 0;
}
~Pila() {
while (elementos != 0) pop();
}
void push(const T& elem) {
Nodo* aux = newNodo;
aux->elemento = elem;
aux->siguiente = ultimo;
ultimo = aux;
++elementos;
}
void pop() {
Nodo* aux = ultimo;
ultimo = ultimo->siguiente;
delete aux;
--elementos;
}
T cima() const {
return ultimo->elemento;
}
bool vacia() const {
return elementos == 0;
}
unsigned int altura() const {
return elementos;
}
};
endif De forma másespecífica se puede denotar de la siguiente forma:
Implementación Mediante Estructuras Estáticas (apilar).
Algoritmo Apilar
Entradas
x: Valor { elemento que se desea insertar }
stack: Pila de Valor
Salidas
stack
Inicio
{ comprobar si en la pila se pueden insertar más elementos }
{ esto es necesario por el tipo de representación de la estructura }
Si ( stack.Cima = MAX )entonces
Error "pila llena"
Sino
stack.Cima ← stack.Cima + 1
stack.Info [stack.Cima] ← x
Fin_sino
Fin
bool Pila::Apilar (Valor x)
{
bool error;
if (cima == MAX)
error = true;
else
{
error = false;
info[cima] = x;
cima++;
}
return error;
}
Implementación Mediante Estructuras Estáticas (desapilar).
La operación de borrado elimina de laestructura el elemento situado en la cima. Normalmente recibe el nombre de Pop en la bibliografía inglesa. El algoritmo de borrado sería:
Algoritmo Desapilar
Entradas
stack: Pila de Valor
Salidas
stack
x: Valor
Inicio
{ comprobar si se pueden eliminar elementos de la pila }
{ esta operación no depende de la representación, siempre es necesaria }
Si ( Pila_Vacia ( stack) ) entonces
Error “pila vacia”
sino
stack.Cima ← stack.Cima - 1
Fin_si
Fin
Resolución de Problemas con Pilas.
La búsqueda de la solución de un problema, es independientemente de si el enfoque es exhaustivo u óptimo, necesita espacio en la pila. Ejemplos de búsqueda exhaustiva métodos son fuerza bruta y backtraking. Ejemplos de búsqueda óptima a explorar métodos, son...