ed cap4 pilascolas12010

Estructura de Datos

Pilas Colas

Prof.: Mauricio Solar Prof.: Lorna Figueroa

Primer Semestre, 2010

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

Indice

TDA: Pilas TDA: Colas Colas de Prioridad Anillos BiColas BiColas Circulares


Pilas - Stack

Una de las estructuras de datos ms primitivas y ms antiguas en la ciencia de los computadores.

A pesar de ser tan simple, es esencial en los compiladores, SS.OO., etc.

Se pueden representar como una lista lineal que crece y decrece por el mismo extremo. El ltimo elemento que se incorpora a la estructura, es el

nico que se puede consultar y eliminar.

trabajos

LIFOEntradaSalida


Pilas - Stack

Es un tipo lineal de datos, secuencia de elementos de un tipo, una estructura tipo LIFO (Last In First Out) ltimo en entrar primero en salir.

Son un subconjunto de las listas, en donde las eliminaciones e inserciones se realizan en un solo extremo.

trabajos

LIFOEntradaSalida


Aplicaciones de las Pilas

Aplicaciones Directas: Histrico de pginas visitadas en un browser de web. Secuencia de undo en un editor de textos. Cadena de llamadas a mtodos en JVM o medioambiente

runtime en C++ Parsers en Compiladores (reconocedores sintcticos). SSOO. Convertir notacin infija a posfija o prefija. Implementacin de recursividad.

Aplicaciones Indirectas: Estructuras de datos auxiliares para algoritmos Componentes de otras estructuras de datos.


Ejemplo Aplicacin de las pilas

Suponga que se quiere evaluar una expresin aritmtica, mediante un proceso que se basa en guardar dicha expresin en dos pilas: una de operadores (+, -, * y /) y otra de operandos (nmeros naturales).


Ejemplo Aplicacin de las pilas

El mtodo consiste en seguir el siguiente proceso de forma reiterada:

1. Si la pila de operadores est vaca, la cima de la de operandos contiene el resultado final.

2. En caso contrario, tomar los dos operandos de la cima de la pila y operarlos segn el operador de la cima de la otra pila. El resultado colocarlo en la cima de la pila de operandos.

*-+

4231

-+

831 +

51 9

Iteracin 1 Iteracin 2 Iteracin 3


Definicin del TAD Pilas

Se definir la semntica de las operaciones del TDA Pila en trminos de las operaciones del TDA Lista.

Operaciones: CrearPilaVaca( P ) PilaVaca( P ) B Apilar( x, P ) Desapilar( P ) Tope( P ) E

apilar desapilar

tope



CrearPilaVaca: Pila Pila CrearPilaVaca(P) = CrearListaVaca(P)

Invocacin: CrearPilaVaca(P)

CrearPilaVaca: Pila Pila CrearPilaVaca(P) = CrearListaVaca(P)

Invocacin: CrearPilaVaca(P)

PilaVaca: Pila Lgico PilaVaca(P) = ListaVaca(P)

Invocacin: PilaVaca(P)

PilaVaca: Pila Lgico PilaVaca(P) = ListaVaca(P)

Invocacin: PilaVaca(P)

Apilar: Elemento x Pila Pila Apilar( x, P ) = Insertar( x, Primera(P), P )

Invocacin: Apilar(x,P)

Apilar: Elemento x Pila Pila Apilar( x, P ) = Insertar( x, Primera(P), P )

Invocacin: Apilar(x,P)



Desapilar: Pila Pila

Desapilar( P ) {Si (no ListaVaca(P))

Eliminar( Primera(P), P )sino Error

}

Invocacin: Despilar(P)

Desapilar: Pila Pila

Desapilar( P ) {Si (no ListaVaca(P))

Eliminar( Primera(P), P )sino Error

}

Invocacin: Despilar(P)



Tope: Pila Elemento

Tope( P ) {Si (no ListaVaca(P))

Retornar( Recuperar(Primera(P), P) )Sino Error

}

Invocacin: Tope(P)

Tope: Pila Elemento

Tope( P ) {Si (no ListaVaca(P))

Retornar( Recuperar(Primera(P), P) )Sino Error

}

Invocacin: Tope(P)


Aplicaciones con TAD Pila

