Nuestra tarea es diseñar 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 realizarse con complejidad de tiempo 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 Special-Stack 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 el tiempo O(1) y el espacio extra O(1) . Sin embargo, en el artículo anterior no se recuperan los elementos originales. Solo se devuelve el elemento mínimo en un momento determinado. En este artículo, el enfoque anterior se modifica para que los elementos originales también se puedan recuperar durante una operación pop() . Enfoque: considere un mínimo variable en el que almacenamos el elemento mínimo en la pila. Ahora, ¿qué pasa si sacamos el elemento mínimo de la pila? ¿Cómo actualizamos la variable mínima al siguiente valor mínimo? Una solución es mantener otra pila ordenada para que el elemento más pequeño esté siempre en la parte superior. Sin embargo, este es un enfoque de espacio O(n).
Para lograr esto en el espacio O(1) , necesitamos una forma de almacenar el valor actual de un elemento y el siguiente valor mínimo en el mismo Node. Esto se puede hacer aplicando matemáticas simples:
new_value = 2*current_value - minimum
Empujamos este new_value en la pila en lugar de current_value. Para recuperar valor_actual y el siguiente mínimo de valor_nuevo:
current_value = (new_value + minimum)/2 minimum = new_value - 2*current
Cuando se realiza la operación Push(x) , seguimos el siguiente algoritmo:
- Si la pila está vacía
- insertar x en la pila
- hacer mínimo igual a x.
- Si la pila no está vacía
- si x es menor que el minimo
- establecer la temperatura igual a 2*x-mínimo
- establecer mínimo igual a x
- establecer x igual a la temperatura
- insertar x en la pila
Cuando se realiza la operación Pop(x) , seguimos el siguiente algoritmo:
- Si la pila no está vacía
- establecer x igual al elemento superior
- si x es menor que el minimo
- establecer mínimo igual a 2*mínimo – x
- establecer x igual a (x+mínimo)/2
- volver x
Cuando se llama a getMin(), devolvemos el elemento almacenado en variable, mínimo :
Java
// Java program to retrieve original elements of the
// from a Stack which returns the minimum element
// in O(1) time and O(1) space
class Stack {
Node top;
// Stores minimum element of the stack
int minimum;
// Function to push an element
void push(Node node)
{
int current = node.getData();
if (top == null) {
top = node;
minimum = current;
}
else {
if (current < minimum) {
node.setData(2 * current - minimum);
minimum = current;
}
node.setNext(top);
top = node;
}
}
// Retrieves topmost element
Node pop()
{
Node node = top;
if (node != null) {
int current = node.getData();
if (current < minimum) {
minimum = 2 * minimum - current;
node.setData((current + minimum) / 2);
}
top = top.getNext();
}
return node;
}
// Retrieves topmost element without
// popping it from the stack
Node peek()
{
Node node = null;
if (top != null) {
node = new Node();
int current = top.getData();
node.setData(current < minimum ? minimum : current);
}
return node;
}
// Function to print all elements in the stack
void printAll()
{
Node ptr = top;
int min = minimum;
if (ptr != null) { // if stack is not empty
while (true) {
int val = ptr.getData();
if (val < min) {
min = 2 * min - val;
val = (val + min) / 2;
}
System.out.print(val + " ");
ptr = ptr.getNext();
if (ptr == null)
break;
}
System.out.println();
}
else
System.out.println("Empty!");
}
// Returns minimum of Stack
int getMin()
{
return minimum;
}
boolean isEmpty()
{
return top == null;
}
}
// Node class which contains data
// and pointer to next node
class Node {
int data;
Node next;
Node()
{
data = -1;
next = null;
}
Node(int d)
{
data = d;
next = null;
}
void setData(int data)
{
this.data = data;
}
void setNext(Node next)
{
this.next = next;
}
Node getNext()
{
return next;
}
int getData()
{
return data;
}
}
// Driver Code
public class Main {
public static void main(String[] args)
{
// Create a new stack
Stack stack = new Stack();
Node node;
// Push the element into the stack
stack.push(new Node(5));
stack.push(new Node(3));
stack.push(new Node(4));
// Calls the method to print the stack
System.out.println("Elements in the stack are:");
stack.printAll();
// Print current minimum element if stack is
// not empty
System.out.println(stack.isEmpty() ? "\nEmpty Stack!" :
"\nMinimum: " + stack.getMin());
// Push new elements into the stack
stack.push(new Node(1));
stack.push(new Node(2));
// Printing the stack
System.out.println("\nStack after adding new elements:");
stack.printAll();
// Print current minimum element if stack is
// not empty
System.out.println(stack.isEmpty() ? "\nEmpty Stack!" :
"\nMinimum: " + stack.getMin());
// Pop elements from the stack
node = stack.pop();
System.out.println("\nElement Popped: "
+ (node == null ? "Empty!" : node.getData()));
node = stack.pop();
System.out.println("Element Popped: "
+ (node == null ? "Empty!" : node.getData()));
// Printing stack after popping elements
System.out.println("\nStack after removing top two elements:");
stack.printAll();
// Printing current Minimum element in the stack
System.out.println(stack.isEmpty() ? "\nEmpty Stack!" :
"\nMinimum: " + stack.getMin());
// Printing top element of the stack
node = stack.peek();
System.out.println("\nTop: " + (node == null ?
"\nEmpty!" : node.getData()));
}
}
Python3
"""
Python program to retrieve original elements of the
from a Stack which returns the minimum element
in O(1) time and O(1) space
"""
# Class to make a Node
class Node:
# Constructor which assign argument to node'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
m = self.minimum
out=[]
if temp is None:
print("Empty Stack")
else:
while not temp is None :
val = temp.value
if val < m:
m = (2 * m) -val
val = ( val + m ) / 2
out.append(str(int(val)))
temp=temp.next
out=' '.join(out)
return (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:
return 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:
return self.minimum
else:
return 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
else:
new_node = Node(value)
if value < self.minimum:
temp = (2 * value) - self.minimum
new_node.value = temp
self.minimum = value
new_node.next = self.top
self.top = new_node
# This method is used to pop top of stack
def pop(self):
new_node = self.top
if self.top is None:
print( "Stack is empty")
else:
removedNode = new_node.value
if removedNode < self.minimum:
self.minimum = ( ( 2 * self.minimum ) - removedNode )
new_node.value = ( (removedNode + self.minimum) / 2 )
self.top = self.top.next
return int(new_node.value)
# Driver program to test above class
stack = Stack()
stack.push(5)
stack.push(3)
stack.push(4)
print("Elements in the stack are:")
print(stack)
print("Minimum: {}" .format( stack.getMin() ) )
stack.push(1)
stack.push(2)
print("Stack after adding new elements:")
print(stack)
print("Minimum:{}" .format( stack.getMin() ) )
print("Element Popped: {}".format(stack.pop()))
print("Element Popped: {}".format(stack.pop()))
print("Stack after removing top two elements: ")
print(stack)
print("Minimum: {}" .format( stack.getMin() ) )
print("Top: {}".format( stack.peek() ) )
# This code is contributed by Blinkii
C#
// C# program to retrieve original elements of the
// from a Stack which returns the minimum element
// in O(1) time and O(1) space
using System;
public class Stack
{
Node top;
// Stores minimum element of the stack
public int minimum;
// Function to push an element
public void push(Node node)
{
int current = node.getData();
if (top == null)
{
top = node;
minimum = current;
}
else
{
if (current < minimum)
{
node.setData(2 * current - minimum);
minimum = current;
}
node.setNext(top);
top = node;
}
}
// Retrieves topmost element
public Node pop()
{
Node node = top;
if (node != null)
{
int current = node.getData();
if (current < minimum)
{
minimum = 2 * minimum - current;
node.setData((current + minimum) / 2);
}
top = top.getNext();
}
return node;
}
// Retrieves topmost element without
// popping it from the stack
public Node peek()
{
Node node = null;
if (top != null)
{
node = new Node();
int current = top.getData();
node.setData(current < minimum ? minimum : current);
}
return node;
}
// Function to print all elements in the stack
public void printAll()
{
Node ptr = top;
int min = minimum;
if (ptr != null)
{
// if stack is not empty
while (true)
{
int val = ptr.getData();
if (val < min)
{
min = 2 * min - val;
val = (val + min) / 2;
}
Console.Write(val + " ");
ptr = ptr.getNext();
if (ptr == null)
break;
}
Console.WriteLine();
}
else
Console.WriteLine("Empty!");
}
// Returns minimum of Stack
public int getMin()
{
return minimum;
}
public bool isEmpty()
{
return top == null;
}
}
// Node class which contains data
// and pointer to next node
public class Node
{
public int data;
public Node next;
public Node()
{
data = -1;
next = null;
}
public Node(int d)
{
data = d;
next = null;
}
public void setData(int data)
{
this.data = data;
}
public void setNext(Node next)
{
this.next = next;
}
public Node getNext()
{
return next;
}
public int getData()
{
return data;
}
}
// Driver Code
public class MainClass
{
public static void Main(String[] args)
{
// Create a new stack
Stack stack = new Stack();
Node node;
// Push the element into the stack
stack.push(new Node(5));
stack.push(new Node(3));
stack.push(new Node(4));
// Calls the method to print the stack
Console.WriteLine("Elements in the stack are:");
stack.printAll();
// Print current minimum element if stack is
// not empty
Console.WriteLine(stack.isEmpty() ? "\nEmpty Stack!" :
"\nMinimum: " + stack.getMin());
// Push new elements into the stack
stack.push(new Node(1));
stack.push(new Node(2));
// Printing the stack
Console.WriteLine("\nStack after adding new elements:");
stack.printAll();
// Print current minimum element if stack is
// not empty
Console.WriteLine(stack.isEmpty() ? "\nEmpty Stack!" :
"\nMinimum: " + stack.getMin());
// Pop elements from the stack
node = stack.pop();
if(node == null)
Console.WriteLine("\nElement Popped: "+"Empty!");
else
Console.WriteLine("\nElement Popped: "+node.getData());
node = stack.pop();
if(node == null)
Console.WriteLine("Element Popped: "+"Empty!");
else
Console.WriteLine("Element Popped: "+node.getData());
// Printing stack after popping elements
Console.WriteLine("\nStack after removing top two elements:");
stack.printAll();
// Printing current Minimum element in the stack
Console.WriteLine(stack.isEmpty() ? "\nEmpty Stack!" :
"\nMinimum: " + stack.getMin());
// Printing top element of the stack
node = stack.peek();
if(node == null)
Console.WriteLine("\nTop: "+"\nEmpty!");
else
Console.WriteLine("\nTop: "+node.getData());
}
}
// This code is contributed by Rajput-Ji
C++
// Cpp program to retrieve original elements of the
// from a Stack which returns the minimum element
// in O(1) time and O(1) space
#include<bits/stdc++.h>
using namespace std;
// Node class which contains data
// and pointer to next node
class Node {
public:
int data;
Node* next;
Node()
{
data = -1;
next = NULL;
}
Node(int d)
{
data = d;
next = NULL;
}
void setData(int data)
{
this->data = data;
}
void setNext(Node* next)
{
this->next = next;
}
Node* getNext()
{
return next;
}
int getData()
{
return data;
}
};
class Stack{
public:
Node* top;
// Stores minimum element of the stack
int minimum;
// Function to push an element
void push(Node* node)
{
int current=node->getData();
if(top == NULL)
{
top=node;
minimum=current;
}
else{
if(current < minimum)
{
node->setData(2*current - minimum);
minimum = current;
}
node->setNext(top);
top=node;
}
}
// Retrieves topmost element
Node* pop()
{
Node* node = top;
if(node!=NULL)
{
int current=node->getData();
if(current<minimum)
{
minimum = 2*minimum - current;
node->setData((current + minimum) / 2);
}
top = top->getNext();
}
return node;
}
// Retrieves topmost element without
// popping it from the stack
Node* peek()
{
Node* node = NULL;
if (top != NULL) {
node = new Node();
int current = top->getData();
node->setData(current < minimum ? minimum : current);
}
return node;
}
// Function to print all elements in the stack
void printAll()
{
Node* ptr = top;
int min = minimum;
if (ptr != NULL) { // if stack is not empty
while (true) {
int val = ptr->getData();
if (val < min) {
min = 2 * min - val;
val = (val + min) / 2;
}
cout << val << " ";
ptr = ptr->getNext();
if (ptr == NULL)
break;
}
cout << '\n';
}
else
cout << "Empty!\n";
}
// Returns minimum of Stack
int getMin()
{
return minimum;
}
bool isEmpty()
{
return top == NULL;
}
};
int main()
{
Stack* stack = new Stack();
Node* node;
stack->push(new Node(5));
stack->push(new Node(3));
stack->push(new Node(4));
// Calls the method to print the stack
cout << "Elements in the stack are:\n";
stack->printAll();
// Print current minimum element if stack is
// not empty
if(stack->isEmpty())
cout << "Empty Stack!\n";
else
cout << "Minimum: " << stack->getMin() << '\n';
// Push new elements into the stack
stack->push(new Node(1));
stack->push(new Node(2));
// Printing the stack
cout << "Stack after adding new elements:\n";
stack->printAll();
// Print current minimum element if stack is
// not empty
if(stack->isEmpty())
cout << "Empty Stack!\n";
else
cout << "Minimum: " << stack->getMin() << '\n';
// Pop elements from the stack
node = stack->pop();
cout << "Element Popped: ";
if(node == NULL)
cout << "Empty!\n";
else
cout << node->getData() << '\n';
node = stack->pop();
cout << "Element Popped: ";
if(node == NULL)
cout << "Empty!\n";
else
cout << node->getData() << '\n';
// Printing stack after popping elements
cout << "Stack after removing top two elements:\n";
stack->printAll();
// Printing current Minimum element in the stack
if(stack->isEmpty())
cout << "Empty Stack!\n";
else
cout << "Minimum: " << stack->getMin() << '\n';
// Printing top element of the stack
node = stack->peek();
cout << "Top: " ;
if(node == NULL)
cout << "Empty!\n";
else
cout << node->getData() << '\n';
return 0;
}
Producción:
Elements in the stack are: 4 3 5 Minimum: 3 Stack after adding new elements: 2 1 4 3 5 Minimum: 1 Element Popped: 2 Element Popped: 1 Stack after removing top two elements: 4 3 5 Minimum: 3 Top: 4
Publicación traducida automáticamente
Artículo escrito por sejalpawar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA