Pregunta: Diseñe una estructura de datos SpecialStack que admita todas las operaciones de pila como push(), pop(), isEmpty(), isFull() y una operación adicional getMin() que debería devolver el elemento mínimo de SpecialStack. Todas estas operaciones de SpecialStack deben ser O(1). Para implementar SpecialStack, solo debe usar la estructura de datos Stack estándar y ninguna otra estructura de datos como arrays, listas, etc.
Ejemplo:
Consider the following SpecialStack 16 --> TOP 15 29 19 18 When getMin() is called it should return 15, which is the minimum element in the current stack. If we do pop two times on stack, the stack becomes 29 --> TOP 19 18 When getMin() is called, it should return 18 which is the minimum in the current stack.
Aquí se analiza un enfoque que utiliza tiempo O(1) y espacio adicional O(n) .
En este artículo, se analiza un nuevo enfoque que admite mínimo con O(1) espacio adicional. Definimos una variable minEle que almacena el elemento mínimo actual en la pila. Ahora la parte interesante es cómo manejar el caso cuando se elimina el elemento mínimo. Para manejar esto, insertamos «2x – minEle» en la pila en lugar de x para que el elemento mínimo anterior pueda recuperarse usando el minEle actual y su valor almacenado en la pila. A continuación se detallan los pasos y una explicación del trabajo.
Push(x) : Inserta x en la parte superior de la pila.
- Si la pila está vacía, inserte x en la pila y haga que minEle sea igual a x.
- Si la pila no está vacía, compare x con minEle. Se presentan dos casos:
- Si x es mayor o igual a minEle, simplemente inserte x.
- Si x es menor que minEle, inserte (2*x – minEle) en la pila y haga que minEle sea igual a x. Por ejemplo, el minEle anterior era 3. Ahora queremos insertar 2. Actualizamos minEle como 2 e insertamos 2*2 – 3 = 1 en la pila.
Pop(): elimina un elemento de la parte superior de la pila.
- Retire el elemento de la parte superior. Sea y el elemento eliminado. Se presentan dos casos:
- Si y es mayor o igual a minEle, el elemento mínimo en la pila sigue siendo minEle.
- Si y es menor que minEle, el elemento mínimo ahora se convierte en (2*minEle – y), así que actualice (minEle = 2*minEle – y). Aquí es donde recuperamos el mínimo anterior del mínimo actual y su valor en la pila. Por ejemplo, deje que el elemento a eliminar sea 1 y minEle sea 2. Eliminamos 1 y actualizamos minEle como 2*2 – 1 = 3.
Puntos importantes:
- La pila no contiene el valor real de un elemento si es mínimo hasta ahora.
- El elemento mínimo real siempre se almacena en minEle
Ilustración
empujar (x)
- Número a insertar: 3, la pila está vacía, así que inserte 3 en la pila y minEle = 3.
- Número a insertar: 5, la pila no está vacía, 5> minEle, inserte 5 en la pila y minEle = 3.
- Número a insertar: 2, la pila no está vacía, 2< minEle, inserte (2*2-3 = 1) en la pila y minEle = 2.
- Número a insertar: 1, la pila no está vacía, 1< minEle, inserte (2*1-2 = 0) en la pila y minEle = 1.
- Número a insertar: 1, la pila no está vacía, 1 = minEle, inserte 1 en la pila y minEle = 1.
- Número a insertar: -1, la pila no está vacía, -1 < minEle, inserte (2*-1 – 1 = -3) en la pila y minEle = -1.
Estallido()
- Inicialmente, el elemento mínimo minEle en la pila es -1.
- Número eliminado: -3, dado que -3 es menor que el elemento mínimo, el número original que se elimina es minEle, que es -1, y el nuevo minEle = 2*-1 – (-3) = 1
- Número eliminado: 1, 1 == minEle, por lo que el número eliminado es 1 y minEle sigue siendo igual a 1.
- Número eliminado: 0, 0< minEle, el número original es minEle, que es 1 y el nuevo minEle = 2*1 – 0 = 2.
- Número eliminado: 1, 1< minEle, el número original es minEle, que es 2 y el nuevo minEle = 2*2 – 1 = 3.
- Número eliminado: 5, 5> minEle, el número original es 5 y minEle sigue siendo 3
Implementación:
C++
// C++ program to implement a stack that supports
// getMinimum() in O(1) time and O(1) extra space.
#include <bits/stdc++.h>
using namespace std;
// A user defined stack that supports getMin() in
// addition to push() and pop()
struct MyStack
{
stack<int> s;
int minEle;
// Prints minimum element of MyStack
void getMin()
{
if (s.empty())
cout << "Stack is empty\n";
// variable minEle stores the minimum element
// in the stack.
else
cout <<"Minimum Element in the stack is: "
<< minEle << "\n";
}
// Prints top element of MyStack
void peek()
{
if (s.empty())
{
cout << "Stack is empty ";
return;
}
int t = s.top(); // Top element.
cout << "Top Most Element is: ";
// If t < minEle means minEle stores
// value of t.
(t < minEle)? cout << minEle: cout << t;
}
// Remove the top element from MyStack
void pop()
{
if (s.empty())
{
cout << "Stack is empty\n";
return;
}
cout << "Top Most Element Removed: ";
int t = s.top();
s.pop();
// Minimum will change as the minimum element
// of the stack is being removed.
if (t < minEle)
{
cout << minEle << "\n";
minEle = 2*minEle - t;
}
else
cout << t << "\n";
}
// Removes top element from MyStack
void push(int x)
{
// Insert new number into the stack
if (s.empty())
{
minEle = x;
s.push(x);
cout << "Number Inserted: " << x << "\n";
return;
}
// If new number is less than minEle
else if (x < minEle)
{
s.push(2*x - minEle);
minEle = x;
}
else
s.push(x);
cout << "Number Inserted: " << x << "\n";
}
};
// Driver Code
int main()
{
MyStack s;
s.push(3);
s.push(5);
s.getMin();
s.push(2);
s.push(1);
s.getMin();
s.pop();
s.getMin();
s.pop();
s.peek();
return 0;
}
Java
// Java program to implement a stack that supports
// getMinimum() in O(1) time and O(1) extra space.
import java.util.*;
// A user defined stack that supports getMin() in
// addition to push() and pop()
class MyStack
{
Stack<Integer> s;
Integer minEle;
// Constructor
MyStack() { s = new Stack<Integer>(); }
// Prints minimum element of MyStack
void getMin()
{
// Get the minimum number in the entire stack
if (s.isEmpty())
System.out.println("Stack is empty");
// variable minEle stores the minimum element
// in the stack.
else
System.out.println("Minimum Element in the " +
" stack is: " + minEle);
}
// prints top element of MyStack
void peek()
{
if (s.isEmpty())
{
System.out.println("Stack is empty ");
return;
}
Integer t = s.peek(); // Top element.
System.out.print("Top Most Element is: ");
// If t < minEle means minEle stores
// value of t.
if (t < minEle)
System.out.println(minEle);
else
System.out.println(t);
}
// Removes the top element from MyStack
void pop()
{
if (s.isEmpty())
{
System.out.println("Stack is empty");
return;
}
System.out.print("Top Most Element Removed: ");
Integer t = s.pop();
// Minimum will change as the minimum element
// of the stack is being removed.
if (t < minEle)
{
System.out.println(minEle);
minEle = 2*minEle - t;
}
else
System.out.println(t);
}
// Insert new number into MyStack
void push(Integer x)
{
if (s.isEmpty())
{
minEle = x;
s.push(x);
System.out.println("Number Inserted: " + x);
return;
}
// If new number is less than original minEle
if (x < minEle)
{
s.push(2*x - minEle);
minEle = x;
}
else
s.push(x);
System.out.println("Number Inserted: " + x);
}
};
// Driver Code
public class Main
{
public static void main(String[] args)
{
MyStack s = new MyStack();
s.push(3);
s.push(5);
s.getMin();
s.push(2);
s.push(1);
s.getMin();
s.pop();
s.getMin();
s.pop();
s.peek();
}
}
Python 3
# Class to make a Node
class Node:
# Constructor which assign argument to nade's value
def __init__(self, value):
self.value = value
self.next = None
# This method returns the string representation of the object.
def __str__(self):
return "Node({})".format(self.value)
# __repr__ is same as __str__
__repr__ = __str__
class Stack:
# Stack Constructor initialise top of stack and counter.
def __init__(self):
self.top = None
self.count = 0
self.minimum = None
# This method returns the string representation of the object (stack).
def __str__(self):
temp = self.top
out = []
while temp:
out.append(str(temp.value))
temp = temp.next
out = '\n'.join(out)
return ('Top {} \n\nStack :\n{}'.format(self.top,out))
# __repr__ is same as __str__
__repr__=__str__
# This method is used to get minimum element of stack
def getMin(self):
if self.top is None:
return "Stack is empty"
else:
print("Minimum Element in the stack is: {}" .format(self.minimum))
# Method to check if Stack is Empty or not
def isEmpty(self):
# If top equals to None then stack is empty
if self.top == None:
return True
else:
# If top not equal to None then stack is empty
return False
# This method returns length of stack
def __len__(self):
self.count = 0
tempNode = self.top
while tempNode:
tempNode = tempNode.next
self.count+=1
return self.count
# This method returns top of stack
def peek(self):
if self.top is None:
print ("Stack is empty")
else:
if self.top.value < self.minimum:
print("Top Most Element is: {}" .format(self.minimum))
else:
print("Top Most Element is: {}" .format(self.top.value))
# This method is used to add node to stack
def push(self,value):
if self.top is None:
self.top = Node(value)
self.minimum = value
elif value < self.minimum:
temp = (2 * value) - self.minimum
new_node = Node(temp)
new_node.next = self.top
self.top = new_node
self.minimum = value
else:
new_node = Node(value)
new_node.next = self.top
self.top = new_node
print("Number Inserted: {}" .format(value))
# This method is used to pop top of stack
def pop(self):
if self.top is None:
print( "Stack is empty")
else:
removedNode = self.top.value
self.top = self.top.next
if removedNode < self.minimum:
print ("Top Most Element Removed :{} " .format(self.minimum))
self.minimum = ( ( 2 * self.minimum ) - removedNode )
else:
print ("Top Most Element Removed : {}" .format(removedNode))
# Driver program to test above class
stack = Stack()
stack.push(3)
stack.push(5)
stack.getMin()
stack.push(2)
stack.push(1)
stack.getMin()
stack.pop()
stack.getMin()
stack.pop()
stack.peek()
# This code is contributed by Blinkii
C#
// C# program to implement a stack
// that supports getMinimum() in O(1)
// time and O(1) extra space.
using System;
using System.Collections;
// A user defined stack that supports
// getMin() in addition to Push() and Pop()
public class MyStack
{
public Stack s;
public int minEle;
// Constructor
public MyStack()
{
s = new Stack();
}
// Prints minimum element of MyStack
public void getMin()
{
// Get the minimum number
// in the entire stack
if (s.Count==0)
Console.WriteLine("Stack is empty");
// variable minEle stores the minimum
// element in the stack.
else
Console.WriteLine("Minimum Element in the " +
" stack is: " + minEle);
}
// prints top element of MyStack
public void Peek()
{
if (s.Count==0)
{
Console.WriteLine("Stack is empty ");
return;
}
int t =(int)s.Peek(); // Top element.
Console.Write("Top Most Element is: ");
// If t < minEle means minEle stores
// value of t.
if (t < minEle)
Console.WriteLine(minEle);
else
Console.WriteLine(t);
}
// Removes the top element from MyStack
public void Pop()
{
if (s.Count==0)
{
Console.WriteLine("Stack is empty");
return;
}
Console.Write("Top Most Element Removed: ");
int t = (int)s.Pop();
// Minimum will change as the minimum element
// of the stack is being removed.
if (t < minEle)
{
Console.WriteLine(minEle);
minEle = 2*minEle - t;
}
else
Console.WriteLine(t);
}
// Insert new number into MyStack
public void Push(int x)
{
if (s.Count==0)
{
minEle = x;
s.Push(x);
Console.WriteLine("Number Inserted: " + x);
return;
}
// If new number is less than original minEle
if (x < minEle)
{
s.Push(2 * x - minEle);
minEle = x;
}
else
s.Push(x);
Console.WriteLine("Number Inserted: " + x);
}
}
// Driver Code
public class main
{
public static void Main(String []args)
{
MyStack s = new MyStack();
s.Push(3);
s.Push(5);
s.getMin();
s.Push(2);
s.Push(1);
s.getMin();
s.Pop();
s.getMin();
s.Pop();
s.Peek();
}
}
// This code is contributed by Arnab Kundu
Producción
Number Inserted: 3 Number Inserted: 5 Minimum Element in the stack is: 3 Number Inserted: 2 Number Inserted: 1 Minimum Element in the stack is: 1 Top Most Element Removed: 1 Minimum Element in the stack is: 2 Top Most Element Removed: 2 Top Most Element is: 5
¿Cómo funciona este enfoque?
Cuando el elemento a insertar es menor que minEle, insertamos «2x – minEle». Lo importante para las notas es, 2x – minEle siempre será menor que x (como se muestra a continuación), es decir, nuevo minEle y mientras sacamos este elemento veremos que algo inusual ha sucedido ya que el elemento sacado es menor que minEle. Así que estaremos actualizando minEle.
How 2*x - minEle is less than x in push()? x < minEle which means x - minEle < 0 // Adding x on both sides x - minEle + x < 0 + x 2*x - minEle < x We can conclude 2*x - minEle < new minEle
Al salir, si encontramos el elemento (y) menor que el minEle actual, encontramos el nuevo minEle = 2*minEle – y.
How previous minimum element, prevMinEle is, 2*minEle - y
in pop() is y the popped element?
// We pushed y as 2x - prevMinEle. Here
// prevMinEle is minEle before y was inserted
y = 2*x - prevMinEle
// Value of minEle was made equal to x
minEle = x .
new minEle = 2 * minEle - y
= 2*x - (2*x - prevMinEle)
= prevMinEle // This is what we wanted
Ejercicio:
También se puede utilizar un enfoque similar para encontrar el elemento máximo. Implemente una pila que admita getMax() en tiempo O(1) y espacio extra constante.
Enfoque 2: Cree un Node de clase que tenga dos variables val y min. val almacenará el valor real que vamos a insertar en la pila, mientras que min almacenará el valor mínimo visto hasta ahora hasta ese Node. mirar en el código para una mejor comprensión.
Implementación:
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class MinStack {
Stack<Node> s;
class Node{
int val;
int min;
public Node(int val,int min){
this.val=val;
this.min=min;
}
}
/** initialize your data structure here. */
public MinStack() {
this.s=new Stack<Node>();
}
public void push(int x) {
if(s.isEmpty()){
this.s.push(new Node(x,x));
}else{
int min=Math.min(this.s.peek().min,x);
this.s.push(new Node(x,min));
}
}
public int pop() {
return this.s.pop().val;
}
public int top() {
return this.s.peek().val;
}
public int getMin() {
return this.s.peek().min;
}
}
class GFG {
public static void main (String[] args) {
MinStack s=new MinStack();
s.push(-1);
s.push(10);
s.push(-4);
s.push(0);
System.out.println(s.getMin());
System.out.println(s.pop());
System.out.println(s.pop());
System.out.println(s.getMin());
}
}
//time O(1);
//it takes o(n) space since every node has to remember min value
//this code is contributed by gireeshgudaparthi
C#
/*package whatever //do not write package name here */
using System;
using System.Collections.Generic;
public class MinStack {
Stack<Node> s;
public class Node {
public int val;
public int min;
public Node(int val, int min) {
this.val = val;
this.min = min;
}
}
/** initialize your data structure here. */
public MinStack() {
this.s = new Stack<Node>();
}
public void push(int x) {
if (s.Count==0) {
this.s.Push(new Node(x, x));
} else {
int min = Math.Min(this.s.Peek().min, x);
this.s.Push(new Node(x, min));
}
}
public int pop() {
return this.s.Pop().val;
}
public int top() {
return this.s.Peek().val;
}
public int getMin() {
return this.s.Peek().min;
}
}
public class GFG {
public static void Main(String[] args) {
MinStack s = new MinStack();
s.push(-1);
s.push(10);
s.push(-4);
s.push(0);
Console.WriteLine(s.getMin());
Console.WriteLine(s.pop());
Console.WriteLine(s.pop());
Console.WriteLine(s.getMin());
}
}
// time O(1);
// it takes o(n) space since every node has to remember min value
// This code contributed by gauravrajput1
C++
#include <bits/stdc++.h>
#include <iostream>
#include <stack>
using namespace std;
int mini(int a, int b) { return a > b ? b : a; }
class MinStack {
public:
stack<pair<int, int> > s;
void push(int element)
{
/* new max will be given no. if stack is empty else
we compare given no. to max at current top of
stack*/
int new_min = s.empty()
? element
: mini(element, s.top().second);
// we push the pair of given_element,new_min in s
s.push({ element, new_min });
}
int pop()
{
int popped;
if (!s.empty()) {
// popped has popped number
popped = s.top().first;
s.pop();
}
else {
// print a message or throw exception etc
}
return popped;
}
int minimum()
{
int min_elem = s.top().second;
return min_elem;
}
};
int main()
{
MinStack s;
s.push(-1);
s.push(10);
s.push(-4);
s.push(0);
cout << s.minimum() << endl;
cout << s.pop() << endl;
cout << s.pop() << endl;
cout << s.minimum();
return 0;
}
// this code is contributed by Apoorv Shrivastava - VITB
Producción
-4 0 -4 -1
Este artículo es una contribución de Nikhil Tekwani. Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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