void MostrarPila(Pila P) {Pila p1;CrearPilaVacia( p1 )PasarPila( P, p1 ) // definirlamientras no PilaVacia( p1 ) {

Imprimir( Tope(p1) )Apilar( Tope(p1), P )Desapilar( p1 )

}}

void MostrarPila(Pila P) {Pila p1;CrearPilaVacia( p1 )PasarPila( P, p1 ) // definirlamientras no PilaVacia( p1 ) {

Imprimir( Tope(p1) )Apilar( Tope(p1), P )Desapilar( p1 )

}}


Pila PasarPila( Pila Origen ) {Pila Dest;mientras (no PilaVacia( Origen ))

Apilar( Tope(Origen), Dest )Desapilar( Origen )

}return Dest;

}

Pila PasarPila( Pila Origen ) {Pila Dest;mientras (no PilaVacia( Origen ))

Apilar( Tope(Origen), Dest )Desapilar( Origen )

}return Dest;

}

Aplicaciones con TAD Pila


PILAS

La representacin grfica de una pila es como la de cualquier estructura dinmica:

...

tope

NULL


PILAS Implementaciones

typedef struct nodoP {tElemento info;struct nodoP* sig;

}

Las pilas se implementan como una lista enlazada simple. El puntero de la lista (el tope) apunta al primer nodo de la

pila.

pila

tope a1 a2 an.


boolean EstaVacia (struct nodoP* tope) {return (tope sig = = NULL);// Verdadero si est vaca

}

boolean EstaVacia (struct nodoP* tope) {return (tope sig = = NULL);// Verdadero si est vaca

}




void Push (tElemento x, struct nodoP* tope) {struct nodoP* q;q = (struct nodoP*) malloc (sizeof (struct nodoP));q info = x; // almacena el elemento q sig = tope; // enlaza al nodo con el resto tope = q; // y lo pone en la cabeza

}

void Push (tElemento x, struct nodoP* tope) {struct nodoP* q;q = (struct nodoP*) malloc (sizeof (struct nodoP));q info = x; // almacena el elemento q sig = tope; // enlaza al nodo con el resto tope = q; // y lo pone en la cabeza

}


tElemento Pop (struct nodoP* tope) {struct nodoP* temp;

tElemento x;if (EstaVaca(tope))

printf (Error: pila vaca);else {

x = tope info;temp = tope; // Se eliminar el tope tope = tope sig;free(temp);return(x);

}}

tElemento Pop (struct nodoP* tope) {struct nodoP* temp;

tElemento x;if (EstaVaca(tope))

printf (Error: pila vaca);else {

x = tope info;temp = tope; // Se eliminar el tope tope = tope sig;free(temp);return(x);

}}



Ejemplo

10 10

100

10

100

1000

10

100

10

100

1

10

100

push(10) push(100) push(1000) pop() push(1) pop()


Expresiones infijas, prefijas, postfijas

Ejemplo de suma de dos operandos: Infija A + B (operador va entre operandos ) Prefija o polaca + A B (operador va antes que

operandos) Postfija o polaca inversa A B + (operador va despus de

operandos) Solo existe una expresin prefija y una postfija para cada

expresin algebraica. Para evaluar estas expresiones se usan las pilas.


Notacin polaca inversa (postfija)

Para evaluar la expresin aritmtica:

Se sigue el orden indicado por las flechas, (segn prioridad de operadores y uso de parntesis).

2b b 4 a c2 a

(b + (b^2 4 * a * c) ^ 0.5) / (2 * a)

6 1 4 2 3 5 8 7


Notacin polaca inversa (postfija)

Para eliminar esta dificultad, se hace una traduccin de las expresiones aritmticas a notacin postfija.

Esta notacin tiene la ventaja de que las operaciones aparecen en el orden en que se efecta realmente la evaluacin.


Notacin postfija

La idea bsica detrs de la notacin de cadenas polacas es que los operadores se escriben al final y no en medio de las expresiones. A + B se escribe como A B +. En esta forma, el operador + se considera como una

instruccin para sumar los valores de las dos variables que lo preceden inmediatamente. Ejemplo:

La clave de la traduccin de notacin infija a posfija es la prioridad de los operadores: ( ), + -, * /, ^


Notacin postfija

Reglas bsicas para convertir expresiones infijas a posfijas:1. Si el elemento es un ( se coloca directamente en la pila de

operadores.2. Si el elemento es un ), los operadores de la pila se transfieren

uno a uno, al extremo derecho de la expresin posfija hasta llegar a un (. Este se saca pero no va a la salida.

3. Si el elemento localizado es una variable, se coloca inmediatamente en el extremo derecho de la expresin posfijaque se est creando.

4. Si el elemento es un operador y es de menor precedencia que el operador en la pila, el operador de la pila se saca y va a lasalida, continuando de esta manera hasta encontrar un ( o hasta que el operador de la pila sea de menor precedencia. Cuando esto ocurre, el operador en turno se apila.


Conversin infija a postfija

Ecuacin cuadrtica

En notacin infija:

( -b + ( b ^ 2 4 * a * c ) ^ ( 1 / 2 ) ) / ( 2 * a )

En notacin postfija:

-b b 2 ^ 4 a c * * 1 2 / ^ + 2 a * /

2b b 4 a c2 a


1. Implementar la pila 2. Repetir hasta encontrar el fin de la expresin postfija

Tomar un carcter. Si el carcter es un operando colocarlo en la pila. Si el carcter es un operador entonces sacar los dos

valores del tope de la pila (operando2 operando1), aplicar el operador (operando1 operador operando2) y colocar el resultado en el nuevo tope de la pila.

Estructura de datos y organizacin de archivos. Mary E. Loomis. Prentice Hall. 2a Ed.

www.itlp.edu.mx/publica/tutoriales/estru1/33.htmthales.cica.es/rd/Recursos/rd99/ed99-0636-03/notacion_polaca.html

Algoritmo


Para evaluar una expresin postfija con pilas:i = 1Mientras i < Longitud(expresion)

si expresin[i] es operandoInsertar expresion[i] en la pila

sino {es operador}Extraer dos elementos de la pilaoperarlos segn el operador,insertar el resultado de nuevo en la pila

FinMientrasvalor = cimaPila

Algoritmo para evaluar una expresin postfija


Aplicacin: Invertir una Pila

nodoP InvPila(nodoP *tope) {

// Funcin que invierte una pilatElemento x;nodoP *tope1;while( !EstaVacia(tope) ) {

x = Pop(tope); Push(x, tope1);

}return(tope1);

}

nodoP InvPila(nodoP *tope) {

// Funcin que invierte una pilatElemento x;nodoP *tope1;while( !EstaVacia(tope) ) {

x = Pop(tope); Push(x, tope1);

}return(tope1);

}


Implementacin en C

#include #include

typedef struct nodoP {int valor;struct nodoP *sig;

} tipoNodo;

typedef tipoNodo *pNodo;typedef tipoNodo *Pila;

// Prototipo de las funciones void Push(Pila *p, int x);int Pop(Pila *p);

#include #include

typedef struct nodoP {int valor;struct nodoP *sig;

} tipoNodo;

typedef tipoNodo *pNodo;typedef tipoNodo *Pila;

// Prototipo de las funciones void Push(Pila *p, int x);int Pop(Pila *p);


Ejemplo

Algoritmo para encontrar el factorial de un nmero mediante pilas

leer n;mientras n > 1 {push(n);n = n-1;

}factorial = 1;mientras pila no est vaca

factorial = factorial * pop();


Ejercicios

1. Evaluar, indicando en cada paso el estado de la pila:Pila p = (Pila *)malloc(sizeof(Pila));

a) Pop ( Pop ( Push ( 3, Pop ( Push ( 4, Push ( 5, Push ( 6, p ) ) ) ) ) ) )

b) EstaVacia(Pop(Pop(Push( 8,p))))

c) InvPila( Push ( 3, Pop ( Push ( 4, Push ( 5, Push ( 6, p ) ) ) ) ) ) ) )

2. Escribir una funcin que permita contar todos los elementos pares que estn en una pila dada.


COLASCOLAS


Colas - queue

Es una abstraccin til con muchos paralelismos en la vida real: colas de espera en bancos, supermercados, etc Ello hace que su importancia sea crucial en simulaciones.

Computacionalmente hay muchos casos en los que aparecen colas de espera, por ejemplo: Procesos que esperan a ser ejecutados en sistemas

multitarea Procesos batch de clculo intensivo Acceso a recursos compartidos (impresora)


Colas - queue

Aplicaciones Indirectas:

Estructuras de datos auxiliares para algoritmos. Componentes de otras estructuras de datos.


Colas

Tipo de dato lineal con estructura FIFO (First In, First Out),indica que el primer elemento que se incorpor a la estructura, ser el primero que salga, y el nico que se puede consultar en un momento dado.

trabajos

entrada

salida

FIFO


Colas

Las colas son un subconjunto de las listas, en donde las eliminaciones se dan al comienzo de la lista y las inserciones al final.

Los elementos se procesan en el orden como se reciben (similar a la cola de impresin en redes).

Cuando se desea accesar un elemento que no est en un extremo, obligadamente se debe realizar una operacin desplazamiento de los nodos anteriores (o posteriores) a l.

trabajos

entrada

salida

FIFO


Definicin del TAD Cola

CrearColaVaca( C ) ColaVaca( C ) B PonerEnCola( x, C ) SacarDeCola( C ) Frente( C ) E

encolar

desencolar

final

frente



CrearColaVaca: Cola Cola CrearColaVaca(C) = CrearListaVaca(C)

Invocacin: CrearColaVaca(C)

CrearColaVaca: Cola Cola CrearColaVaca(C) = CrearListaVaca(C)

Invocacin: CrearColaVaca(C)

ColaVaca: Cola LgicoColaVaca(C) = ListaVaca(C)

Invocacin: ColaVaca(C)

ColaVaca: Cola LgicoColaVaca(C) = ListaVaca(C)

Invocacin: ColaVaca(C)

PonerEnCola: Elemento x Cola Cola PonerEnCola( x, C ) = Insertar( x, Fin(C), C )

Invocacin: PonerEnCola(x, C)

PonerEnCola: Elemento x Cola Cola PonerEnCola( x, C ) = Insertar( x, Fin(C), C )

Invocacin: PonerEnCola(x, C)



SacarDeCola: Cola Cola

SacarDeCola( C ) {Si (no ListaVaca(C))

Eliminar( Primera(C), C )sino Error

}

Invocacin: SacarDeCola (C)

SacarDeCola: Cola Cola

SacarDeCola( C ) {Si (no ListaVaca(C))

Eliminar( Primera(C), C )sino Error

}

Invocacin: SacarDeCola (C)



Frente: Cola Elemento

Frente( C ) {Si (no ListaVaca(C))

retornar( Recuperar(Primera(C), C) )Sino Error

}

Invocacin: Frente(C)

Frente: Cola Elemento

Frente( C ) {Si (no ListaVaca(C))

retornar( Recuperar(Primera(C), C) )Sino Error

}

Invocacin: Frente(C)


Colas - Implementacin

Estructura para los nodos:

typedef struct TColas {tElemento info;struct tColas* sig;

}TColas *tCola;

info sig

Entrada de Dato

Salida de Dato


Colas

Representacin grfica:

...

frente

NULL

final

Por aqu se sale Por aqu entran


Colas

Otra representacin:


Colas

Se dispone de un puntero ms. Cuando la cola est vaca se tiene la siguiente situacin:

frente

NULL

final


