Diseñe una estructura de datos de cola para obtener el mínimo o el máximo en tiempo O (1)

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)

Publicación traducida automáticamente

Artículo escrito por Artemisia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *