Tema 4 y 5 - Colas y Pilas
El TAD Cola y el TAD Pila, especificación informal, implementación y descripción gráfica. Diferencias entre ambos explicadas. Implementaciones con array circular, lista dinámica circular y a partir del TAD Lista. Operaciones explicadas de forma gráfica.
Visita nuestra nueva página web con contenidos actualizados y mucho más.
Estos apuntes también están en: Pásame el Código
tip
Copyright © 2024 Pablo Portas López
note
Para ver las diferencias entre los dos TADs: TAD Cola vs TAD Pila
Una cola es una secuencia de cero o más elementos del mismo tipo. Los elementos de una cola están ordenados de una forma lineal, no por su contenido, sino por la posición que ocupan.
Cuando un elemento es insertado se añade al principio de la cola. Para eliminar o extraer un elemento, solo se podrá eliminar el primero, que fue el primero en ser insertado. Este concepto es descrito como FIFO (First in, first out).
note
Para saber más sobre FIFO. Wikipedia
El primero en llegar a una cola, es el primero en salir de la cola, ya que está al principio (front) de la cola.
El último en llegar, por otra parte, debe preguntar: ¿Dónde está el final de la cola? Y esperar pacientemente, ya que será el último en salir de la cola.
Siguiendo los pasos para la especificación de un TAD, definimos las operaciones del mismo clasificándolas en: constructoras, generadoras, modificadoras, observadoras y destructoras.
note
Para más información: Especificación de un TAD
Objetivo: Crea una cola vacía
Salida: Una cola vacía
PosCondición: La cola sin datosMostrar implementación{...}Objetivo: Inserta un elemento en la cola quedando al final.
Entrada:
- Item: Contenido del elemento a insertar.
- Queue: Cola donde vamos a insertar.
Salida: Queue: Cola con el elemento Item insertado y verdadero si se ha podido insertar, falso en caso contrario.Mostrar implementación{...}
Objetivo: Elimina el primer elemento de la cola
Entrada: Queue: Cola a modificar
Salida: Queue: Cola sin el primer elemento
Precondición: La cola no está vacíaMostrar implementación{...}
Objetivo: Recupera el contenido del primer elemento de la cola
Entrada: Queue: Cola donde obtener el dato
Salida: Item: Contenido del primer elemento de la cola
Precondición: La cola no está vacíaMostrar implementación{...}Objetivo: Determina si la cola está vacía
Entrada: Queue: Cola a comprobar
Salida: Verdadero si la cola está vacía, falso en caso contrarioMostrar implementación{...}
note
Esta implementación se basa en el Tema 3 - Listas.
Una pila es una secuencia de cero o más elementos del mismo tipo. Los elementos de una cola están ordenados de una forma lineal, no por su contenido, sino por la posición que ocupan.
Cuando un elemento es insertado se añade al principio de la pila. Para extraer o eliminar un elemento solo se puede el primer elemento, que fue último en añadirse. Este concepto es descrito como LIFO (Last in, first out).
note
Para saber más sobre LIFO. Wikipedia
Cuando agregas libros a una pila, el primer libro queda aplastado bajo el peso de todos los demás. Al fondo de la pila.
El último libro es el de la cima (peek) y es el que primero puedes retirar.
Para poder retirar el libro que primero se depositó en la pila debes retirar todos antes.
Siguiendo los pasos para la especificación de un TAD, definimos las operaciones del mismo clasificándolas en: constructoras, generadoras, modificadoras, observadoras y destructoras.
note
Para más información: Especificación de un TAD
Objetivo: Crea una pila vacía
Salida: Una pila vacía
PosCondición: La pila sin datosMostrar implementación{...}Objetivo: Inserta un elemento en la cola quedando al final.
Entrada:
- Item: Contenido del elemento a insertar.
- Queue: Cola donde vamos a insertar.
Salida: Stack: Cola con el elemento Item insertado y verdadero si se ha podido insertar, falso en caso contrario.Mostrar implementación{...}
Objetivo: Saca el elemento de la cima de la pila
Entrada: Stack: Pila de donde vamos a sacar
Salida: Stack: Pila sin el elemento de su cima
Precondición: La pila no está vacíaMostrar implementación{...}
Objetivo: Recupera el contenido del elemento de la cima de la pila
Entrada: Stack: Pila donde obtener el datoo
Salida: Item: Contenido del elemento de la cima de la pila
Precondición: La pila no está vacíaMostrar implementación{...}Objetivo: Determina si una pila está vacía
Entrada: Stack: Pila a comprobar
Salida: Verdadero si la pila está vacía, falso en caso contrarioMostrar implementación{...}
El TAD Cola y el TAD Pila son muy similares, por eso en estos apuntes han sido unificados en un solo tema.
TAD Cola (Quede) | TAD Pila (Stack) |
|---|---|
El primero en entrar, el primero en salir (FIFO) | El último en entrar, el primero en salir (LIFO) |
|
|
|
|
|
|
|
|