• Conocimientos mínimos: Vector

vector, que se utiliza en C++ para representar arreglos de tamaño dinámico, es una de las estructuras más comunes y utilizadas para guardar listas de valores ¹⁾.

Además de la indexación (con corchetes, como en v[5]) vector tiene muchas operaciones de utilidad, como por ejemplo .front(), .back(), .push_back() y .pop_back(). Sin embargo, a vector le faltan un par de operaciones interesantes, que son .push_front() y .pop_front(). Como su nombre sugiere, estas operaciones se comportan de manera análoga a las clásicas push_back y pop_back, pero insertan o eliminan un elemento por el comienzo del deque (es decir, la posición $0$) en lugar de por el final (posición $N-1$).

Deque es una estructura más poderosa que vector: permite todas las operaciones que vector permite (incluso la indexación con corchetes), y además permite usar .push_front() y .pop_front(), que son eficientes (su complejidad temporal es $O(1)$ amortizado).

Supongamos que leemos un $N$, y una lista de $N$ elementos de la entrada, y tenemos que escribirla en la salida pero “mezclada”, de manera tal que el primer elemento queda “en el medio” de la lista, y los siguientes se van poniendo, alternadamente, uno a la izquierda y uno a la derecha. Por ejemplo si se ingresa:

7
1 2 3 4 5 6 7

Queremos generar en la salida:

6 4 2 1 3 5 7

Es fácil dar un programa que haga esto aprovechando las capacidades de deque, que nos permiten justamente realizar estas dos operaciones: agregar a izquierda, y agregar a derecha.

#include <iostream>
#include <deque>
 
using namespace std;
 
int main()
{
    int N; cin >> N;
    deque<int> resultado;
    for (int i=0;i<N;i++)
    {
        int x; cin >> x;
        if (i%2 == 0)
            resultado.push_back(x);
        else
            resultado.push_front(x);        
    }
    for (int i=0;i<N;i++)
    {
        if (i>0) cout << " ";
        cout << resultado[i];
    }
    cout << endl;
    return 0;
}