Una pila:
Es una estructura de datos homogénea (elementos del mismo tipo), secuencial y de tamaño variable. Sólo es posible un modo de acceso a esta estructura: a través de la cabeza de la pila. De este modo podemos añadir un elemento a la cabeza de la pila o extraer un elemento de la cabeza de la pila. Debido a que las operaciones de extracción e inserción se realizan por el mismo extremo, el último elemento en ser añadido será el primero en ser extraído; por ello a estas estructuras se las conoce con el nombre de LIFO ( last-in, first-out; último en entrar, primero en salir).
Es una estructura de datos homogénea (elementos del mismo tipo), secuencial y de tamaño variable. Sólo es posible un modo de acceso a esta estructura: a través de la cabeza de la pila. De este modo podemos añadir un elemento a la cabeza de la pila o extraer un elemento de la cabeza de la pila. Debido a que las operaciones de extracción e inserción se realizan por el mismo extremo, el último elemento en ser añadido será el primero en ser extraído; por ello a estas estructuras se las conoce con el nombre de LIFO ( last-in, first-out; último en entrar, primero en salir).
Un ejemplo típico de pila lo constituye un montón de platos: Cuando se
quiere introducir un nuevo plato, éste se coloca en la posición más
accesible, encima del último plato. Cuando se toma un plato, éste se
extrae, igualmente, del punto más accesible, el último que se ha
introducido. O, si somos más estrictos, otro ejemplo sería una caja
llena de libros. Sólo podemos ver cuál es el libro que está más arriba
en la caja, y si ponemos o tomamos un libro, sólo podremos actuar sobre
este primer libro. No podemos siquiera saber el número total de libros
guardados en la pila. Sólo sabremos el número de elementos de la pila de
libros si previamente los sacamos hasta vaciar la caja.
Operaciones con Pila Asociadas con la estructura pila existen una
serie de operaciones necesarias para su manipulación. Éstas son:
Iniciación de la estructura: - Crear la pila (CrearPila): La operación
de creación de la pila inicia la pila como vacía. Operaciones para
añadir y eliminar información: - Añadir elementos en la cima (Apilar):
pondrá un nuevo elemento en la parte superior de la pila. Eliminar
elementos de la cima (Desapilar): lo que hará será devolver el elemento
superior de la cima y eliminarlo de la pila.
Operaciones
Una pila cuenta con 2 operaciones imprescindibles: apilar y
desapilar, a las que en las implementaciones modernas de las pilas se
suelen añadir más de uso habitual.
- Crear: se crea la pila vacía. (constructor)
- Tamaño: regresa el numero de elementos de la pila. (size)
- Apilar: se añade un elemento a la pila.(push)
- Desapilar: se elimina el elemento frontal de la pila.(pop)
- Cima: devuelve el elemento que esta en la cima de la pila. (top o peek)
- Vacía: devuelve cierto si la pila está vacía o falso en caso contrario (empty).
Pila como tipo abstracto de datos:
A modo de resumen tipo de datos, la pila es un contenedor de nodos y tiene dos operaciones básicas: push (o apilar) y pop
(o desapilar). 'Push' añade un nodo a la parte superior de la pila,
dejando por debajo el resto de los nodos. 'Pop' elimina y devuelve el
actual nodo superior de la pila. Una metáfora que se utiliza con
frecuencia es la idea de una pila de platos en una cafetería con muelle
de pila. En esa serie, sólo la primera placa es visible y accesible para
el usuario, todas las demás placas permanecen ocultas. Como se añaden
las nuevas placas, cada nueva placa se convierte en la parte superior de
la pila, escondidos debajo de cada plato, empujando a la pila de
placas. A medida que la placa superior se elimina de la pila, la segunda
placa se convierte en la parte superior de la pila. Dos principios
importantes son ilustrados por esta metáfora: En primer lugar la última
salida es un principio, la segunda es que el contenido de la pila está
oculto. Sólo la placa de la parte superior es visible, por lo que para
ver lo que hay en la tercera placa, el primer y segundo platos tendrán
que ser retirados.
Ejemplo en c++:
#ifndef PILA
#define PILA // define la pila
template <class T>
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 = new Nodo;
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
Una cola:
Es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. También se le llama estructura FIFO (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir.
Las colas se utilizan en sistemas informáticos, transportes y operaciones de investigación
(entre otros), dónde 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.
Ejemplos de colas en la vida real serían:
Operaciones Básicas:
- Crear: se crea la cola vacía.
- Encolar (añadir, entrar, insertar): se añade un elemento a la cola. Se añade al final de esta.
- Desencolar (sacar, salir, eliminar): se elimina el elemento frontal de la cola, es decir, el primer elemento que entró.
#ifndef COLA
#define COLA // Define la cola
template <class T>
class Cola{
private:
struct Nodo{
T elemento;
struct Nodo* siguiente; // coloca el nodo en la segunda posición
}* primero;
struct Nodo* ultimo;
unsigned int elementos;
public:
Cola(){
elementos = 0;
}
~Cola(){
while (elementos != 0) pop();
}
void push(const T& elem){
Nodo* aux = new Nodo;
aux->elemento = elem;
if (elementos == 0) primero = aux;
else ultimo->siguiente = aux;
ultimo = aux;
++elementos;
}
void pop(){
Nodo* aux = primero;
primero = primero->siguiente;
delete aux;
--elementos;
}
T consultar() const{
return primero->elemento;
}
bool vacia() const{
return elementos == 0;
}
unsigned int size() const{
return elementos;
}
};
#endif
Listas enlazadas lineales
Listas simples enlazadas
La lista enlazada básica es la lista enlazada simple la cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo en la lista, o al valor NULL o a la lista vacía, si es el último nodo.
Lista Doblemente Enlazada
Un tipo de lista enlazada más sofisticado es la lista doblemente enlazada o lista enlazadas de dos vías. Cada nodo tiene dos enlaces: uno apunta al nodo anterior, o apunta al valor NULL si es el primer nodo; y otro que apunta al nodo siguiente, o apunta al valor NULL si es el último nodo.
Listas enlazadas circulares
En una lista enlazada circular, el primer y el último nodo están
unidos juntos. Esto se puede hacer tanto para listas enlazadas simples
como para las doblemente enlazadas. Para recorrer una lista enlazada
circular podemos empezar por cualquier nodo y seguir la lista en
cualquier dirección hasta que se regrese hasta el nodo original. Desde
otro punto de vista, las listas enlazadas circulares pueden ser vistas
como listas sin comienzo ni fin. Este tipo de listas es el más usado
para dirigir buffers para “ingerir” datos, y para visitar todos los
nodos de una lista a partir de uno dado.
Una lista enlazada circular que contiene tres valores enteros
Listas enlazadas circulares simples
Cada nodo tiene un enlace, similar al de las listas enlazadas simples,
excepto que el siguiente nodo del último apunta al primero. Como en una
lista enlazada simple, los nuevos nodos pueden ser solo eficientemente
insertados después de uno que ya tengamos referenciado. Por esta razón,
es usual quedarse con una referencia solamente al último elemento en una
lista enlazada circular simple, esto nos permite rápidas inserciones al
principio, y también permite accesos al primer nodo desde el puntero
del último nodo.
En una lista enlazada doblemente circular, cada nodo tiene dos
enlaces, similares a los de la lista doblemente enlazada, excepto que el
enlace anterior del primer nodo apunta al último y el enlace siguiente
del último nodo, apunta al primero. Como en una lista doblemente
enlazada, las inserciones y eliminaciones pueden ser hechas desde
cualquier punto con acceso a algún nodo cercano. Aunque estructuralmente
una lista circular doblemente enlazada no tiene ni principio ni fin, un
puntero de acceso externo puede establecer el nodo apuntado que está en
la cabeza o al nodo cola, y así mantener el orden tan bien como en una
lista doblemente enlazada.
A veces las listas enlazadas tienen un nodo centinela (también llamado falso nodo o nodo ficticio)
al principio o al final de la lista, el cual no es usado para guardar
datos. Su propósito es simplificar o agilizar algunas operaciones,
asegurando que cualquier nodo tiene otro anterior o posterior, y que
toda la lista (incluso alguna que no contenga datos) siempre tenga un
“primer y último” nodo.
Las listas enlazadas son usadas como módulos para otras muchas estructuras de datos, tales como pilas, colas y sus variaciones.
El campo de datos de un nodo puede ser otra lista enlazada. Mediante
este mecanismo, podemos construir muchas estructuras de datos enlazadas
con listas; esta practica tiene su origen en el lenguaje de programación
Lisp, donde las listas enlazadas son una estructura de datos primaria
(aunque no la única), y ahora es una característica común en el estilo
de programación funcional.
A veces, las listas enlazadas son usadas para implementar vectores
asociativos, y estas en el contexto de las llamadas listas asociativas.
Hay pocas ventajas en este uso de las listas enlazadas; hay mejores
formas de implementar éstas estructuras, por ejemplo con árboles
binarios de búsqueda equilibrados. Sin embargo, a veces una lista
enlazada es dinámicamente creada fuera de un subconjunto propio de nodos
semejante a un árbol, y son usadas más eficientemente para recorrer
ésta serie de datos.
Ejemplo:
#include <stdio.h> /* for printf */ #include <stdlib.h> /* for malloc */ typedef struct ns { int data; struct ns *next; } node; node *list_add(node **p, int i) { /* algunos compiladores no requieren un casting del valor del retorno para malloc */ node *n = (node *)malloc(sizeof(node)); if (n == NULL) return NULL; n->next = *p; *p = n; n->data = i; return n; } void list_remove(node **p) { /* borrar cabeza*/ if (*p != NULL) { node *n = *p; *p = (*p)->next; free(n); } } node **list_search(node **n, int i) { while (*n != NULL) { if ((*n)->data == i) { return n; } n = &(*n)->next; } return NULL; } void list_print(node *n) { if (n == NULL) { printf("lista esta vacía\n"); } while (n != NULL) { printf("print %p %p %d\n", n, n->next, n->data); n = n->next; } } int main(void) { node *n = NULL; list_add(&n, 0); /* lista: 0 */ list_add(&n, 1); /* lista: 1 0 */ list_add(&n, 2); /* lista: 2 1 0 */ list_add(&n, 3); /* lista: 3 2 1 0 */ list_add(&n, 4); /* lista: 4 3 2 1 0 */ list_print(n); list_remove(&n); /* borrar primero(4) */ list_remove(&n->next); /* borrar nuevo segundo (2) */ list_remove(list_search(&n, 1)); /* eliminar la celda que contiene el 1 (primera) */ list_remove(&n->next); /* eliminar segundo nodo del final(0)*/ list_remove(&n); /* eliminar ultimo nodo (3) */ list_print(n); return 0; }
