Estructura de Datos
Pilas y Colas
Estudiantes:
Anjeli De Jesús Reyes Hernández
Didier Javier Bolaño Bolaño
Jesús David Parra Alonso
Valery Porto Niño
Ing. De Sistemas
16/04/2023
PILAS
TDA Pila (Stack)
Pila: Colección lineal de objetos actualizada en un extremo llamado tope
usando una política LIFO (last-in first-out, el primero en entrar es el último en
salir).
Operaciones:
• push(e): Inserta el elemento e en el tope de la pila.
• pop (): Elimina el elemento del tope de la pila y lo entrega como resultado.
Si se aplica a una pila vacía, produce una situación de error.
• isEmpty (): Retorna verdadero si la pila no contiene elementos y falso en
caso contrario.
• top (): Retorna el elemento del tope de la pila. Si se aplica a una pila vacía,
produce una situación de error.
• size (): Retorna un entero natural que indica cuántos elementos hay en la
pila.
Implementación de Pila
Definición de una interfaz Pila:
Se abstrae de la ED con la que se implementará.
Se documenta el significado de cada método en lenguaje natural.
Se usa un parámetro formal de “tipo” representando el tipo de los
elementos de la pila.
Se definen excepciones para las condiciones de error.
Diagrama UML del diseño
La flecha punteada se lee “implementa”. Daremos tres implementaciones de la
interfaz Stack<E> con tres clases:
PilaArreglo<E>
PilaEnlazada<E>
PilaConLista<E>
Interfaz Stack
En UML las operaciones se dan con una sintaxis Pascallike y las excepciones
se dan como comentarios:
Implementación de pila con arreglo
Código de Pilas:
COLAS
Cola: también llamada fila, es una estructura de datos caracterizada por ser
una secuencia de elementos en la que la operación de inserción se realiza por
un extremo y la operación de extracción por el otro. También se le conoce
como estructura FIFO (First In First Out), debido a que el primer elemento en
entrar será también el primero en salir.
La particularidad de una estructura de datos de tipo cola, es el hecho de que
sólo se puede acceder al primer y al último elemento de la estructura. Así
mismo, los elementos sólo se pueden eliminar por el principio y sólo se
pueden añadir por el final de la cola.
Operaciones:
• Crear: Se crea la cola vacía.
• Encolar (añadir, entrar, insertar): Se añade un elemento a la cola, el cual
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, el cual
es el primer elemento que entró.
Tipos de colas:
Colas circulares (anillos): Son aquellas en las que el último elemento y
el primero están unidos.
Colas de prioridad: En este tipo de cola los elementos se atienden en
el orden indicado por una prioridad asociada a cada uno. Si varios
elementos tienen la misma prioridad, se atenderán de modo
convencional según la posición que ocupen. Hay 2 formas de
implementación:
1. Añadir un campo a cada nodo con su prioridad. Es conveniente mantener la
cola ordenada por orden de prioridad.
2. Crear tantas colas como prioridades haya, y almacenar cada elemento en su
cola.
Bicolas: Son colas en las cuales los nodos se pueden añadir y quitar por
ambos extremos; se les llama DEQUE (Double Ended QUEue) por
dicha razón. Para representar las bicolas lo podemos hacer con un array
circular con inicio y fin que apunten a cada uno de los extremos. En este
tipo de cola hay unas variantes:
Bicolas de entrada restringida: Son aquellas donde la inserción sólo
se hace por el final, aunque es permitido eliminar al inicio ó al final.
Bicolas de salida restringida: Son aquellas donde sólo se elimina por
el final, aunque se puede insertar al inicio y al final.
Código de Colas:
REFERENCIAS BIBLIOGRAFICAS:
- ¿Qué son las colas en la estructura de datos? (s.f.).
[Link]
estructura-de-datos
- EcuRed. (s.f.). Cola(Estructura de datos).
[Link]