ColasINSERTAR(dato;frente;final) {

Nuevo(p); p->info = dato;

if final = = NULL {frente = p; // 1afinal = p; // 2a

}

else {final->sig = p; // 1bfinal = p; // 2b

}

p->sig = null; // 3}

INSERTAR(dato;frente;final) {Nuevo(p); p->info = dato;

if final = = NULL {frente = p; // 1afinal = p; // 2a

}

else {final->sig = p; // 1bfinal = p; // 2b

}

p->sig = null; // 3}

p

dato

final

frente

p

datonull

31a

2a

3

...

frente 1bnull

finalp

dato

2b

final


Colas

Algoritmo Eliminar(frente) {if frente = = NULL

cola vaca

else {p = frente; // 1frente = frente->sig; // 2free(p); // 3

}}

Algoritmo Eliminar(frente) {if frente = = NULL

cola vaca

else {p = frente; // 1frente = frente->sig; // 2free(p); // 3

}}

...

frente

1 null

finalfrente23

p

frente null



boolean EstaVaca (tCola **frente, tCola **final) {// Verificacin de cola vaca

if ((*final == NULL) && ( *frente == NULL))return( true); // Verdadero si est vaca

elsereturn (false);

}

boolean EstaVaca (tCola **frente, tCola **final) {// Verificacin de cola vaca

if ((*final == NULL) && ( *frente == NULL))return( true); // Verdadero si est vaca

elsereturn (false);

}



void Enqueue (tCola **frente ,tCola **final) { tElemento dato;printf("Ingrese elemento "); scanf("%d",&dato);if( *frente == NULL) {

*frente=(tCola *) malloc(sizeof(tCola));(*frente)->info = dato; // los parntesis son requeridos por(*frente)->sig = NULL; // precedencia de operandos *final = *frente;

}else {

tCola *q = (tCola *) malloc (sizeof (tCola) );q->info= dato;q->sig = NULL;*final = (*final)->sig = q;

}}

void Enqueue (tCola **frente ,tCola **final) { tElemento dato;printf("Ingrese elemento "); scanf("%d",&dato);if( *frente == NULL) {

*frente=(tCola *) malloc(sizeof(tCola));(*frente)->info = dato; // los parntesis son requeridos por(*frente)->sig = NULL; // precedencia de operandos *final = *frente;

}else {

tCola *q = (tCola *) malloc (sizeof (tCola) );q->info= dato;q->sig = NULL;*final = (*final)->sig = q;

}}


tElemento Dequeue (TCola **top, TCola **final) {tCola *temp;if (EstaVacia(frente,final))

printf("Error (cola vacia)");else {

tElemento x=(*frente)->info;temp = *frente;*frente = (*frente)-> sig;temp->sig=NULL;free(temp);return(x);

}}

tElemento Dequeue (TCola **top, TCola **final) {tCola *temp;if (EstaVacia(frente,final))

printf("Error (cola vacia)");else {

tElemento x=(*frente)->info;temp = *frente;*frente = (*frente)-> sig;temp->sig=NULL;free(temp);return(x);

}}



Ejemplo

a

a b

a b c

b c

No es necesario movertodos los elementos

a b

a b c

b c

Apuntadores al frentey al final

a


Colas - Ejercicios

Escribir una funcin que, dada una cola que almacena nmeros enteros, cuente la cantidad de mltiplos de 5 que contiene.Solucin:int Mul5EnCola(tCola**frente, tCola**final) {// Contar los nmeros mltiplos de 5 almacenados en la cola

int cont=0;tCola *aux =*frente;while (*aux!= NULL) {

int temp = Dequeue(aux, final);if(temp % 5 == 0)

cont++;}return(cont);

}

Escribir una funcin que, dada una cola que almacena nmeros enteros, cuente la cantidad de mltiplos de 5 que contiene.Solucin:int Mul5EnCola(tCola**frente, tCola**final) {// Contar los nmeros mltiplos de 5 almacenados en la cola

int cont=0;tCola *aux =*frente;while (*aux!= NULL) {

int temp = Dequeue(aux, final);if(temp % 5 == 0)

cont++;}return(cont);

}


#include #include #include struct tColas {

int info;struct TColas* sig;

};

typedef TColas tCola;

void Enqueue(tCola **frente, tCola **final);int Dequeue (tCola **frente, tCola **final);int Multiplos5EnCola(tCola **frente, tCola **final);int EstaVacia(tCola **final, tCola **frente);

#include #include #include struct tColas {

int info;struct TColas* sig;

};

typedef TColas tCola;

void Enqueue(tCola **frente, tCola **final);int Dequeue (tCola **frente, tCola **final);int Multiplos5EnCola(tCola **frente, tCola **final);int EstaVacia(tCola **final, tCola **frente);

Colas Ejercicios


void main() {int m5, i, max;tCola *final = NULL;tCola *frente = NULL;

// Ingresar datos a la colaprintf("Cuantos datos a ingresar? "); scanf("%d",&max);for(i=0;i < max; i++)

Enqueue(&frente,&final);// Buscar los mltiplos de 5m5= Multiplos5EnCola(&frente, &final);printf("\n\nNumeros multiplos de 5: %d",m5);getch();

}

void main() {int m5, i, max;tCola *final = NULL;tCola *frente = NULL;

// Ingresar datos a la colaprintf("Cuantos datos a ingresar? "); scanf("%d",&max);for(i=0;i < max; i++)

Enqueue(&frente,&final);// Buscar los mltiplos de 5m5= Multiplos5EnCola(&frente, &final);printf("\n\nNumeros multiplos de 5: %d",m5);getch();

}

Colas Ejercicios

Operaciones:

A

BA

A B C

B C

B C D

C D

1.1.-- Insertar AInsertar A

2.2.-- Insertar BInsertar B

Estado de la cola:

3.3.-- Insertar CInsertar C

4.4.-- Remover ElementoRemover Elemento

5.5.-- Insertar DInsertar D

6.- Remover Elemento

Inicio: Cola Vaca


Tipos de colas

Colas de prioridad Anillos BiColas BiColas circulares


Tipos de colas: Colas de Prioridad

Una cola de prioridad es una generalizacin de los conceptos de pila y cola en la que, tras entrar en la cola, la salida de los elementos no se basa necesariamente en el orden de llegada sino que se basa en un orden definido entre ellos.

Los elementos se atienden en el orden indicado por una prioridad asociada a cada uno.

Si varios elementos tienen la misma prioridad, se atendern de modo convencional segn la posicin que ocupen.



Los objetos se introducen de igual forma que en los casos anteriores;

La diferencia aparece en el caso de la extraccin y en la consulta del siguiente objeto a extraer. El elemento que se saca es el menor de los que se han

introducido segn la relacin de orden total. Si hay varios elementos menores, con el mismo valor, el que

se saca es aqul que se introdujo primero.



Existen dos formas de implementacin:1. Aadir un campo a cada nodo con su prioridad. Resulta

conveniente mantener la cola ordenada por orden de prioridad.

cp

dato2 pr2pr1dato1 ... daton prn

typedef struct {// Informacion// PrioridadCola *sgte;

} Cola_Prioridad;



2. Crear tantas colas como prioridades haya, y almacenar cada elemento en su cola.

I11 I12 I13P1

P2

P3

P4 I41 I42

I21

prim

ult

Frente Final


Algunas aplicaciones de las colas de prioridad

Gestin de procesos en un SO. Los procesos no se ejecutan uno tras otro en base a su orden de llegada. Algunos procesos deben tener prioridad (por su mayor importancia, por su menor duracin, etc.) sobre otros.

Implementacin de algoritmos voraces, proporcionan soluciones globales a problemas basndose en decisiones tomadas slo con informacin local. La determinacin de la mejor opcin local suele basarse en una cola de prioridad. Algunos algoritmos sobre grafos, como la obtencin de

caminos o rboles de expansin de costo mnimo, son ejemplos representativos.


Convertir una expresin aritmtica infija en postfija:Dada una expresin aritmtica E formada por nmeros y los operadores: +, -, *, / expresada en formato infijo, transformarla a formato postfijo.

Ejemplos del uso TDA Cola Prioridad


Cola Convertir( Cola Infija ) {Cola Post; Pila P; Elem token;

CrearPilaVacia( P );CrearColaVacia( Post );CrearElem( token );REPETIR

Asignar(token, Frente(Infija)),SacarDeCola( Infija );Si Operando( token )

PonerEnCola( token, Post );SinoSi (no PilaVacia(P)) && (Prioridad(token)


Anillos Cola circular

Las colas lineales tienen un grave problema: como las extracciones slo pueden realizarse por un

extremo, puede llegar un momento en que el apuntador A sea igual al mximo nmero de elementos en la cola, siendo que al frente de la misma existan lugares vacos, y al insertar un nuevo elemento nos mandar un error de overflow (cola llena).

Para solucionar el problema de desperdicio de memoria se implementaron las colas circulares, en las cuales existe un apuntador desde el ltimo elemento al primero de la cola.



Es una secuencia de elementos dispuestos de forma circular. Los elementos pueden aadirse y eliminarse desde un nico

punto llamado cabeza del anillo. El crculo de elementos se puede rotar en ambos sentidos, de

manera que los diferentes elementos van pasando por la cabeza del anillo.

Un anillo es, pues, una estructura en la que todo elemento tieneun sucesor y un predecesor, y hay una posicin distinguida llamada cabeza del anillo.



Estructuras con caractersticas parecidas se presentan a distintos niveles: redes de computadores con configuraciones de anillo y

comunicacin mediante paso de mensajes las interfaces de usuario, en los intrpretes de comandos,

que suelen utilizar un buffer de entrada estructurado como un anillo de lneas que se puede recorrer para recuperar lneas introducidas con anterioridad.


Implementacin en C Anillos

Declaracin:struct tcola {

int clave; struct tcola *sig;

};

Creacin:void crear(struct tcola **cola) {

*cola = NULL; }

Funcin que devuelve verdadero si la cola est vaca:int vacia(struct tcola *cola) {

return (cola == NULL); }



Poner_En_Cola:void encolar(struct tcola **cola, int elem) {

struct tcola *nuevo; nuevo = (struct tcola *) malloc(sizeof(struct tcola)); nuevo->clave = elem; if (*cola == NULL)

nuevo->sig = nuevo; else {

nuevo->sig = (*cola)->sig; (*cola)->sig = nuevo;

} (*cola) = nuevo;

}



Sacar_De_Cola:void desencolar(struct tcola **c1, int *elem) {

struct tcola *aux; *elem = (*c1)->sig->clave; if ((*c1) == (*c1)->sig) {

free(*c1); *c1 = NULL;

} else {

aux = (*c1)->sig; (*c1)->sig = aux->sig; free(aux);

} }



Programa de prueba:#include #include int main(void) {

struct tcola *cola; int elem; crear(&cola); if (vacia(cola))

printf("\nCola vacia!"); encolar(&cola, 100); desencolar(&cola, &elem); return 0;

}


Tipos de colas BiColas

Colas en donde los nodos se pueden insertar y eliminar por ambos extremos;

Se les llama DEQUE (Double Ended QUEue).


TAD BiCola

Las operaciones son las mismas que la del TAD Cola, salvo que Primero, Insertar y Eliminar son sustituidas por 2 operaciones respectivamente: PrimeroIzquierda: TipoDeque TipoElemento PrimeroDerecha: TipoDeque TipoElemento InsertarIzquierda: TipoElementox TipoDeque TipoDeque InsertarDerecha: TipoElemento x TipoDeque TipoDeque EliminarIzquierda: TipoDeque TipoDeque EliminarIzquierda: TipoDeque TipoDeque


Tipos de colas BiColas

Existen dos variantes:

Bicolas de entrada restringida: Son aquellas donde la insercin slo se hace por el final, aunque se puede eliminar al principio o al final.

Bicolas de salida restringida: Son aquellas donde slo se elimina por el final, aunque se puede insertar al principio y al final.


BiColas circulares

Permite la implementacin eficiente de todas las operaciones del anillo normal, y de la cola doble.

p puede apuntar ahora sin problemas a la cabeza del anillo, ya que se puede acceder sin problemas y de forma directa al ltimo elemento.


BiColas circulares

Las rotaciones tanto a derecha como a izquierda no suponen tampoco complicacin alguna, ya que se tienen punteros en ambas direcciones.


Bibliografa - Webgrafa

Abstraccin de datos1. http://www14.uniovi.es/tutorED/abstraccion/abstraccionfr.html

Estructura de Datos2. http://www14.uniovi.es/tutorED/estlineales/estlineafr.html3. http://www14.uniovi.es/tutorED/java-c++/java-c++fr.html4. Como programar en Java. Deitel y Deitel.

Listas 5. http://www14.uniovi.es/tutorED/estlineales/interlistafr.htm

6. http://oviedo3.ccu.uniovi.es/martin/EDI/ListPage.htm


Bibliografa - Webgrafa

Listas, pilas y colas. Ejercicios7. Fundamentos de programacin. Libro de problemas. Luis

Joyanes Aguilar8. http://old.algoritmia.net/listas.htm9. Estructura de datos y organizacin de archivos. Mary E.

Loomis. Prentice Hall. 2a Ed.10. Pilas y Colas. Cursos Propeduticos 2006, Programacin y

Estructuras de Datos. Manuel Montes, Claudia Feregrino.

ed cap4 pilascolas12010

Documents