OIA-Wiki

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
====== Deque ======

  * **Conocimientos mínimos**: [[curso-cpp:contenedor-vector|Vector]]


===== Motivación =====

''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 ((O incluso matrices, mediante listas de listas.)).

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)$ [[algoritmos-oia:analisis-amortizado|amortizado]]).

===== Ejemplo =====

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:

<code>
7
1 2 3 4 5 6 7
</code> 

Queremos generar en la salida:

<code>
6 4 2 1 3 5 7
</code>

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.

<code cpp>
#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;
}
</code>
OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Herramientas de la página
