Pilas
Definicin:
La pila es una estructura de datos que permite
almacenar datos en el orden LIFO (Last In First Out, en
espaol, "ltimo en entrar, primero en salir").
La recuperacin de los datos es realizada en el orden
inverso de su insercin.
Para el manejo de los datos cuenta con dos operaciones
bsicas: apilar (push), que coloca un objeto en la pila,
y su operacin inversa, retirar(o desapilar, pop), que
retira el ltimo elemento apilado.
Pila como tipo abstracto de datos
La pila es un contenedor de nodos y tiene dos operaciones bsicas: push (o apilar)
y pop (o desapilar).
Push: Aade un nodo a la parte superior de la pila, dejando por debajo el resto de los
nodos ya presentes en la pila.
Pop: Devuelve y elimina el actual nodo superior de la pila.
Una metfora que se utiliza con frecuencia es la idea de una pila de platos dispuesta en
una cafetera en un contenedor con un muelle que mantiene la pila a nivel. En esa serie,
solo el primer plato es visible y accesible para el usuario, todos las dems permanecen
ocultos. Como se aaden nuevos platos, cada nuevo plato se convierte en la parte
superior de la pila, permaneciendo escondidos debajo los dems. A medida que el plato
superior se extrae de la pila, el inmediatamente inferior pasa a ocupar la parte superior
de la pila. Dos principios importantes son ilustrados por esta metfora: nicamente se
accede al plato que se encuentra en la parte superior (el ltimo en depositarse), y el
resto de platos de la pila permanecen ocultos. Para extraer un plato distinto al superior
habr que extraer antes los que se encuentran sobre l.
Operaciones
Habitualmente, junto a las dos operaciones bsicas de apilar y desapilar
(push, pop), las pilas puede implementar otra serie de funciones:
Crear (constructor): crea la pila vaca.
Tamao (size): regresa el nmero de elementos de la pila.
Apilar (push): aade un elemento a la pila.
Desapilar (pop): lee y retira el elemento superior de la pila.
Leer ltimo (top o peek): lee el elemento superior de la pila sin
retirarlo.
Vaca (empty): devuelve cierto si la pila est sin elementos o falso en
caso de que contenga alguno.
La elaboracin del modelo de un
elemento de la pila
Para definir un elemento de la pila ser utilizado el
tipo struct.
El elemento de la pila contendr un campo dato y un
puntero siguiente.
El puntero siguiente tiene que ser de la misma clase
que el elemento, de lo contrario no va a poder apuntar
hacia el elemento.
El puntero siguiente permitir el acceso al prximo
elemento.
Para permitir las operaciones sobre la pila, vamos a
guardar ciertos elementos: el primer elemento, el
numero de elementos
El primer elemento, que se encuentra en la cabeza de la
pila, nos permitir realizar la operacin de recuperacin
de los datos situados en la parte superior de la pila. Para
ello, se utilizar otra estructura (no es obligatorio,
pueden ser utilizadas variables).
El puntero inicio indicar la direccin del primer elemento de la lista.
La variable tamao contiene el numero de elementos.
Cualquiera que sea la posicin en la lista, el
puntero inicio apunta siempre hacia el primer elemento,
que estar en la cabeza de la pila.
El campo tamao abarcar el numero de elementos de
la pila, cualquiera que sea la operacin efectuada sobre
la pila.
Colas
Concepto
Una cola es una estructura de datos, caracterizada por ser una secuencia
de elementos en la que la operacin de insercin push se realiza por un
extremo y la operacin de extraccin pop por el otro. Tambin se le llama
estructura FIFO (del ingls First In First Out), debido a que el primer
elemento en entrar ser tambin el primero en salir.
Utilizacin
Las colas se utilizan en sistemas informticos, transportes y operaciones
de investigacin (entre otros), dnde los objetos, personas o eventos son
tomados como datos que se almacenan y se guardan mediante colas para
su posterior procesamiento. Este tipo de estructura de datos abstracta se
implementa en lenguajes orientados a objetos mediante clases, en forma
de listas enlazadas.
Operaciones bsicas
Crear: se crea la cola vaca.
Encolar (aadir, entrar, insertar): se aade un elemento
a la cola. Se aade al final de esta.
Desencolar (sacar, salir, eliminar): se elimina el
elemento frontal de la cola, es decir, el primer elemento
que entr.
Frente (consultar, front): se devuelve el elemento
frontal de la cola, es decir, el primer elemento que entr.
Tipos
Colas simples: Se inserta por un sitio y se saca por otro, en
el caso de la cola simple se inserta por el final y se saca por
el principio. Para gestionar este tipo de cola hay que
recordar siempre cual es el siguiente elemento que se va a
leer y cual es el ultimo elemento que se ha introducido.
Colas circulares: En las colas circulares se considera que
despus del ultimo elemento se accede de nuevo al primero.
De esta forma se reutilizan las posiciones extraidas, el final
de la cola es a su vez el principio, crendose un circuito
cerrado.
Colas con prioridad: Las colas con prioridad se implementan
mediante listas o arrays ordenados. No nos interesa en este
caso que salgan en el orden de entrada sino con una
prioridad que le asignemos. Puede darse el caso que existan
varios elementos con la misma prioridad, en este caso saldr
primero aquel que primero llego (FIFO).
Ejemplos
Ejemplo 1
Ya hemos visto que las colas son casos particulares de listas abiertas, pero ms
simples. Como en los casos anteriores, veremos ahora un ejemplo de cola usando
clases.
Para empezar, y como siempre, necesitaremos dos clases, una para nodo y otra para
cola. Adems la clase para nodo debe ser amiga de la clase cola, ya que sta debe
acceder a los miembros privados de nodo.
class nodo {
public:
nodo(int v, nodo *sig = NULL) typedef nodo *pnodo;
{
class cola {
valor = v; public:
siguiente = sig; cola() : ultimo(NULL),
primero(NULL) {}
} ~cola();
void Anadir(int v);
private: int Leer();
int valor;
private:
nodo *siguiente; pnodo primero, ultimo;
}
friend class cola;
};
typedef nodo *pnodo;
Ejemplo 2
#include <iostream>
using namespace std;
typedef nodo *pnodo;
class nodo {
public: class cola {
nodo(int v, nodo *sig = NULL) { public:
cola() : ultimo(NULL),
valor = v; primero(NULL) {}
siguiente = sig; ~cola();
}
void Push(int v);
int Pop();
private:
private:
int valor;
pnodo ultimo;
nodo *siguiente; };
friend class cola;
};
cola::~cola() {
while(primero) Leer();
}
void cola::Anadir(int v) {
pnodo nuevo;
/* Crear un nodo nuevo */
nuevo = new nodo(v);
/* Si la cola no estaba vaca, aadimos el nuevo a continuacin de ultimo
*/
if(ultimo) ultimo->siguiente = nuevo;
/* Ahora, el ltimo elemento de la cola es el nuevo nodo */
ultimo = nuevo;
/* Si primero es NULL, la cola estaba vaca, ahora primero apuntar
tambin al nuevo nodo */
if(!primero) primero = nuevo;
}
int cola::Leer() {
pnodo nodo; /* variable auxiliar para manipular nodo */
int v; /* variable auxiliar para retorno */
/* Nodo apunta al primer elemento de la pila */
nodo = primero;
if(!nodo) return 0; /* Si no hay nodos en la pila retornamos 0 */
/* Asignamos a primero la direccin del segundo nodo
*/
primero = nodo->siguiente;
/* Guardamos el valor de retorno */
v = nodo->valor;
/* Borrar el nodo */
delete nodo;
/* Si la cola qued vaca, ultimo debe ser NULL
tambin*/
if(!primero) ultimo = NULL;
return v;
}
int main() {
cola Cola;
[Link](20);
cout << "Aadir(20)" << endl;
[Link](10);
cout << "Aadir(10)" << endl;
cout << "Leer: " << [Link]() << endl;
[Link](40);
cout << "Aadir(40)" << endl;
[Link](30);
cout << "Aadir(30)" << endl;
cout << "Leer: " << [Link]() << endl;
cout << "Leer: " << [Link]() << endl;
[Link](90);
cout << "Aadir(90)" << endl;
cout << "Leer: " << [Link]() << endl;
cout << "Leer: " << [Link]() << endl;
return 0;
{
