Problema: diseñe una estructura de datos, una SpecialQueue que admita las siguientes operaciones enque, deque, getMin() o getMax() donde la operación getMin() toma O(1) tiempo.
Ejemplo:
Let the data to be inserted in queue be - 4, 2, 1, 6 Operation Queue Output push(4) 4 - push(2) 4, 2 - push(1) 4, 2, 1 - getMin() 4, 2, 1 1 push(6) 4, 2, 1, 6 - pop() 2, 1, 6 4 pop() 1, 6 2 pop() 6 1 getMin() 6 6 // Notice the getMin() function call // It returns the minimum element // of all the values present in the queue
Enfoque: La idea es utilizar la Cola de doble terminación para almacenar en orden creciente si la estructura debe devolver el elemento mínimo y almacenar en orden decreciente si la estructura debe devolver el elemento máximo. Las operaciones de la Estructura de Datos se definen de la siguiente manera:
Enque
- Inserte el elemento en la estructura de la cola.
- Si el tamaño de la estructura Deque está vacío, el tamaño de Deque es 0. Luego, inserte el elemento desde atrás.
- De lo contrario, si hay algunos elementos en la estructura de Deque, extraiga los elementos de Deque hasta que la parte posterior de Deque sea mayor que el elemento actual y luego, finalmente, inserte el elemento desde atrás.
Deque
- Si el primer elemento de Deque es igual al elemento frontal de la cola, extraiga los elementos de Queue y Deque al mismo tiempo.
- De lo contrario, extraiga el elemento del principio de la cola para mantener el orden de los elementos.
Obtener mínimo
Devuelve el elemento frontal del Deque para obtener el elemento mínimo del elemento actual de la cola.
A continuación se muestra la implementación del enfoque anterior:
Java
import java.util.*;
import java.io.*;
class SpecialQueue {
Queue<Integer> q;
Deque<Integer> dq;
public SpecialQueue(){
q = new LinkedList<>();
dq = new ArrayDeque<>();
}
void enque(int data){
// remove all elements from
// from deque which are greater
// than the current element 'data'
while(!dq.isEmpty() && dq.getLast() > data){
dq.removeLast();
}
// If queue is empty then
// while loop is skipped.
dq.addLast(data);
q.add(data);
}
void deque(){
// If min element is present
// at front of queue
if(dq.getFirst() == q.peek()){
dq.removeFirst();
}
q.remove();
}
// Method to get min element in Queue
int getMin() throws Exception{
// If queue is Empty, return Exception
if(q.isEmpty())
throw new Exception("Queue is Empty");
else
return dq.getFirst();
}
public static void main(String[] args) throws Exception {
SpecialQueue arr = new SpecialQueue();
arr.enque(1);
arr.enque(2);
arr.enque(4);
System.out.println(arr.getMin());
arr.deque();
System.out.println(arr.getMin());
}
}
C++
// C++ implementation to design
// a queue data structure to get
// minimum element in O(1) time
#include <bits/stdc++.h>
using namespace std;
template <typename T>
// Structure of the queue
class MinMaxQueue {
public:
// Queue to store the
// element to maintain the
// order of insertion
queue<T> Q;
// Doubly ended queue to
// get the minimum element
// in the O(1) time
deque<T> D;
// Function to push a element
// into the queue
void enque_element(T element)
{
// If there is no element
// in the queue
if (Q.size() == 0) {
Q.push(element);
D.push_back(element);
}
else {
Q.push(element);
// Pop the elements out
// until the element at
// back is greater than
// current element
while (!D.empty() &&
D.back() > element) {
D.pop_back();
}
D.push_back(element);
}
}
// Function to pop the element
// out from the queue
void deque_element()
{
// Condition when the Minimum
// element is the element at
// the front of the Deque
if (Q.front() == D.front()) {
Q.pop();
D.pop_front();
}
else {
Q.pop();
}
}
// Function to get the
// minimum element from
// the queue
T getMin()
{
return D.front();
}
};
// Driver Code
int main()
{
MinMaxQueue<int> k;
int example[3] = { 1, 2, 4 };
// Loop to enque element
for (int i = 0; i < 3; i++) {
k.enque_element(example[i]);
}
cout << k.getMin() << "\n";
k.deque_element();
cout << k.getMin() << "\n";
}
Python3
# Python 3 implementation to design # a queue data structure to get # minimum element in O(1) time from collections import deque as dq # class for the queue class MinMaxQueue: def __init__(self): # Queue to store the # element to maintain the # order of insertion self.Q = dq([]) # Doubly ended queue to # get the minimum element # in the O(1) time self.D = dq([]) # Function to push a element # into the queue def enque_element(self, element): # If there is no element # in the queue if (len(self.Q) == 0): self.Q.append(element) self.D.append(element) else: self.Q.append(element) # Pop the elements out # until the element at # back is greater than # current element while (self.D and self.D[-1] > element): self.D.pop() self.D.append(element) # Function to pop the element # out from the queue def deque_element(self,): # Condition when the Minimum # element is the element at # the front of the Deque if (self.Q[0] == self.D[0]): self.Q.popleft() self.D.popleft() else: self.Q.popleft() # Function to get the # minimum element from # the queue def getMin(self,): return self.D[0] # Driver Code if __name__ == '__main__': k = MinMaxQueue() example = [1, 2, 4] # Loop to enque element for i in range(3): k.enque_element(example[i]) print(k.getMin()) k.deque_element() print(k.getMin())
Producción:
1 2
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)