Colas:
Una Cola es una coleccion ordenada de
elementos a partir de las cual se pueden eliminar
elementos de un extremo(llamado frente de la cola) y en
la cuel también se pueden agregar elementos en el otro
extremo(llamado parte posterior de la cola).
Las colas son estructuras de
tipo FIFO (first-in, first-out), ya que el primer
elemento en entrar a la cola será el primero en salir de
ella.
Existen muchísimos
ejemplos de colas en la vida real, como por ejemplo:
personas esperando en un teléfono público, niños
esperando para subir a un juego mecánico, estudiantes
esperando para subir a un camión escolar, etc.
Podemos representar a las colas
de dos formas :
- Como arreglos
- Como listas
ordenadas
Para trastar las colas como
arreglos de elementos, debemos definir el tamaño de la
cola y dos apuntadores, uno para accesar el primer
elemento de la lista y otro que guarde el último.
Las operaciones que nosotros
podemos realizar sobre una cola son las siguientes:
Las inserciones en la cola se
llevarán a cabo por atrás de la cola, mientras que las
eliminaciones se realizarán por el frente de la cola (
el primero en entrar es el primero en salir).
Lo
descrito anteriormente sera ilustrado por medio de
imagenes, para hacerlo mas claro:
 |
Lo primero
que se hace es crear una "cola." |
 |
Se va a trabajar con
una cola de 17 elementos:
1 ,2 , ... ,17 .
En donde el 1 es el
elemento al frente de la cola y el 17 el elemento
posterior de la misma.
|
 |
Cada que se agregan
elementos debe ser al final de la cola. De esta
manera se realiza una INSERCION la cual adiciona un
elemento en la parte posterior de la cola.
|
 |
La
insercion siempre se puede realizar puesto que no
existe límite en cuanto el numero de elementos
que puede contener una cola.En este caso ya
llegamos a los 17 con los que vamos a trabajar.
|
 |
Se puede
realizar una Extraccion en la cual se retira el
elemento del frente de la cola. |
 |
Como se puede
apreciar, en las colas siempre el primero en
entrar es el priemero en salir y el ultimo en
entrar el ultimo en salir. |
 |
La operación
de eliminacion se puede aplicar unicamente si la
cola no esta vacía, es decir no existe forma de
remover un elemento de una cola que no contiene
elementos. |
//Trabaja con 10
elementos.
int
arr[10];
void
push(){
int i;
for
(i=0; i<10;i++){
scanf("%i",arr[i]); } }
void
pop(){
int i;
for
(i=0; i<10;i++){
printf("%i \n",arr[i]); } }
|
Este es el
codigo de un pequeño
programa que
trabaja
con Colas, en
Lenguaje C.
|
Listas:
Una Lista enlazada
o encadenada es una colección de elementos ó nodos, en
donde cada uno contiene datos y un enlace o liga.
Un nodo es una
secuencia de caracteres en memoria dividida en campos (de
cualquier tipo). Un nodo siempre contiene la dirección
de memoria del siguiente nodo de información si este
existe.
Un apuntador es
la dirección de memoria de un nodo
El campo liga, que es
de tipo puntero, es el que se usa para establecer la liga
con el siguiente nodo de la lista. Si el nodo fuera el
último, este campo recibe como valor NIL (vacío).
Algunas de las
operaciones que podemos realizar sobre una lista enlazada
se veran en las sig. imagenes:
 |
Se crea una
Lista |
 |
La Insercion:
consiste en
agregar un nuevo nodo a la lista.
|
 |
Para esta operación se
pueden considerar tres casos:
- Insertar
un nodo al inicio.
- Insertar
un nodo antes o después de cierto nodo.
- Insertar
un nodo al final.
|
 |
Para insertar
un nodo en el cual almacenar inf., en una lista
que debe de crecer,se debe de buscar un nodo
vacio para ser agregado a la lista |
 |
EL Borrado: La operación de
borrado consiste en quitar un nodo de la lista,
redefiniendo las ligas que correspondan.
|
 |
Se pueden presentar
cuatro casos:
- Eliminar
el primer nodo.
- Eliminar
el último nodo.
- Eliminar
un nodo con cierta información.
- Eliminar
el nodo anterior o posterior al nodo
cierta con información.
|
 |
