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:
C++
#include <iostream>
#include <stdlib.h>
using namespace std;
/* A simple stack class with
basic stack functionalities */
class Stack {
private:
static const int max = 100;
int arr[max];
int top;
public:
Stack() { top = -1; }
bool isEmpty();
bool isFull();
int pop();
void push(int x);
};
/* Stack's member method to check
if the stack is empty */
bool Stack::isEmpty()
{
if (top == -1)
return true;
return false;
}
/* Stack's member method to check
if the stack is full */
bool Stack::isFull()
{
if (top == max - 1)
return true;
return false;
}
/* Stack's member method to remove
an element from it */
int Stack::pop()
{
if (isEmpty()) {
cout << "Stack Underflow";
abort();
}
int x = arr[top];
top--;
return x;
}
/* Stack's member method to insert
an element to it */
void Stack::push(int x)
{
if (isFull()) {
cout << "Stack Overflow";
abort();
}
top++;
arr[top] = x;
}
/* A class that supports all the stack
operations and one additional
operation getMin() that returns the
minimum element from stack at
any time. This class inherits from
the stack class and uses an
auxiliary stack that holds minimum
elements */
class SpecialStack : public Stack {
Stack min;
public:
int pop();
void push(int x);
int getMin();
};
/* SpecialStack's member method to insert
an element to it. This method
makes sure that the min stack is also
updated with appropriate minimum
values */
void SpecialStack::push(int x)
{
if (isEmpty() == true) {
Stack::push(x);
min.push(x);
}
else {
Stack::push(x);
int y = min.pop();
min.push(y);
if (x < y)
min.push(x);
else
min.push(y);
}
}
/* SpecialStack's member method to
remove an element from it. This method
removes top element from min stack also. */
int SpecialStack::pop()
{
int x = Stack::pop();
min.pop();
return x;
}
/* SpecialStack's member method to get
minimum element from it. */
int SpecialStack::getMin()
{
int x = min.pop();
min.push(x);
return x;
}
/* Driver program to test SpecialStack
methods */
int main()
{
SpecialStack s;
s.push(10);
s.push(20);
s.push(30);
cout << s.getMin() << endl;
s.push(5);
cout << s.getMin();
return 0;
}
Java
// Java implementation of SpecialStack
// Note : here we use Stack class for
// Stack implementation
import java.util.Stack;
/* A class that supports all the
stack operations and one additional
operation getMin() that returns
the minimum element from stack at
any time. This class inherits from
the stack class and uses an
auxiliary stack that holds minimum
elements */
class SpecialStack extends Stack<Integer> {
Stack<Integer> min = new Stack<>();
/* SpecialStack's member method to
insert an element to it. This method
makes sure that the min stack is
also updated with appropriate minimum
values */
void push(int x)
{
if (isEmpty() == true) {
super.push(x);
min.push(x);
}
else {
super.push(x);
int y = min.pop();
min.push(y);
if (x < y)
min.push(x);
else
min.push(y);
}
}
/* SpecialStack's member method to
insert an element to it. This method
makes sure that the min stack is
also updated with appropriate minimum
values */
public Integer pop()
{
int x = super.pop();
min.pop();
return x;
}
/* SpecialStack's member method to get
minimum element from it. */
int getMin()
{
int x = min.pop();
min.push(x);
return x;
}
/* Driver program to test SpecialStack
methods */
public static void main(String[] args)
{
SpecialStack s = new SpecialStack();
s.push(10);
s.push(20);
s.push(30);
System.out.println(s.getMin());
s.push(5);
System.out.println(s.getMin());
}
}
// This code is contributed by Sumit Ghosh
Python3
# Python3 program for the
# above approach
# A simple stack class with
# basic stack functionalities
class stack:
def __init__(self):
self.array = []
self.top = -1
self.max = 100
# Stack's member method to check
# if the stack is empty
def isEmpty(self):
if self.top == -1:
return True
else:
return False
# Stack's member method to check
# if the stack is full
def isFull(self):
if self.top == self.max - 1:
return True
else:
return False
# Stack's member method to
# insert an element to it
def push(self, data):
if self.isFull():
print('Stack OverFlow')
return
else:
self.top += 1
self.array.append(data)
# Stack's member method to
# remove an element from it
def pop(self):
if self.isEmpty():
print('Stack UnderFlow')
return
else:
self.top -= 1
return self.array.pop()
# A class that supports all the stack
# operations and one additional
# operation getMin() that returns the
# minimum element from stack at
# any time. This class inherits from
# the stack class and uses an
# auxiliary stack that holds
# minimum elements
class SpecialStack(stack):
def __init__(self):
super().__init__()
self.Min = stack()
# SpecialStack's member method to
# insert an element to it. This method
# makes sure that the min stack is also
# updated with appropriate minimum
# values
def push(self, x):
if self.isEmpty():
super().push(x)
self.Min.push(x)
else:
super().push(x)
y = self.Min.pop()
self.Min.push(y)
if x <= y:
self.Min.push(x)
else:
self.Min.push(y)
# SpecialStack's member method to
# remove an element from it. This
# method removes top element from
# min stack also.
def pop(self):
x = super().pop()
self.Min.pop()
return x
# SpecialStack's member method
# to get minimum element from it.
def getmin(self):
x = self.Min.pop()
self.Min.push(x)
return x
# Driver code
if __name__ == '__main__':
s = SpecialStack()
s.push(10)
s.push(20)
s.push(30)
print(s.getmin())
s.push(5)
print(s.getmin())
# This code is contributed by rachitkatiyar99
C++
/* SpecialStack's member method to
insert an element to it. This method
makes sure that the min stack is
also updated with appropriate minimum
values */
void SpecialStack::push(int x)
{
if (isEmpty() == true) {
Stack::push(x);
min.push(x);
}
else {
Stack::push(x);
int y = min.pop();
min.push(y);
/* push only when the incoming element
of main stack is smaller
than or equal to top of auxiliary stack */
if (x <= y)
min.push(x);
}
}
/* SpecialStack's member method to
remove an element from it. This method
removes top element from min stack also. */
int SpecialStack::pop()
{
int x = Stack::pop();
int y = min.pop();
/* Push the popped element y back
only if it is not equal to x */
if (y != x)
min.push(y);
return x;
}
Java
/* SpecialStack's member method to
insert an element to it. This method
makes sure that the min stack is
also updated with appropriate minimum
values */
void push(int x)
{
if (isEmpty() == true) {
super.push(x);
min.push(x);
}
else {
super.push(x);
int y = min.pop();
min.push(y);
/* push only when the incoming
element of main stack is smaller
than or equal to top of auxiliary stack */
if (x <= y)
min.push(x);
}
}
/* SpecialStack's member method to
remove an element from it. This method
removes top element from min stack also. */
public Integer pop()
{
int x = super.pop();
int y = min.pop();
/* Push the popped element y back
only if it is not equal to x */
if (y != x)
min.push(y);
return x;
}
// This code is contributed by Sumit Ghosh
Python3
''' SpecialStack's member method to insert an element to it. This method makes sure that the min stack is also updated with appropriate minimum values ''' def push(x): if (isEmpty() == True): super.append(x); min.append(x); else: super.append(x); y = min.pop(); min.append(y); ''' push only when the incoming element of main stack is smaller than or equal to top of auxiliary stack ''' if (x <= y): min.append(x); ''' SpecialStack's member method to remove an element from it. This method removes top element from min stack also. ''' def pop(): x = super.pop(); y = min.pop(); ''' Push the popped element y back only if it is not equal to x ''' if (y != x): min.append(y); return x; # This code contributed by umadevi9616
C#
/* SpecialStack's member method to
insert an element to it. This method
makes sure that the min stack is
also updated with appropriate minimum
values */
void push(int x)
{
if (min.Count==0) {
super.Push(x);
min.Push(x);
}
else {
super.Push(x);
int y = min.Pop();
min.Push(y);
/* push only when the incoming
element of main stack is smaller
than or equal to top of auxiliary stack */
if (x <= y)
min.Push(x);
}
}
/* SpecialStack's member method to
remove an element from it. This method
removes top element from min stack also. */
public int pop()
{
int x = super.Pop();
int y = min.Pop();
/* Push the popped element y back
only if it is not equal to x */
if (y != x)
min.Push(y);
return x;
}
// This code is contributed by umadevi9616
Javascript
<script>
/* SpecialStack's member method to
insert an element to it. This method
makes sure that the min stack is
also updated with appropriate minimum
values */
function push(x)
{
if (isEmpty() == true) {
super.push(x);
min.push(x);
}
else {
super.push(x);
var y = min.pop();
min.push(y);
/* push only when the incoming
element of main stack is smaller
than or equal to top of auxiliary stack */
if (x <= y)
min.push(x);
}
}
/* SpecialStack's member method to
remove an element from it. This method
removes top element from min stack also. */
function pop()
{
var x = super.pop();
var y = min.pop();
/* Push the popped element y back
only if it is not equal to x */
if (y != x)
min.push(y);
return x;
}
// This code is contributed by umadevi9616
</script>
C++
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
/* A special stack having peek() pop() and
* push() along with additional getMin() that
* returns minimum value in a stack without
* using extra space and all operations in O(1)
* time.. ???? */
class SpecialStack
{
// Sentinel value for min
int min = -1;
// DEMO_VALUE
static const int demoVal = 9999;
stack<int> st;
public:
void getMin()
{
cout << "min is: " << min << endl;
}
void push(int val)
{
// If stack is empty OR current element
// is less than min, update min.
if (st.empty() || val < min)
{
min = val;
}
// Encode the current value with
// demoVal, combine with min and
// insert into stack
st.push(val * demoVal + min);
cout << "pushed: " << val << endl;
}
int pop()
{
// if stack is empty return -1;
if ( st.empty() ) {
cout << "stack underflow" << endl ;
return -1;
}
int val = st.top();
st.pop();
// If stack is empty, there would
// be no min value present, so
// make min as -1
if (!st.empty())
min = st.top() % demoVal;
else
min = -1;
cout << "popped: " << val / demoVal << endl;
// Decode actual value from
// encoded value
return val / demoVal;
}
int peek()
{
// Decode actual value
// from encoded value
return st.top() / demoVal;
}
};
// Driver Code
int main()
{
SpecialStack s;
vector<int> arr = { 3, 2, 6, 1, 8, 5, 5, 5, 5 };
for(int i = 0; i < arr.size(); i++)
{
s.push(arr[i]);
s.getMin();
}
cout << endl;
for(int i = 0; i < arr.size(); i++)
{
s.pop();
s.getMin();
}
return 0;
}
// This code is contributed by scisaif
Java
import java.util.Stack;
/* A special stack having peek() pop() and push() along with
* additional getMin() that returns minimum value in a stack
* without using extra space and all operations in O(1)
* time.. 🙂
* */
public class SpecialStack {
int min = -1; // sentinel value for min
static int demoVal = 9999; // DEMO_VALUE
Stack<Integer> st = new Stack<Integer>();
void getMin() { System.out.println("min is: " + min); }
void push(int val)
{
// if stack is empty OR current element is less than
// min, update min..
if (st.isEmpty() || val < min) {
min = val;
}
st.push(val * demoVal
+ min); // encode the current value with
// demoVal, combine with min and
// insert into stack
System.out.println("pushed: " + val);
}
int pop()
{
// if stack is empty return -1;
if (st.isEmpty() ) {
System.out.println("stack underflow");
return -1;
}
int val = st.pop();
if (!st.isEmpty()) // if stack is empty, there would
// be no min value present, so
// make min as -1
min = st.peek() % demoVal;
else
min = -1;
System.out.println("popped: " + val / demoVal);
return val / demoVal; // decode actual value from
// encoded value
}
int peek()
{
return st.peek() / demoVal; // decode actual value
// from encoded value
}
// Driver Code
public static void main(String[] args)
{
SpecialStack s = new SpecialStack();
int[] arr = { 3, 2, 6, 1, 8, 5, 5, 5, 5 };
for (int i = 0; i < arr.length; i++) {
s.push(arr[i]);
s.getMin();
}
System.out.println();
for (int i = 0; i < arr.length; i++) {
s.pop();
s.getMin();
}
}
}
Python3
# A special stack having peek() pop() and
# push() along with additional getMin() that
# returns minimum value in a stack without
# using extra space and all operations in O(1)
# time.. ????
class SpecialStack:
def __init__(self):
# Sentinel value for min
self.minm = -1
# DEMO_VALUE
SpecialStack.demoVal = 9999
self.st = []
def getMin(self):
print("min is: ", self.minm)
def push(self, val):
# If stack is empty OR current element
# is less than min, update min.
if len(self.st) == 0 or val < self.minm:
self.minm = val
# Encode the current value with
# demoVal, combine with min and
# insert into stack
self.st.append(val*self.demoVal + self.minm)
print("pushed: ", val)
def pop(self):
# if stack is empty return -1
if len(self.st) == 0:
print("stack underflow")
return -1
val = self.st.pop()
# If stack is empty, there would
# be no min value present, so
# make min as -1
if len(self.st) != 0:
self.minm = self.st[-1] % self.demoVal
else:
self.minm = -1
print("popped: ", val // self.demoVal)
# Decode actual value from
# encoded value
return val // self.demoVal
def peek(self):
# Decode actual value
# from encoded value
return self.st[-1] // self.demoVal
# Driver Code
if __name__ == "__main__":
s = SpecialStack()
arr = [3, 2, 6, 1, 8, 5, 5, 5, 5]
for i in range(len(arr)):
s.push(arr[i])
s.getMin()
print("\n")
for i in range(len(arr)):
s.pop()
s.getMin()
# This code is contributed by pankajkumar70792.
C#
using System;
using System.Collections.Generic;
/* A special stack having peek() pop() and push() along with
* additional getMin() that returns minimum value in a stack
* without using extra space and all operations in O(1)
* time.. 🙂
* */
public class SpecialStack {
int min = -1; // sentinel value for min
static int demoVal = 9999; // DEMO_VALUE
Stack<int> st = new Stack<int>();
void getMin() { Console.WriteLine("min is: " + min); }
void push(int val)
{
// if stack is empty OR current element is less than
// min, update min..
if (st.Count==0 || val < min) {
min = val;
}
st.Push(val * demoVal
+ min); // encode the current value with
// demoVal, combine with min and
// insert into stack
Console.WriteLine("pushed: " + val);
}
int pop()
{
// if stack is empty return -1;
if (st.Count==0 ) {
Console.WriteLine("stack underflow");
return -1;
}
int val = st.Pop();
if (st.Count!=0) // if stack is empty, there would
// be no min value present, so
// make min as -1
min = st.Peek() % demoVal;
else
min = -1;
Console.WriteLine("popped: " + val / demoVal);
return val / demoVal; // decode actual value from
// encoded value
}
int peek()
{
return st.Peek() / demoVal; // decode actual value
// from encoded value
}
// Driver Code
public static void Main(String[] args)
{
SpecialStack s = new SpecialStack();
int[] arr = { 3, 2, 6, 1, 8, 5, 5, 5, 5 };
for (int i = 0; i < arr.Length; i++) {
s.push(arr[i]);
s.getMin();
}
Console.WriteLine();
for (int i = 0; i < arr.Length; i++) {
s.pop();
s.getMin();
}
}
}
// This code is contributed by gauravrajput1
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