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.

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

---
title: TAD Cola
---
flowchart LR
    subgraph MEMORIA
        NODO1[NODO 1]
        NODO2[NODO 2]
        NODO3[NODO 3]
    end
    ENTRADA --> NODO3 --> NODO2 --> NODO1 --> SALIDA
    FRENTE([Este es el frente de la cola]) -.-> NODO1
    FINAL([Este es el final de la cola]) -.-> NODO3

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

createEmptyQueue → Queue

createEmptyQueue \rightarrow Queue

Objetivo: Crea una cola vacía
Salida: Una cola vacía
PosCondición: La cola sin datos

Mostrar implementación

// SPDX-FileCopyrightText: 2023 Fernando Álvarez
//
// SPDX-License-Identifier: GPL-3.0-only

void createEmptyQueue(tQueue *cola){

    cola->front = QNULL;
    cola->rear = QNULL;

}

enqueue(Item, Queue) → Queue, bool

enqueue (Item, Queue) \rightarrow Queue, bool

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

// 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

dequeue(Queue) → Queue

dequeue(Queue) \rightarrow Queue

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

Mostrar implementación

// 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

front(Queue) → Item

front(Queue) \rightarrow Item

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

Mostrar implementación

// SPDX-FileCopyrightText: 2023 Fernando Álvarez
//
// SPDX-License-Identifier: GPL-3.0-only

tItemQ front(tQueue cola){

    return cola.front->data;
}

isEmptyQueue(Queue) → bool

isEmptyQueue(Queue) \rightarrow bool

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

Mostrar implementación

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

---
title: TAD Pila
---
flowchart LR
    subgraph MEMORIA
        NODO1[NODO 3]
        NODO2[NODO 2]
        NODO3[NODO 1]
    end
    ENTRADA & SALIDA --> NODO1 --> NODO2 --> NODO3

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.

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

createEmptyStack → Stack

createEmptyStack \rightarrow Stack

Objetivo: Crea una pila vacía
Salida: Una pila vacía
PosCondición: La pila sin datos

Mostrar implementación

// EN CONSTRUCCIÓN
// COLABORA https://github.com/TeenBiscuits/Pasame-Codigo

push(Item, Stack) → Stack, bool

push (Item, Stack) \rightarrow Stack, bool

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

// EN CONSTRUCCIÓN
// COLABORA https://github.com/TeenBiscuits/Pasame-Codigo

Destructoras

pop(Stack) → Stack

pop(Stack) \rightarrow Stack

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

Mostrar implementación

// EN CONSTRUCCIÓN
// COLABORA https://github.com/TeenBiscuits/Pasame-Codigo

Observadoras

peek(Stack) → Item

peek(Stack) \rightarrow Item

Objetivo: Recupera el contenido del elemento de la cima de la pila
Entrada: Stack: Pila donde obtener el dato
Salida: Item: Contenido del elemento de la cima de la pila
Precondición: La pila no está vacía

Mostrar implementación

// EN CONSTRUCCIÓN
// COLABORA https://github.com/TeenBiscuits/Pasame-Codigo

isEmptyStack(Stack) → bool

isEmptyStack(Stack) \rightarrow bool

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

Mostrar implementación

// EN CONSTRUCCIÓN
// COLABORA https://github.com/TeenBiscuits/Pasame-Codigo

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 (Queue)	TAD Pila (Stack)
El primero en entrar, el primero en salir (FIFO)	El último en entrar, el primero en salir (LIFO)
`createEmptyQueue()`	`createEmptyStack()`
`isEmptyQueue(Queue)`	`isEmptyStack(Stack)`
`enqueue(Item, Queue)` y `dequeue(Queue)`: 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(Queue)`: Devuelve el elemento `n` de la cola (el primero en entrar).	`peek(Stack)`: Devuelve el elemento `0` de la pila (el último en entrar).

---
title: TAD Cola
---
flowchart TB
    subgraph MEMORIA
        NODO1[NODO 1]
        NODO2[NODO 2]
        NODO3[NODO 3]
    end
    ENTRADA --> NODO3 --> NODO2 --> NODO1 --> SALIDA

---
title: TAD Pila
---
flowchart TB
    subgraph MEMORIA
        NODO1[NODO 3]
        NODO2[NODO 2]
        NODO3[NODO 1]
    end
    ENTRADA & SALIDA --> NODO1 --> NODO2 --> NODO3