Pro2324 Help

Tema 4 y 5 - Colas y Pilas

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

TAD Cola
MEMORIA
NODO 1
NODO 2
NODO 3
ENTRADA
SALIDA
Este es el frente de la cola
Este es el final de la cola
TAD Cola

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.

Colas.png

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

TAD Pila
MEMORIA
NODO 3
NODO 2
NODO 1
ENTRADA
SALIDA
TAD Pila

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.

Pila.jpg

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 pila vacía
    Salida: Una pila vacía
    PosCondición: La pila sin datos

    // EN CONSTRUCCIÓN // COLABORA https://github.com/TeenBiscuits/Pro2324

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

    // EN CONSTRUCCIÓN // COLABORA https://github.com/TeenBiscuits/Pro2324

Destructoras


  • 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ía

    // EN CONSTRUCCIÓN // COLABORA https://github.com/TeenBiscuits/Pro2324

Observadoras


  • 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ía

    // EN CONSTRUCCIÓN // COLABORA https://github.com/TeenBiscuits/Pro2324

  • Objetivo: Determina si una pila está vacía
    Entrada: Stack: Pila a comprobar
    Salida: Verdadero si la pila está vacía, falso en caso contrario

    // EN CONSTRUCCIÓN // COLABORA https://github.com/TeenBiscuits/Pro2324

TAD Cola vs TAD Pila

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)

createEmptyQueue()

createEmptyStack()

isEmptyQueue(Quede)

isEmptyStack(Stack)

enquede(Item, Quede) y dequede(Quede): Añadir y Eliminar un elemento a la cola

push(Item, Stack) y pop(Stack): Añadir y Eliminar un elemento a la pila

front(Quede): Devuelve el elemento n de la cola (el primero en entrar).

peek(Stack): Devuelve el elemento 0 de la pila (el último en entrar).

TAD Cola
MEMORIA
NODO 1
NODO 2
NODO 3
ENTRADA
SALIDA
TAD Cola
TAD Pila
MEMORIA
NODO 3
NODO 2
NODO 1
ENTRADA
SALIDA
TAD Pila
Last modified: 18 July 2024