C++ Pilas (stacks) y colas (queues)

Enviado por bhuergo el Mar, 04/10/2022 - 16:55

Requisitos:

Unos conocimientos más o menos equivalentes a los entrenamientos de iniciación

Este es el primer artículo de cuatro que forman el manual del primer entrenamiento intermedio de la OIE: Estructuras de datos de la STL. La STL es la colección principal de clases y funciones que usamos en nuestros programas en C++. Una de sus grandes utilidades de cara a la programación competitiva son una serie de estructuras de datos que estudiaremos hoy, que nos facilitarán este tipo de problemas, ya que nos ahorran el tener que programarlas desde cero.

En el artículo de hoy veremos dos estructuras de datos que tiene C++: pilas (stacks) y colas (queues). Ambas estructuras son lineales, es decir, guardan los datos en una fila en lugar de, por ejemplo, en un árbol o grafo.

Colas

Las colas se caracterizan por ser estructuras first-in-first-out (FIFO). Esto significa que funcionan como una cola de personas en una panadería: la primera persona en llegar a la panadería será la primera en ser atendida y así sucesivamente hasta vaciar la cola.

Para usar colas en C++, habrá que importar el módulo <queue> a nuestro programa. Para crear una cola, como cualquier otro objeto en C++, será necesario darle nombre. Siempre que creemos una cola estaremos creando una cola vacía. Podemos hacerlo de la siguiente manera:

queue<int> cola;

En este ejemplo, la cola únicamente podrá guardar valores de tipo int. Las colas podrán guardar objetos de una única clase, ya sea una creada por el usuario o una estándar, como en este ejemplo.

Las colas tienen una serie de operaciones que se pueden realizar con ellas:

Insertar elementos: para insertar un elemento al final de la cola, podemos usar la función push().
Eliminar elementos: para quitar el elemento del principio de la cola, podemos usar la función pop().
Ver cuál es el primer elemento de la cola: para ver cuál es este elemento, podemos usar la función front(). Esto es muy útil, ya que pop() únicamente quitará el primer elemento de la cola, pero no nos dirá cuál es. Esta es una diferencia fundamental entre C++ y otros lenguajes, así que los que vengáis de otros lenguajes tenéis que acordaros de esto, que tiende a ser un bug muy común.
Ver cuál es el último elemento de la cola: hay un equivalente de la función front() para el final de la cola, la función back().
Ver cuántos elementos tiene la cola: para saber esto, podemos utilizar la función size(). Además, podremos saber si la cola está vacía con la función empty().

Todas estas operaciones tienen complejidad O(1), es decir, que el ordenador tardará lo mismo en realizarlas con independencia de cómo de larga sea la cola en el momento de la operación.

Para asegurarte de que lo has entendido bien, trata de predecir la salida del próximo fragmento de código antes de ejecutarlo en tu ordenador y comprobar así tu respuesta:

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> cola;
    cola.push(1);
    cola.push(2);
    cout << cola.size() << '\n';
    cola.pop();
    cout << cola.size() << '\n';
    cola.push(1);
    cola.push(3);
    cout << cola.front() << '\n';
    cola.pop();
    cola.pop();
    if (cola.empty()) cout << "La cola no tiene elementos\n";
    else cout << "La cola tiene elementos\n";
    return 0;
}

Problema para reforzar tus conocimientos: ¿Quién empieza? (Acepta el reto)

Problema reto: Team Queue (Online Judge)

Sección de ampliación: deques

(Las secciones de ampliación son temas que pueden resultaros útiles pero que no están estrictamente dentro del temario de la semana, por lo que las podéis saltar y el manual se entenderá igual.)

Además, C++ tiene unas colas especiales llamadas deque, que son la abreviación de double-ended queue, es decir, cola con dos finales. Las deques tienen las mismas operaciones que las colas, con el extra de que podemos añadir y quitar elementos desde ambos extremos de la fila. Para añadir al principio usaremos push_front(), para añadir al final usaremos push_back(), para quitar del principio haremos pop_front() y para quitar del final haremos pop_back(). Más información aquí.

Problema reto: Sliding Window Maximum (LeetCode)

Pilas

Las pilas se caracterizan por ser estructuras last-in-first-out (LIFO). Esto significa que funcionan como un montón de cartas donde no solo levantarás siempre la carta que está arriba del todo del montón, pero también colocarás siempre las cartas arriba del todo del montón.

Para usar pilas en C++, habrá que importar el módulo <stack> a nuestro programa. Para crear una pila, como cualquier otro objeto en C++, será necesario darle nombre. Siempre que creemos una pila estaremos creando una pila vacía. Podemos hacerlo de la siguiente manera:

stack<int> pila;

En este ejemplo, la pila únicamente podrá guardar valores de tipo int. Las pilas podrán guardar objetos de una única clase, ya sea una creada por el usuario o una estándar, como en este ejemplo.

Las pilas tienen una serie de operaciones que se pueden realizar con ellas:

