Diseñe la cola delantera media trasera usando STL

Diseñe una estructura de datos que admita las siguientes operaciones en cola de manera eficiente:

• push__front(x): inserta un elemento al principio de la cola.
• push__middle(x): Inserta el elemento en el medio de la cola.
• push__back(x): Inserta el elemento al final de la cola.
• pop__front() Elimina el elemento frontal de la cola y lo devuelve. Si la cola está vacía, devuelve -1.
• pop__middle(): elimina el elemento central de la cola y lo devuelve. Si la cola está vacía, devuelve -1.
• pop__back(): elimina el elemento posterior de la cola y lo devuelve. Si la cola está vacía, devuelve -1.

Ejemplos:

Enfoque basado en Deque : El problema se puede resolver usando dos deque . La idea es usar dos deques. La operación al final de la cola se debe realizar al final del segundo deque, y la operación en el medio se debe realizar al final del primer deque. Siga los pasos a continuación para resolver el problema:

• Si el tamaño del primer deque es mayor que el tamaño del segundo deque, quite el elemento final del primer deque y agréguelo al frente del segundo deque.
• Si el tamaño del segundo deque excede el tamaño del primer deque en 1, retire el elemento frontal del segundo deque y empújelo al final del primer deque.
• Si el tamaño del primer deque es mayor que el del segundo deque, retire el elemento posterior del primer deque e insértelo en el segundo deque.
• push__front(x): Inserta un elemento x al frente de la primera deque usando push_front() .
• push__back(x): inserta un elemento x al final de la segunda deque usando push_back()
• push__middle(x): inserta el elemento x al final de la primera deque usando push_back().
• pop__front(): elimine el elemento frontal de la primera deque si el tamaño de la deque es mayor que 0 usando pop_front().
• pop__back(): elimine el elemento final de la segunda deque si el tamaño de deque es mayor que 0 usando pop_back().
• pop__middle(): elimine el elemento final de la primera deque si el tamaño de deque es mayor que el uso de pop_back().

A continuación se muestra la implementación del enfoque anterior:

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Create class Queue.
class Queue {
 
    // Initialize two deques
    deque<int> first, second;
 
    // Function to balance the size of
    // first ans second deque
    void equalizeSizedeque1deque2()
    {
 
        // If size of less than second
        if (first.size() <= second.size())
            return;
 
        // Insert the last element of
        // first deque into second deque
        second.push_front(first.back());
 
        // Pop the front element
        // of the deque
        first.pop_back();
    }
 
    // Function to balance the size of
    // second and first deque
    void equalizeSizedeque2deque1()
    {
 
        // if size of second deque deceed
        // the first deque by 1
        if (second.size() <= first.size() + 1)
            return;
 
        // Insert front element of second
        // deque into the first
        first.push_back(second.front());
 
        // Remove front element of
        // second deque
        second.pop_front();
    }
 
public:
    // Function to insert element
    // at front of queue
    void push__front(int val)
    {
 
        // Insert val into first deque
        first.push_front(val);
 
        // Balancing the size of second
        equalizeSizedeque1deque2();
    }
 
    // Function to insert val
    // into the middle of queue
    void push__middle(int val)
    {
 
        // Insert val into first deque
        first.push_back(val);
 
        // Balancing the size of
        // second deque
        equalizeSizedeque1deque2();
    }
 
    // Function to insert val
    // into back of queue
    void push__back(int val)
    {
 
        // Insert val into second deque
        second.push_back(val);
 
        // Balancing the size of
        // second deque
        equalizeSizedeque2deque1();
    }
 
    // Function to pop front
    // element from queue
    int pop__front()
    {
 
        // If first deque and second
        // deque is empty
        if (first.empty() && second.empty())
            return -1;
 
        int ans;
 
        // If the first deque
        // is empty
        if (first.empty()) {
 
            // Stores front element
            // of second deque
            ans = second.front();
 
            // Pop front element of
            // second deque
            second.pop_front();
        }
        else {
 
            // Stores front element
            // of first deque
            ans = first.front();
 
            // Pop front element of
            // first deque
            first.pop_front();
 
            // Balancing the size of first
            equalizeSizedeque2deque1();
        }
        return ans;
    }
 
    // Function to pop middle
    // element of queue
    int pop__middle()
    {
 
        // If both deques are empty
        if (first.empty() && second.empty())
            return -1;
 
        // Stores mid element
        // of queue
        int ans;
 
        // If size of both deque is equal
        if (first.size() == second.size()) {
 
            // Stores back element
            // of first deque
            ans = first.back();
 
            // Pop back element of
            // first deque
            first.pop_back();
        }
        else {
 
            // Stores front element
            // of second deque
            ans = second.front();
 
            // Pop front element
            // from second deque
            second.pop_front();
        }
        return ans;
    }
 
    // Function to remove mid
    // element from queue
    int pop__back()
    {
 
        // If both the deque are empty
        if (first.empty() && second.empty())
            return -1;
 
        // Stores back element from
        // second deque
        int ans = second.back();
 
        // Pop back element from
        // second deque
        second.pop_back();
 
        // Balancing the size of second
        equalizeSizedeque1deque2();
        return ans;
    }
};
 
// Driver code
int main()
{
    Queue q;
    q.push__front(1);
    q.push__back(2);
    q.push__middle(3);
    cout << q.pop__middle() << " ";
    cout << q.pop__back() << " ";
    cout << q.pop__front() << " ";
    return 0;
}

3 2 1

Análisis de la Complejidad del Tiempo:

Enfoque basado en listas: siga los pasos a continuación para resolver el problema:

• push__front(x): inserta un elemento x al principio de la lista usando push_front() .
• push__back(x): inserta un elemento x al final de la segunda lista usando push_back()
• push__middle(x): recorre la lista usando advance() y luego inserta el elemento en la posición media de la lista usando insert()
• pop__front(): elimine el elemento frontal de la lista si el tamaño de la lista es mayor que 0 usando pop_front() , de lo contrario, devuelva -1 .
• pop__back(): elimine el último elemento de la lista si el tamaño de la lista es mayor que 0 usando pop_back(), de lo contrario, devuelva -1 .
• pop__middle(): si el tamaño de la lista es mayor que 0 , itere hasta el elemento central de la lista usando advance() y luego borre el elemento en esa posición usando erase(). De lo contrario, devuelve -1 .

A continuación se muestra la implementación del enfoque anterior:

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Create structure of queue
class Queue {
 
    list<int> l;
 
public:
    // Function to push element
    // at front of the queue
    void push__front(int val)
    {
        l.push_front(val);
    }
 
    // Function to push element
    // at middle of the queue
    void push__middle(int val)
    {
 
        auto itr = l.begin();
 
        // Traverse the list
        advance(itr, l.size() / 2);
 
        // Insert element into
        // middle of the list
        l.insert(itr, val);
    }
 
    // Function to insert element
    // at the back of the queue
    void push__back(int val)
    {
        l.push_back(val);
    }
 
    // Function to pop element from
    // front of the queue
    int pop__front()
    {
 
        // Stores front element
        // of queue
        int val = -1;
        if (l.size()) {
            val = l.front();
            l.pop_front();
        }
        return val;
    }
 
    // Function to pop middle element
    // of the queue
    int pop__middle()
    {
        int val = -1;
        if (l.size()) {
            auto itr = l.begin();
 
            // Traverse the list
            advance(itr, (l.size() - 1) / 2);
            val = *itr;
 
            // Remove mid element
            // from queue
            l.erase(itr);
        }
        return val;
    }
 
    // Function to pop end
    // element of the queue
    int pop__back()
    {
 
        // Stores back element
        // of the queue
        int val = -1;
 
        if (l.size()) {
            val = l.back();
            l.pop_back();
        }
        return val;
    }
};
 
// Drivers code
int main()
{
    Queue q;
    q.push__front(1);
    q.push__back(2);
    q.push__middle(3);
    cout << q.pop__middle() << " ";
    cout << q.pop__back() << " ";
    cout << q.pop__front() << " ";
    return 0;
}

3 2 1 

Análisis de la Complejidad del Tiempo:

Enfoque basado en listas doblemente enlazadas : el problema también se puede resolver usando una lista doblemente enlazada sin usar STL almacenando la dirección del encabezado y el último Node. Siga los pasos a continuación para resolver el problema:

• empujar__frente(x):
  • Asigne espacio para almacenar el valor de datos x y almacene la dirección en el puntero de Node actual
  • Inserte el elemento x vinculando el Node actual entre el Node principal y el Node principal- >siguiente
  • Incrementa la capacidad en uno
• retroceder__(x): 
  • Asigne espacio para almacenar el valor de datos x y almacene la dirección en el puntero de Node actual
  • Inserte el elemento x vinculando el Node actual entre el último Node y el último-> Node anterior
  • Incrementa la capacidad en uno
• empujar__medio(x): 
  • Asigne espacio para almacenar el valor de datos x y almacene la dirección en el puntero de Node actual
  • Inicializar un puntero temporal de tipo Node
  • Llegue al elemento medio de la lista doblemente enlazada haciendo temp=temp->siguiente mitad de los tiempos de capacidad actual
  • Ahora inserte el elemento x entre temp y temp->siguiente al volver a vincular los Nodes
  • Incrementa la capacidad en uno
• pop__frente() 
  • Si la capacidad del tamaño es menor que 1, devuelve -1
  • De lo contrario, elimine el primer Node entre el encabezado y el encabezado- >siguientes Nodes volviendo a vincular los Nodes
  • Disminuir la capacidad en uno
  • Valor de retorno del elemento eliminado
• retroceder____(): 
  • Si la capacidad es menor que 1 , devuelve -1
  • De lo contrario, elimine el Node final entre el último y el último-> Nodes anteriores volviendo a vincular los Nodes
  • Disminuir la capacidad en uno
  • Valor de retorno del elemento eliminado
• pop__medio(): 
  • Inicializar un puntero temporal de tipo Node
  • Llegue al elemento medio de la lista doblemente enlazada haciendo temp=temp->siguiente mitad de los tiempos de capacidad actual
  • Ahora elimine el Node temporal entre los Nodes temporal->anterior y temporal->siguiente al volver a vincular los Nodes
  • Disminuir la capacidad en uno
  • Valor de retorno del elemento eliminado