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:
Operaciones | Cola | Devolver |
---|---|---|
empujar__frente(4) | 4 | _ |
retroceder__(2) | 4, 2 | _ |
empujar__medio(1) | 4, 1, 2 | _ |
frente_pop() | 1, 2 | 4 |
pop__medio() | 2 | 1 |
pop__frente() | _ | 2 |
pop__frente() | _ | -1 |
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++
// 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:
empujar__frente(x) | pop__frente() | retroceder__(x) | retroceder____() | empujar__medio(x) | pop__medio() |
---|---|---|---|---|---|
O(1) | O(1) | O(1) | O(1) | O(1) | O(1) |
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++
// 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:
empujar__frente(x) | pop__frente() | retroceder__(x) | retroceder____() | empujar__medio(x) | pop__medio() |
---|---|---|---|---|---|
O(1) | O(1) | O(1) | O(1) | EN) | EN) |
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
Publicación traducida automáticamente
Artículo escrito por Akash_chowrasia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA