Cree una estructura de datos personalizada que evalúe funciones en O(1)

Posted on by Rudeus Greyrat

Cree una estructura de datos personalizada de modo que tenga funciones: – 

  • ObtenerÚltimoElemento(); 
  • EliminarÚltimoElemento(); 
  • AñadirElemento() 
  • ObtenerMin()

Todas las funciones deben ser de O (1)
Fuente de la pregunta: preguntas de la entrevista de Amazon

Acercarse : 

  1. cree una pila personalizada de estructura de tipo con dos elementos, (elemento, min_till_now) 
  2. implementar las funciones en este tipo de datos personalizado 

Implementación:

C++

// program to demonstrate customized data structure
// which supports functions in O(1)
#include <iostream>
#include <vector>
using namespace std;
const int MAXX = 1000;
 
// class stack
class stack {
    int minn;
    int size;
 
public:
    stack()
    {
        minn = 99999;
        size = -1;
    }
    vector<pair<int, int> > arr;
    int GetLastElement();
    int RemoveLastElement();
    int AddElement(int element);
    int GetMin();
};
 
// utility function for adding a new element
int stack::AddElement(int element)
{
    if (size > MAXX) {
        cout << "stack overflow, max size reached!\n";
        return 0;
    }
    if (element < minn)
        minn = element;
    arr.push_back(make_pair(element, minn));
    size++;
    return 1;
}
 
// utility function for returning last element of stack
int stack::GetLastElement()
{
    if (size == -1) {
        cout << "No elements in stack\n";
        return 0;
    }
    return arr[size].first;
}
 
// utility function for removing last element successfully;
int stack::RemoveLastElement()
{
    if (size == -1) {
        cout << "stack empty!!!\n";
        return 0;
    }
 
    // updating minimum element
    if (size > 0 && arr[size - 1].second > arr[size].second) {
        minn = arr[size - 1].second;
    }
    arr.pop_back();
    size -= 1;
    return 1;
}
 
// utility function for returning min element till now;
int stack::GetMin()
{
    if (size == -1) {
        cout << "stack empty!!\n";
        return 0;
    }
    return arr[size].second;
}
 
// Driver code
int main()
{
    stack s;
    int success = s.AddElement(5);
    if (success == 1)
        cout << "5 inserted successfully\n";
 
    success = s.AddElement(7);
    if (success == 1)
        cout << "7 inserted successfully\n";
 
    success = s.AddElement(3);
    if (success == 1)
        cout << "3 inserted successfully\n";
    int min1 = s.GetMin();
    cout << "min element  :: " << min1 << endl;
 
    success = s.RemoveLastElement();
    if (success == 1)
        cout << "removed successfully\n";
 
    success = s.AddElement(2);
    if (success == 1)
        cout << "2 inserted successfully\n";
 
    success = s.AddElement(9);
    if (success == 1)
        cout << "9 inserted successfully\n";
    int last = s.GetLastElement();
    cout << "Last element :: " << last << endl;
 
    success = s.AddElement(0);
    if (success == 1)
        cout << "0 inserted successfully\n";
    min1 = s.GetMin();
    cout << "min element  :: " << min1 << endl;
 
    success = s.RemoveLastElement();
    if (success == 1)
        cout << "removed successfully\n";
 
    success = s.AddElement(11);
    if (success == 1)
        cout << "11 inserted successfully\n";
    min1 = s.GetMin();
    cout << "min element  :: " << min1 << endl;
 
    return 0;
}

Java

// program to demonstrate customized data structure
// which supports functions in O(1)
import java.util.ArrayList;
public class Gfg
{
   
  // class Pair
  static class Pair{
    int element;
    int minElement;
 
    public Pair(int element, int minElement) {
      this.element = element;
      this.minElement = minElement;
    }
  }
  int min;
  ArrayList<Pair> stack = new ArrayList<>();
 
  public Gfg() {
    this.min = Integer.MAX_VALUE;
  }
 
  // utility function for adding a new element
  void addElement(int x)
  {
    if(stack.size() == 0 || x < min)
    {
      min=x;
    }
    Pair pair = new Pair(x,min);
    stack.add(pair);
    System.out.println(x + " inserted successfully");
  }
 
  // utility function for returning last element of stack
  int getLastElement()
  {
    if (stack.size() == 0)
    {
      System.out.println("UnderFlow Error");
      return -1;
    }
    else
    {
      return stack.get(stack.size() - 1).element;
    }
  }
 
  // utility function for removing last element successfully;
  void removeLastElement()
  {
 
    if (stack.size() == 0)
    {
      System.out.println("UnderFlow Error");
    }
    else if (stack.size() > 1)
    {
      min=stack.get(stack.size() - 2).minElement;
    }
    else
    {
      min=Integer.MAX_VALUE;
    }
    stack.remove(stack.size() - 1);
    System.out.println("removed successfully");
  }
 
  // utility function for returning min element till now;
  int getMin()
  {
    if (stack.size() == 0)
    {
      System.out.println("UnderFlow Error");
      return -1;
    }
    return stack.get(stack.size() - 1).minElement;
  }
 
  // Driver Code
  public static void main(String[] args) {
    Gfg newStack = new Gfg();
    newStack.addElement(5);
    newStack.addElement(7);
    newStack.addElement(3);
    System.out.println("min element :: "+newStack.getMin());
    newStack.removeLastElement();
    newStack.addElement(2);
    newStack.addElement(9);
    System.out.println("last element :: "+newStack.getLastElement());
    newStack.addElement(0);
    System.out.println("min element :: "+newStack.getMin());
    newStack.removeLastElement();
    newStack.addElement(11);
    System.out.println("min element :: "+newStack.getMin());
  }
}
 
// This code is contributed by AkashYadav4.

Python3

# Program to demonstrate customized data structure
# which supports functions in O(1)
import sys
 
stack = []
Min = sys.maxsize
 
# Utility function for adding a new element
def addElement(x):
     
    global Min, stack
    if (len(stack) == 0 or x < Min):
        Min = x
    pair = [x, Min]
    stack.append(pair)
    print(x, "inserted successfully")
 
# Utility function for returning last
# element of stack
def getLastElement():
     
    global Min, stack
     
    if (len(stack) == 0):
        print("UnderFlow Error")
        return -1
    else:
        return stack[-1][0]
 
# Utility function for removing last
# element successfully;
def removeLastElement():
     
    global Min, stack
    if (len(stack) == 0):
        print("UnderFlow Error")
    elif (len(stack) > 1):
        Min = stack[-2][1]
    else:
        Min = sys.maxsize
    stack.pop()
     
    print("removed successfully")
 
# Utility function for returning min
# element till now;
def getMin():
     
    global Min, stack
    if (len(stack) == 0):
        print("UnderFlow Error")
        return -1
         
    return stack[-1][1]
 
# Driver code
addElement(5)
addElement(7)
addElement(3)
print("min element ::", getMin())
removeLastElement()
addElement(2)
addElement(9)
print("Last element ::", getLastElement())
addElement(0)
print("min element ::", getMin())
removeLastElement()
addElement(11)
print("min element ::", getMin())
 
# This code is contributed by mukesh07

C#

// program to demonstrate customized data structure
// which supports functions in O(1)
using System;
using System.Collections.Generic;
class GFG {
 
  static List<Tuple<int,int>> stack = new List<Tuple<int,int>>();
  static int min = Int32.MaxValue;
  
  // utility function for adding a new element
  static void addElement(int x)
  {
    if(stack.Count == 0 || x < min)
    {
      min=x;
    }
    Tuple<int,int> pair = new Tuple<int,int>(x,min);
    stack.Add(pair);
    Console.WriteLine(x + " inserted successfully");
  }
  
  // utility function for returning last element of stack
  static int getLastElement()
  {
    if (stack.Count == 0)
    {
      Console.WriteLine("UnderFlow Error");
      return -1;
    }
    else
    {
      return stack[stack.Count - 1].Item1;
    }
  }
  
  // utility function for removing last element successfully;
  static void removeLastElement()
  {
  
    if (stack.Count == 0)
    {
      Console.WriteLine("UnderFlow Error");
    }
    else if (stack.Count > 1)
    {
      min=stack[stack.Count - 2].Item2;
    }
    else
    {
      min=Int32.MaxValue;
    }
    stack.RemoveAt(stack.Count - 1);
    Console.WriteLine("removed successfully");
  }
  
  // utility function for returning min element till now;
  static int getMin()
  {
    if (stack.Count == 0)
    {
      Console.WriteLine("UnderFlow Error");
      return -1;
    }
    return stack[stack.Count - 1].Item2;
  }
   
  static void Main() {
    addElement(5);
    addElement(7);
    addElement(3);
    Console.WriteLine("min element :: "+getMin());
    removeLastElement();
    addElement(2);
    addElement(9);
    Console.WriteLine("Last element :: "+getLastElement());
    addElement(0);
    Console.WriteLine("min element :: "+getMin());
    removeLastElement();
    addElement(11);
    Console.WriteLine("min element :: "+getMin());
  }
}
 
// This code is contributed by divyeshrabadiya07.

Javascript

<script>
    // program to demonstrate customized data structure
    // which supports functions in O(1)
     
    let min;
    let stack = [];
 
    min = Number.MAX_VALUE
 
    // utility function for adding a new element
    function addElement(x)
    {
      if(stack.length == 0 || x < min)
      {
        min=x;
      }
      let pair = [x,min];
      stack.push(pair);
      document.write(x + " inserted successfully" + "</br>");
    }
 
    // utility function for returning last element of stack
    function getLastElement()
    {
      if (stack.length == 0)
      {
        document.write("UnderFlow Error" + "</br>");
        return -1;
      }
      else
      {
        return stack[stack.length - 1][0];
      }
    }
 
    // utility function for removing last element successfully;
    function removeLastElement()
    {
 
      if (stack.length == 0)
      {
        document.write("UnderFlow Error" + "</br>");
      }
      else if (stack.length > 1)
      {
        min=stack[stack.length - 2][1];
      }
      else
      {
        min=Number.MAX_VALUE;
      }
      stack.pop();
      document.write("removed successfully" + "</br>");
    }
 
    // utility function for returning min element till now;
    function getMin()
    {
      if (stack.length == 0)
      {
        document.write("UnderFlow Error" + "</br>");
        return -1;
      }
      return stack[stack.length - 1][1];
    }
     
    addElement(5);
    addElement(7);
    addElement(3);
    document.write("min element :: "+getMin() + "</br>");
    removeLastElement();
    addElement(2);
    addElement(9);
    document.write("Last element :: "+getLastElement() + "</br>");
    addElement(0);
    document.write("min element :: "+getMin() + "</br>");
    removeLastElement();
    addElement(11);
    document.write("min element :: "+getMin() + "</br>");
     
    // This code is contributed by rameshtravel07.
</script>
Producción

5 inserted successfully
7 inserted successfully
3 inserted successfully
min element ::3
removed successfully
2 inserted successfully
9 inserted successfully
Last element::9
0 inserted successfully
min element ::0
removed successfully
11 inserted successfully
min element ::2

Complejidad del tiempo: Cada función se ejecuta en O(1)

Este artículo es una contribución de Mandeep Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 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 *