listas, colas y pilas misael 12-0518
Post on 06-Aug-2015
115 Views
Preview:
TRANSCRIPT
VIDEOS COLAS Y PILAS
http://www.youtube.com/watch?v=eeHhtDjvHdo
Listas
Es una secuencia de cero o más elementos de un mismo tipo.
< e1, e2, …, en > (Este es un ejemplo de una lista)
La longitud se define como la cantidad de los elementos que la component.
La posición de un elemento es el lugar que ocupa dentro de la secuencia de valores que componen la estructura.
Tipos de Lista
Lista densa: la misma lista determina el próximo elemento de la lista. Un ejemplo de este: Un Array.
Lista enlazada: el próximo elemento de la lista lo determina el elemento actual. Por ende, guardar la primera posición del primer elemento es primordial. Esto la hace bastante dinámica, debido a que su peso cambio en su tiempo de ejecución.
Cola
Las colas son una secuencia en la que sus elementos se caracterizan por tener 2 operaciones:
• Inserción PUSH. Que se realiza por un extremo llamado frente.
• Extracción POP. Que se realiza por un extremo llamado final.
Recorrido
Estas se recorren con lo que es llamado FIFO (First in – First Out). En el que el recorrido se hace sacando el primer dato que se insert hasta llegue hasta el final.
Funciones
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ó. Frente (consultar, front): se devuelve el elemento frontal de la cola, es decir, el primer
elemento que entró.
Usos: En las impresoras se usa este metodo, en los procesos del computador.
Bicolas
Son colas en donde los nodos se pueden añadir y quitar por ambos extremos; se les llama DEQUE (Double Ended QUEue).
Hay variantes:
• Bicolas de entrada restringida: Son aquellas donde la inserción sólo se hace por el final, aunque podemos eliminar al principio ó al final.
• Bicolas de salida restringida: Son aquellas donde sólo se elimina por el final, aunque se puede insertar al principio y al final.
Cola de prioridad
Son aquellas que cumplen dos reglas :
1. De dos elementos siempre se atenderá antes al que tenga mayor prioridad. 2. Si dos elementos tienen la misma prioridad se atiende primero el que llego antes.
Realización Se ponen todos los nodos en la misma cola. Su particularidad es que cada nodo tiene un campo adicional con la prioridad del dato; de tal forma que cuando insertamos nuevos datos, el nuevo nodo, se inserta al final de la cola de los que tengan su misma prioridad.
Pila
Las pilas son una secuencia en la que permite almacenar y recuperar datos. Se caracterizan por tener 2 operaciones:
1. Inserción PUSH. Que se realiza por un extremo llamado frente.
2. Extracción POP. Que se realiza por un extremo llamado final.
Recorrido
Estas se recorren con lo que es llamado LIFO (Last In First Out). En la que el ultimo dato en llegar es el primero en salir.
Funciones
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). Llena: devuelve cierto si la pila está llena o falso en caso contrario (full).
Usos:
-Evaluación de expresiones en notación postfija (notación polaca inversa).
-Reconocedores sintácticos de lenguajes independientes del contexto
-Implementación de recursividad.
top related