Insertar elementos: para insertar un elemento en la parte de arriba de la pila, podemos usar la función push().
Eliminar elementos: para quitar el elemento de arriba del todo de la pila, podemos usar la función pop().
Ver cuál es el elemento de arriba del todo de la pila: para ver cuál es este elemento, podemos usar la función top(). Esto es muy útil, ya que pop() únicamente quitará el primer elemento de la pila, pero no nos dirá cuál es. Esta es una diferencia fundamental entre C++ y otros lenguajes, así que los que vengáis de otros lenguajes tenéis que acordaros de esto, que tiende a ser un bug muy común.
Ver cuántos elementos tiene la pila: para saber esto, podemos utilizar la función size(). Además, podremos saber si la pila está vacía con la función empty().

Todas estas operaciones tienen complejidad O(1), es decir, que el ordenador tardará lo mismo en realizarlas con independencia de cómo de larga sea la pila en el momento de la operación.

Para asegurarte de que lo has entendido bien, trata de predecir la salida del próximo fragmento de código antes de ejecutarlo en tu ordenador y comprobar así tu respuesta:

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> pila;
    pila.push(1);
    pila.push(2);
    cout << pila.size() << '\n';
    pila.pop();
    cout << pila.size() << '\n';
    pila.push(1);
    pila.push(3);
    cout << pila.top() << '\n';
    pila.pop();
    pila.pop();
    if (pila.empty()) cout << "La pila no tiene elementos\n";
    else cout << "La pila tiene elementos\n";
    return 0;
}

Problema para reforzar tus conocimientos: Paréntesis balanceados (Acepta el reto)

Problema reto: Remove Duplicate Letters (LeetCode)

Sección de ampliación: monotonic stack

Una de las aplicaciones más útiles de las pilas es la técnica conocida como monotonic stack. Esta consiste en, dada una lista de elementos A de longitud n, usar un stack de forma que en O(n) hayamos encontrado, para cada posición de la lista, cuál es la primera posición a su izquierda con un valor mayor. Es decir, para cada posición i, encontrar la mayor posición j tal que j < i y A[j] > A[i] (si existe tal posición). Encontraremos este problema en muchas variaciones: encontrar la primera posición a la derecha, encontrar la primera con un valor menor, etc.

La técnica se resume con el siguiente código, que ahora veremos en algo de detalle. Para los concursos os sirve con aprender el código tal cual, pero la intuición que incluimos debajo nunca sobra.

vector<int> calcularPosiciones(vector<int> & A) {
    stack<int> pila;
    vector<int> posicionesBuscadas(A.size());
    posicionesBuscadas[0] = -1; // -1 = no hay posición que cumpla la condición
    pila.push(0);
    for (size_t i = 1; i < A.size(); i++) {
        while(!pila.empty() && A[pila.top()] <= A[i]) {
            pila.pop();
        }
        if (pila.empty()) posicionesBuscadas[i] = -1;
        else posicionesBuscadas[i] = pila.top();
        pila.push(i);
    }
    return posicionesBuscadas;
}

Para resolver este problema, crearemos una pila en la que guardaremos índices de nuestra lista A. Trataremos en todo momento de mantener la propiedad (*) de que en nuestra pila, si un elemento i está encima de otro elemento j, j < i y A[j] > A[i]. Inicialmente, añadiremos a la cola el índice 0, e iteraremos sobre los índices i = 1, 2, ..., n-1. Nuestro objetivo será que al terminar de iterar sobre un índice i, el elemento de arriba del todo del stack sea i, seguido de posicionesBuscadas[i], seguido de posicionesBuscadas[posicionesBuscadas[i]], y así hasta llegar al final de la pila.

La lógica a seguir es que si al iterar sobre el índice i+1 nos encontramos con que A[i] <= A[i+1] y, por lo tanto, no nos sirve el índice anterior como la posición buscada, tendremos que encontrar un índice a la izquierda de i cuyo valor supere A[i]. El primer índice con esta característica será posicionesBuscadas[i] (si no es -1), y así podemos razonar sucesivamente. Ahora ya sabemos cómo encontrar la posición buscada para el índice i+1. ¿Cómo mantenemos la propiedad (*) de la pila? Pues cada vez que bajando por la pila nos encontremos un índice j < i+1 tal que A[j] <= A[i+1] lo borraremos, ya que en ningún momento volverá a ser la posición buscada de un índice futuro. Tras hacer esto, añadiremos a la pila el índice i+1. Al seguir estos pasos, nos aseguramos también de que el elemento anterior en la pila a i+1 (si hay, si no hay sabremos que es el mayor hasta el momento) sea la posición buscada del índice i+1 y, como la propiedad (*) se cumplía en la iteración sobre el índice i, se mantendrá ahora.

Problemas reto: Advertisement (CSES) y Fancy Fence (CEOI 2020)

Este es el primer artículo del manual del entrenamiento intermedio sobre Estructuras de datos de la STL. El siguiente a leer de esta unidad es C++ Mapas (maps) y conjuntos (sets) desordenados.

Añadir nuevo comentario

Texto sin formato