Se puede llegar a tener
un solo elemento que en este caso sera el ultimo
en haber sido introducido y tendra el apluntador
1. Sera el primer, ultimo y unico elemento. |
 |
Si se borra
el ultimo elemento se tendra nuevamente un lista
vacia. |
// Almacena una
cadena de caracteres
de tamaño 60
o menor.
Nodo{
char nom[60];
Nodo *liga;
}*tmp, *ptr,
*aux, *auxap;
void
insertar(){
int comp;
tmp = (Nodo*) malloc(sizeof(Nodo));
printf("Nombre: ");
scanf("%s",tmp->nom);
if (ptr->liga ==
NULL){
ptr->liga = tmp;
tmp->liga = NULL;
}else{
aux = ptr->liga;
comp = strncmp(aux->nom,tmp->nom,3);
if (comp
> 0) {
tmp->liga = aux;
ptr->liga = tmp; }
else{
aux = ptr->liga;
auxap = ptr;
comp = 0;
while ((comp <= 0) && (aux != NULL)){
comp = strncmp(aux->nom, tmp->nom,3);
if (comp <= 0){
aux =
aux->liga;
auxap =
auxap->liga;
} }
tmp->liga = aux;
auxap->liga = tmp; }
} }
void
ver(){
Nodo *aux;
aux = ptr->liga;
printf("Lista de Nombres \n");
while (aux != NULL){
printf("%s\n",aux->nom);
aux = aux->liga;
}
getch();
free(aux);
}
|
Este es el codigo de
un pequeño
programa que trabaja con Listas, en
Lenguaje C.
|
Pilas:
Las Pilas son
otro tipo de estructura de datos lineales, las cuales
presentan restricciones en cuanto a la posición en la
cual pueden realizarse las inserciones y las extracciones
de elementos.
Las pilas no son
estructuras de datos fundamentales, es decir, no están
definidas como tales en los lenguajes de programación.
Las pilas pueden representarse mediante el uso de :
- Arreglos.
- Listas enlazadas.
Para utilizar los
arreglos debemos definir el tamaño máximo de la pila,
además de un apuntador al último elemento insertado en
la pila el cual se denomina SP.
Las principales
operaciones que podemos realizar en una pila son:
- Insertar un
elemento (push).
- Eliminar un
elemento (pop).
 |
Creacion de
la Pila. |
 |
Una pila es
una lista de elementos en la que se pueden
insertar y eliminar elementos sólo por uno de
los extremos. En esta imagen se esta insertando
el primer elemento. |
 |
Al Insertar
un elemento se le llama Push. |
 |
De nuevo se
va a trabajar con 17 elementos. |
 |
Eliminacion
(Pop): Los
elementos de una pila serán eliminados en
orden inverso al que se insertaron. Es decir, el
último elemento que se metió a la pila será el
primero en salir de ella.
|
 |
Debido al
orden en que se insertan y eliminan los elementos
en una pila, también se le conoce como
estructura LIFO (Last In, First Out: último en
entrar, primero en salir). |
 |
En la vida
cotidiana existen muchos ejemplos de pilas, una
pila de platos en una alacena, una pila de latas
en un supermercado, una pila de papeles sobre un
escritorio, etc. En esta fig. esta
saliendo el ultimo elemento en la pila, el cual
fue el primero en entrar.
|
 |
Si
una pila contiene un solo elemento(como en la
figura anterior), y se realiza la opereción de
retiro, la pila resultante no contendra elementos
y en este caso se denomina "Pila
Vacia". |
Trabaja con 10
elementos
int
arr[10];
void
push(){
int i;
for
(i=0; i<10;i++){
scanf("%i",arr[i]); } }
void
pop(){
int i;
for
(i=10; i>0;i++){
printf("%i \n",arr[i]); } }
|
Este es el codigo de un
pequeño
programa que
trabaja con
Pilas, en
Lenguaje C.
|
CONCLUSIONES:
Despues de manejar algunos ejemplos de algunas
estructuras de datos ,nos damos cuenta de la importancia de estas ene le
manejo y recopilación de datos que se manejan en todos los hambitos de
la computación .
REFERENCIAS:
http://www1.mmu.edu.my/~mukund/dsal/appldsal.html
Estructura de Datos
en Pascal
Aaron M. Tenenbaum,
Moshe J. Augenstein
Ed. Prentice-Hall
Hispanoamericana, Mexico1989, Pag. 560
|
