Diseñe una pila dinámica especial utilizando una array que admita todas las operaciones de pila, como push() , pop() , peek(), isEmpty() y getMin() en complejidades constantes de tiempo y espacio.
Ejemplos:
Suponiendo que la orientación de derecha a izquierda es la orientación de arriba a abajo y realizando las operaciones:
- Push(10): 10 se agrega a la parte superior de la pila. A partir de entonces, la pila se modifica a {10}.
- Empuje (4): 4 se agrega a la parte superior de la pila. A partir de entonces, la pila se modifica a {10, 4}.
- Push(9): 9 se agrega a la parte superior de la pila. A partir de entonces, la pila se modifica a {10, 4, 9}.
- Push(6): 6 se agrega a la parte superior de la pila. A partir de entonces, la pila se modifica a {10, 4, 9, 6}.
- Empuje (5): 5 se agrega a la parte superior de la pila. A partir de entonces, la pila se modifica a {10, 4, 9, 6, 5}.
- Peek(): Imprime el elemento superior de la pila 5.
- getMin(): Imprime el elemento mínimo de la pila 4.
- Pop(): elimina el elemento superior, 5 de la pila. A partir de entonces, la pila se modifica a {10, 4, 9, 6}.
- Pop(): elimina el elemento superior, 6 de la pila. A partir de entonces, la pila se modifica a {10, 4, 9}.
- Pop(): elimina el elemento superior, 9 de la pila. A partir de entonces, la pila se modifica a {10, 4}.
- Pop(): elimina el elemento superior, 4 de la pila. A partir de entonces, la pila se modifica a {10}.
- Peek(): Imprime el elemento superior de la pila 10.
- getMin(): Imprime el elemento mínimo de la pila 10.
Enfoque: para implementar una pila dinámica usando una array, la idea es duplicar el tamaño de la array cada vez que se llena. Siga los pasos a continuación para resolver el problema:
- Inicialice una array, digamos arr[] con un tamaño inicial de 5 , para implementar la pila.
- Además, inicialice dos variables, digamos top y minEle para almacenar el índice del elemento superior de la pila y el elemento mínimo de la pila.
- Ahora, realice las siguientes operaciones de pila:
- isEmpty(): Comprueba si la pila está vacía o no .
- Retorna verdadero si la parte superior es menor o igual a 0 . De lo contrario, devuelve falso.
- 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 .
- Si la array utilizada está llena, duplique el tamaño de la array y luego copie todos los elementos de la array anterior en la nueva array y luego asigne la dirección de la nueva array a la array original. A partir de entonces, realice la operación de empuje como se explicó anteriormente.
- Pop(): elimina un elemento de la parte superior de la pila.
- Sea y el elemento eliminado . Surgen dos casos
- Si y es mayor o igual que 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 como minEle = 2*minEle-y .
- getMin(): encuentra el valor mínimo de la pila.
- Si la pila no está vacía, devuelve el valor de minEle . De lo contrario, devuelva » -1 » e imprima » Subdesbordamiento «.
- isEmpty(): Comprueba si la pila está vacía o no .
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
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// A class to create
// our special stack
class Stack {
private:
// Initial size of
// the Array
int Max = 5;
// Array for the stack
// implementation
int* arr = new int(Max);
// Stores the minimum
// Element of the stack
int minEle = 0;
// Stores the top element
// of the stack
int top = 0;
public:
// Method to check whether
// stack is empty or not
bool empty()
{
if (top <= 0) {
return true;
}
else {
return false;
}
}
// Method to push elements
// to the Special Stack
void push(int x)
{
// If stack is empty
if (empty()) {
// Assign x to minEle
minEle = x;
// Assign x to arr[top]
arr[top] = x;
// Increment top by 1
top++;
}
// If array is full
else if (top == Max) {
// Update the Max size
Max = 2 * Max;
int* temp = new int(Max);
// Traverse the array arr[]
for (int i = 0; i < top; i++) {
temp[i] = arr[i];
}
// If x is less than minEle
if (x < minEle) {
// Push 2*x-minEle
temp[top] = 2 * x - minEle;
// Assign x to minEle
minEle = x;
top++;
}
// Else
else {
// Push x to stack
temp[top] = x;
top++;
}
// Assign address of the
// temp to arr
arr = temp;
}
else {
// If x is less
// than minEle
if (x < minEle) {
// Push 2*x-minEle
arr[top] = 2 * x - minEle;
top++;
// Update minEle
minEle = x;
}
else {
// Push x to the
// stack
arr[top] = x;
top++;
}
}
}
// Method to pop the elements
// from the stack.
void pop()
{
// If stack is empty
if (empty()) {
cout << "Underflow" << endl;
return;
}
// Stores the top element
// of the stack
int t = arr[top - 1];
// If t is less than
// the minEle
if (t < minEle) {
// Pop the minEle
cout << "Popped element : " << minEle << endl;
// Update minEle
minEle = 2 * minEle - t;
}
// Else
else {
// Pop the topmost element
cout << "Popped element : " << t << endl;
}
top--;
return;
}
// Method to find the topmost
// element of the stack
int peek()
{
// If stack is empty
if (empty()) {
cout << "Underflow" << endl;
return -1;
}
// Stores the top element
// of the stack
int t = arr[top - 1];
// If t is less than
// the minEle
if (t < minEle) {
return minEle;
}
// Else
else {
return t;
}
}
// Method to find the Minimum
// element of the Special stack
int getMin()
{
// If stack is empty
if (empty()) {
cout << "Underflow" << endl;
return -1;
}
// Else
else {
return minEle;
}
}
};
// Driver Code
int main()
{
Stack S;
S.push(10);
S.push(4);
S.push(9);
S.push(6);
S.push(5);
cout << "Top Element : " << S.peek() << endl;
cout << "Minimum Element : " << S.getMin() << endl;
S.pop();
S.pop();
S.pop();
S.pop();
cout << "Top Element : " << S.peek() << endl;
cout << "Minimum Element : " << S.getMin() << endl;
return 0;
}
Java
// Java program for the above approach
public class Main
{
// Initial size of
// the Array
static int Max = 5;
// Array for the stack
// implementation
static int[] arr = new int[Max];
// Stores the minimum
// Element of the stack
static int minEle = 0;
// Stores the top element
// of the stack
static int Top = 0;
// Method to check whether
// stack is empty or not
static boolean empty()
{
if (Top <= 0) {
return true;
}
else {
return false;
}
}
// Method to push elements
// to the Special Stack
static void push(int x)
{
// If stack is empty
if (empty()) {
// Assign x to minEle
minEle = x;
// Assign x to arr[top]
arr[Top] = x;
// Increment top by 1
Top++;
}
// If array is full
else if (Top == Max) {
// Update the Max size
Max = 2 * Max;
int[] temp = new int[Max];
// Traverse the array arr[]
for (int i = 0; i < Top; i++) {
temp[i] = arr[i];
}
// If x is less than minEle
if (x < minEle) {
// Push 2*x-minEle
temp[Top] = 2 * x - minEle;
// Assign x to minEle
minEle = x;
Top++;
}
// Else
else {
// Push x to stack
temp[Top] = x;
Top++;
}
// Assign address of the
// temp to arr
arr = temp;
}
else {
// If x is less
// than minEle
if (x < minEle) {
// Push 2*x-minEle
arr[Top] = 2 * x - minEle;
Top++;
// Update minEle
minEle = x;
}
else {
// Push x to the
// stack
arr[Top] = x;
Top++;
}
}
}
// Method to pop the elements
// from the stack.
static void pop()
{
// If stack is empty
if (empty()) {
System.out.print("Underflow");
return;
}
// Stores the top element
// of the stack
int t = arr[Top - 1];
// If t is less than
// the minEle
if (t < minEle) {
// Pop the minEle
System.out.println("Popped element : " + minEle);
// Update minEle
minEle = 2 * minEle - t;
}
// Else
else {
// Pop the topmost element
System.out.println("Popped element : " + t);
}
Top--;
return;
}
// Method to find the topmost
// element of the stack
static int peek()
{
// If stack is empty
if (empty()) {
System.out.println("Underflow");
return -1;
}
// Stores the top element
// of the stack
int t = arr[Top - 1];
// If t is less than
// the minEle
if (t < minEle) {
return minEle;
}
// Else
else {
return t;
}
}
// Method to find the Minimum
// element of the Special stack
static int getMin()
{
// If stack is empty
if (empty()) {
System.out.println("Underflow");
return -1;
}
// Else
else {
return minEle;
}
}
// Driver code
public static void main(String[] args) {
push(10);
push(4);
push(9);
push(6);
push(5);
System.out.println("Top Element : " + peek());
System.out.println("Minimum Element : " + getMin());
pop();
pop();
pop();
pop();
System.out.println("Top Element : " + peek());
System.out.println("Minimum Element : " + getMin());
}
}
// This code is contributed by rameshtravel07.
Python3
# Python3 program for the above approach
# Initial size of
# the Array
Max = 5
# Array for the stack
# implementation
arr = [0]*Max
# Stores the minimum
# Element of the stack
minEle = 0
# Stores the top element
# of the stack
Top = 0
# Method to check whether
# stack is empty or not
def empty():
if (Top <= 0):
return True
else:
return False
# Method to push elements
# to the Special Stack
def push(x):
global arr, Top, Max, minEle
# If stack is empty
if empty():
# Assign x to minEle
minEle = x
# Assign x to arr[top]
arr[Top] = x
# Increment top by 1
Top+=1
# If array is full
elif (Top == Max):
# Update the Max size
Max = 2 * Max
temp = [0]*Max
# Traverse the array arr[]
for i in range(Top):
temp[i] = arr[i]
# If x is less than minEle
if (x < minEle):
# Push 2*x-minEle
temp[Top] = 2 * x - minEle
# Assign x to minEle
minEle = x
Top+=1
# Else
else:
# Push x to stack
temp[Top] = x
Top+=1
# Assign address of the
# temp to arr
arr = temp
else:
# If x is less
# than minEle
if (x < minEle):
# Push 2*x-minEle
arr[Top] = 2 * x - minEle
Top+=1
# Update minEle
minEle = x
else:
# Push x to the
# stack
arr[Top] = x
Top+=1
# Method to pop the elements
# from the stack.
def pop():
global Top, minEle
# If stack is empty
if empty():
print("Underflow")
return
# Stores the top element
# of the stack
t = arr[Top - 1]
# If t is less than
# the minEle
if (t < minEle) :
# Pop the minEle
print("Popped element :", minEle)
# Update minEle
minEle = 2 * minEle - t
# Else
else:
# Pop the topmost element
print("Popped element :", t)
Top-=1
return
# Method to find the topmost
# element of the stack
def peek():
# If stack is empty
if empty():
print("Underflow")
return -1
# Stores the top element
# of the stack
t = arr[Top - 1]
# If t is less than
# the minEle
if (t < minEle):
return minEle
# Else
else:
return t
# Method to find the Minimum
# element of the Special stack
def getMin():
# If stack is empty
if empty():
print("Underflow")
return -1
# Else
else:
return minEle
push(10)
push(4)
push(9)
push(6)
push(5)
print("Top Element :", peek())
print("Minimum Element :", getMin())
pop()
pop()
pop()
pop()
print("Top Element :", peek())
print("Minimum Element :", getMin())
# This code is contributed by mukesh07.
C#
// C# program for the above approach
using System;
class GFG {
// Initial size of
// the Array
static int Max = 5;
// Array for the stack
// implementation
static int[] arr = new int[Max];
// Stores the minimum
// Element of the stack
static int minEle = 0;
// Stores the top element
// of the stack
static int Top = 0;
// Method to check whether
// stack is empty or not
static bool empty()
{
if (Top <= 0) {
return true;
}
else {
return false;
}
}
// Method to push elements
// to the Special Stack
static void push(int x)
{
// If stack is empty
if (empty()) {
// Assign x to minEle
minEle = x;
// Assign x to arr[top]
arr[Top] = x;
// Increment top by 1
Top++;
}
// If array is full
else if (Top == Max) {
// Update the Max size
Max = 2 * Max;
int[] temp = new int[Max];
// Traverse the array arr[]
for (int i = 0; i < Top; i++) {
temp[i] = arr[i];
}
// If x is less than minEle
if (x < minEle) {
// Push 2*x-minEle
temp[Top] = 2 * x - minEle;
// Assign x to minEle
minEle = x;
Top++;
}
// Else
else {
// Push x to stack
temp[Top] = x;
Top++;
}
// Assign address of the
// temp to arr
arr = temp;
}
else {
// If x is less
// than minEle
if (x < minEle) {
// Push 2*x-minEle
arr[Top] = 2 * x - minEle;
Top++;
// Update minEle
minEle = x;
}
else {
// Push x to the
// stack
arr[Top] = x;
Top++;
}
}
}
// Method to pop the elements
// from the stack.
static void pop()
{
// If stack is empty
if (empty()) {
Console.WriteLine("Underflow");
return;
}
// Stores the top element
// of the stack
int t = arr[Top - 1];
// If t is less than
// the minEle
if (t < minEle) {
// Pop the minEle
Console.WriteLine("Popped element : " + minEle);
// Update minEle
minEle = 2 * minEle - t;
}
// Else
else {
// Pop the topmost element
Console.WriteLine("Popped element : " + t);
}
Top--;
return;
}
// Method to find the topmost
// element of the stack
static int peek()
{
// If stack is empty
if (empty()) {
Console.WriteLine("Underflow");
return -1;
}
// Stores the top element
// of the stack
int t = arr[Top - 1];
// If t is less than
// the minEle
if (t < minEle) {
return minEle;
}
// Else
else {
return t;
}
}
// Method to find the Minimum
// element of the Special stack
static int getMin()
{
// If stack is empty
if (empty()) {
Console.WriteLine("Underflow");
return -1;
}
// Else
else {
return minEle;
}
}
static void Main() {
push(10);
push(4);
push(9);
push(6);
push(5);
Console.WriteLine("Top Element : " + peek());
Console.WriteLine("Minimum Element : " + getMin());
pop();
pop();
pop();
pop();
Console.WriteLine("Top Element : " + peek());
Console.WriteLine("Minimum Element : " + getMin());
}
}
// This code is contributed by suresh07.
Javascript
<script>
// Javascript program for the above approach
// Initial size of
// the Array
let Max = 5;
// Array for the stack
// implementation
let arr = new Array(Max);
// Stores the minimum
// Element of the stack
let minEle = 0;
// Stores the top element
// of the stack
let Top = 0;
// Method to check whether
// stack is empty or not
function empty()
{
if (Top <= 0) {
return true;
}
else {
return false;
}
}
// Method to push elements
// to the Special Stack
function push(x)
{
// If stack is empty
if (empty()) {
// Assign x to minEle
minEle = x;
// Assign x to arr[top]
arr[Top] = x;
// Increment top by 1
Top++;
}
// If array is full
else if (Top == Max) {
// Update the Max size
Max = 2 * Max;
let temp = new Array(Max);
// Traverse the array arr[]
for (let i = 0; i < Top; i++) {
temp[i] = arr[i];
}
// If x is less than minEle
if (x < minEle) {
// Push 2*x-minEle
temp[Top] = 2 * x - minEle;
// Assign x to minEle
minEle = x;
Top++;
}
// Else
else {
// Push x to stack
temp[Top] = x;
Top++;
}
// Assign address of the
// temp to arr
arr = temp;
}
else {
// If x is less
// than minEle
if (x < minEle) {
// Push 2*x-minEle
arr[Top] = 2 * x - minEle;
Top++;
// Update minEle
minEle = x;
}
else {
// Push x to the
// stack
arr[Top] = x;
Top++;
}
}
}
// Method to pop the elements
// from the stack.
function pop()
{
// If stack is empty
if (empty()) {
document.write("Underflow" + "</br>");
return;
}
// Stores the top element
// of the stack
let t = arr[Top - 1];
// If t is less than
// the minEle
if (t < minEle) {
// Pop the minEle
document.write("Popped element : " + minEle + "</br>");
// Update minEle
minEle = 2 * minEle - t;
}
// Else
else {
// Pop the topmost element
document.write("Popped element : " + t + "</br>");
}
Top--;
return;
}
// Method to find the topmost
// element of the stack
function peek()
{
// If stack is empty
if (empty()) {
document.write("Underflow" + "</br>");
return -1;
}
// Stores the top element
// of the stack
let t = arr[Top - 1];
// If t is less than
// the minEle
if (t < minEle) {
return minEle;
}
// Else
else {
return t;
}
}
// Method to find the Minimum
// element of the Special stack
function getMin()
{
// If stack is empty
if (empty()) {
document.write("Underflow" + "</br>");
return -1;
}
// Else
else {
return minEle;
}
}
push(10);
push(4);
push(9);
push(6);
push(5);
document.write("Top Element : " + peek() + "</br>");
document.write("Minimum Element : " + getMin() + "</br>");
pop();
pop();
pop();
pop();
document.write("Top Element : " + peek() + "</br>");
document.write("Minimum Element : " + getMin() + "</br>");
// This code is contributed by divyesh072019.
</script>
Producción
Top Element : 5 Minimum Element : 4 Popped element : 5 Popped element : 6 Popped element : 9 Popped element : 4 Top Element : 10 Minimum Element : 10
Complejidad Temporal: O(1) para cada operación
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por prathamjha5683 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA