Tema 4 y 5 - Colas y Pilas

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

TAD Colas

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).

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.

Operaciones

Siguiendo los pasos para la especificación de un TAD, definimos las operaciones del mismo clasificándolas en: constructoras, generadoras, modificadoras, observadoras y destructoras.

Generadoras

Objetivo: Crea una cola vacía
Salida: Una cola vacía
PosCondición: La cola sin datos
// SPDX-FileCopyrightText: 2023 Fernando Álvarez // // SPDX-License-Identifier: GPL-3.0-only void createEmptyQueue(tQueue *cola){ cola->front = QNULL; cola->rear = QNULL; }
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.
// SPDX-FileCopyrightText: 2023 Fernando Álvarez // // SPDX-License-Identifier: GPL-3.0-only bool enqueue(tItemQ item,tQueue *cola){ tPosQ aux; if(!createNode(&aux)){ return false; } else{ aux->data=item; aux->next=QNULL; if(cola->front == QNULL){ cola->front = aux; } else{ cola->rear->next = aux; } cola->rear = aux; return true; } }

Destructoras

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ía
// SPDX-FileCopyrightText: 2023 Fernando Álvarez // // SPDX-License-Identifier: GPL-3.0-only void dequeue(tQueue *cola){ tPosQ aux; aux = cola->front; cola->front = aux->next; if(cola->front == QNULL){ cola->rear = QNULL; } free(aux); }

Observadoras

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ía
// SPDX-FileCopyrightText: 2023 Fernando Álvarez // // SPDX-License-Identifier: GPL-3.0-only tItemQ front(tQueue cola){ return cola.front->data; }
Objetivo: Determina si la cola está vacía
Entrada: Queue: Cola a comprobar
Salida: Verdadero si la cola está vacía, falso en caso contrario
// SPDX-FileCopyrightText: 2023 Fernando Álvarez // // SPDX-License-Identifier: GPL-3.0-only bool isEmptyQueue(tQueue cola){ return(cola.front == QNULL); }

Implementación con array circular

Implementación con lista dinámica circular

Implementación a partir del TAD Lista

TAD Pilas

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).

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.