Todos conocemos las estructuras Stacks , también conocidas como estructuras de último en entrar, primero en salir (LIFO) . La pila tiene principalmente dos operaciones principales, a saber, empujar y sacar, donde empujar inserta un elemento en la parte superior y sacar un elemento de la parte superior de la pila.
Ahora, cada vez que se considera una implementación de pila, su tamaño está predeterminado o fijo. Aunque se asigna dinámicamente, una vez que se crea, su tamaño no se puede cambiar. Y de ahí surge una condición llamada «pila llena».
Pero, ¿qué pasa si una pila puede crecer a medida que se insertan más elementos o se van a insertar más elementos en el futuro? Recuerde, estamos hablando de una pila basada en arreglos. Growable Stack es el concepto de asignar más memoria de modo que la condición de «pila llena» no surja fácilmente.
Se puede implementar una pila basada en array ampliable asignando nueva memoria más grande que la memoria de la pila anterior y copiando elementos de la pila antigua a la nueva pila. Y luego, por fin, cambie el nombre de la nueva pila al nombre que se le dio a la pila anterior
Hay dos estrategias para la pila creciente:
- Estrategia ajustada : agregue una cantidad constante a la pila anterior (N + c)
- Estrategia de crecimiento : duplicar el tamaño de la pila anterior (2N)
Hay dos operaciones en la pila creciente:
- Operación de inserción regular: agregue un elemento en la parte superior de la pila
- Operación de inserción especial: Cree una nueva pila de tamaño mayor que la pila anterior (de acuerdo con una de las estrategias anteriores) y copie todos los elementos de la pila anterior y luego inserte el nuevo elemento en la nueva pila.
Implementación:
C++
// CPP Program to implement growable array based stack
// using tight strategy
#include <iostream>
using namespace std;
// constant amount at which stack is increased
#define BOUND 4
// top of the stack
int top = -1;
// length of stack
int length = 0;
// function to create new stack
int* create_new(int* a)
{
// allocate memory for new stack
int* new_a = new int[length + BOUND];
// copying the content of old stack
for (int i = 0; i < length; i++)
new_a[i] = a[i];
// re-sizing the length
length += BOUND;
return new_a;
}
// function to push new element
int* push(int* a, int element)
{
// if stack is full, create new one
if (top == length - 1)
a = create_new(a);
// insert element at top of the stack
a[++top] = element;
return a;
}
// function to pop an element
void pop(int* a)
{
if (top < 0) {
cout << "Stack is empty" << endl;
return;
}
top--;
}
// function to display
void display(int* a)
{
// if top is less than 0, that means stack is empty
if (top < 0)
cout << "Stack is Empty" << endl;
else {
cout << "Stack: ";
for (int i = 0; i <= top; i++)
cout << a[i] << " ";
cout << endl;
}
}
// Driver Code
int main()
{
// creating initial stack
int* a = create_new(a);
// pushing element to top of stack
a = push(a, 1);
a = push(a, 2);
a = push(a, 3);
a = push(a, 4);
display(a);
// pushing more element when stack is full
a = push(a, 5);
a = push(a, 6);
display(a);
a = push(a, 7);
a = push(a, 8);
display(a);
// pushing more element so that stack can grow
a = push(a, 9);
display(a);
return 0;
}
Java
// Java Program to implement growable array based stack
// using tight strategy
class GFG {
// constant amount at which stack is increased
static final int BOUND = 4;
// top of the stack
static int top = -1;
// length of stack
static int length = 0;
// function to create new stack
static int[] create_new(int[] a)
{
// allocate memory for new stack
int[] new_a = new int[length + BOUND];
// copying the content of old stack
for (int i = 0; i < length; i++)
new_a[i] = a[i];
// re-sizing the length
length += BOUND;
return new_a;
}
// function to push new element
static int[] push(int[] a, int element)
{
// if stack is full, create new one
if (top == length - 1)
a = create_new(a);
// insert element at top of the stack
a[++top] = element;
return a;
}
// function to pop an element
static void pop(int[] a)
{
if (top < 0) {
System.out.println("Stack is Empty");
return;
}
top--;
}
// function to display
static void display(int[] a)
{
// if top is less than 0, that means stack is empty
if (top < 0)
System.out.println("Stack is Empty");
else {
System.out.print("Stack: ");
for (int i = 0; i <= top; i++)
System.out.print(a[i] + " ");
System.out.println();
}
}
// Driver Code
public static void main(String args[])
{
// creating initial stack
int[] a = create_new(new int[length + BOUND]);
// pushing element to top of stack
a = push(a, 1);
a = push(a, 2);
a = push(a, 3);
a = push(a, 4);
display(a);
// pushing more element when stack is full
a = push(a, 5);
a = push(a, 6);
display(a);
a = push(a, 7);
a = push(a, 8);
display(a);
// pushing more element so that stack can grow
a = push(a, 9);
display(a);
}
}
// This code is contributed by Princi Singh
Python3
# Python3 Program to implement growable array based stack
# using tight strategy
# constant amount at which stack is increased
BOUND = 4
# top of the stack
top = -1
a = []
# length of stack
length = 0
# function to create new stack
def create_new():
global length
# allocate memory for new stack
new_a = [0 for i in range(length + BOUND)]
# copying the content of old stack
for i in range(length):
new_a[i] = a[i]
# re-sizing the length
length += BOUND
return new_a
# function to push new element
def push(element):
global top, a
# if stack is full, create new one
if (top == length - 1):
a = create_new()
top += 1
# insert element at top of the stack
a[top] = element
return a
# function to pop an element
def pop():
global top
# stack is empty can't pop
if (top < 0)
print("Stack is Empty")
else:
top -= 1
# function to display
def display():
global top
# if top is less than 0, that means stack is empty
if (top < 0)
print("Stack is Empty")
else:
print("Stack: ", end='')
for i in range(top + 1):
print(a[i], end=' ')
print()
# Driver Code
if __name__ == '__main__':
# creating initial stack
a = create_new()
# pushing element to top of stack
push(1)
push(2)
push(3)
push(4)
display()
# pushing more element when stack is full
push(5)
push(6)
display()
push(7)
push(8)
display()
# pushing more element so that stack can grow
push(9)
display()
# This code is contributed by rutvik_56.
C#
// C# Program to implement growable array based stack
// using tight strategy
using System;
class GFG {
// constant amount at which stack is increased
static int BOUND = 4;
// top of the stack
static int top = -1;
// length of stack
static int length = 0;
// function to create new stack
static int[] create_new(int[] a)
{
// allocate memory for new stack
int[] new_a = new int[length + BOUND];
// copying the content of old stack
for (int i = 0; i < length; i++)
new_a[i] = a[i];
// re-sizing the length
length += BOUND;
return new_a;
}
// function to push new element
static int[] push(int[] a, int element)
{
// if stack is full, create new one
if (top == length - 1)
a = create_new(a);
// insert element at top of the stack
a[++top] = element;
return a;
}
// function to pop an element
static void pop(int[] a)
{
if (top < 0) {
Console.WriteLine("Stack is Empty");
return;
}
top--;
}
// function to display
static void display(int[] a)
{
// if top is less than 0, that means stack is empty
if (top < 0)
Console.WriteLine("Stack is Empty");
else {
Console.Write("Stack: ");
for (int i = 0; i <= top; i++)
Console.Write(a[i] + " ");
Console.WriteLine();
}
}
// Driver Code
public static void Main(String[] args)
{
// creating initial stack
int[] a = create_new(new int[length + BOUND]);
// pushing element to top of stack
a = push(a, 1);
a = push(a, 2);
a = push(a, 3);
a = push(a, 4);
display(a);
// pushing more element when stack is full
a = push(a, 5);
a = push(a, 6);
display(a);
a = push(a, 7);
a = push(a, 8);
display(a);
// pushing more element so that stack can grow
a = push(a, 9);
display(a);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript Program to implement growable array based stack
// using tight strategy
// constant amount at which stack is increased
let BOUND = 4;
// s_top of the stack
let s_top = -1;
// length of stack
let length = 0;
// function to create new stack
function create_new(a) {
// allocate memory for new stack
let new_a = new Array(length + BOUND);
// copying the content of old stack
for (let i = 0; i < length; i++)
new_a[i] = a[i];
// re-sizing the length
length += BOUND;
return new_a;
}
// function to push new element
function push(a, element) {
// if stack is full, create new one
if (s_top == length - 1)
a = create_new(a);
// insert element at s_top of the stack
a[++s_top] = element;
return a;
}
// function to pop an element
function pop(a) {
if (s_top <0)
document.write("Stack is Empty" + "<br>");
else
s_top--;
}
// function to display
function display(a) {
// if s_top is less than 0, that means stack is empty
if (s_top <0)
document.write("Stack is Empty" + "<br>");
else {
document.write("Stack: ");
for (let i = 0; i <= s_top; i++)
document.write(a[i] + " ");
document.write("<br>");
}
}
// Driver Code
// creating initial stack
let a = create_new(new Array(length + BOUND));
// pushing element to s_top of stack
a = push(a, 1);
a = push(a, 2);
a = push(a, 3);
a = push(a, 4);
display(a);
// pushing more element when stack is full
a = push(a, 5);
a = push(a, 6);
display(a);
a = push(a, 7);
a = push(a, 8);
display(a);
// pushing more element so that stack can grow
a = push(a, 9);
display(a);
// This code is contributed by _saurabh_jaiswal
</script>
Producción
Stack: 1 2 3 4 Stack: 1 2 3 4 5 6 Stack: 1 2 3 4 5 6 7 8 Stack: 1 2 3 4 5 6 7 8 9
Análisis de Complejidad:
- Complejidad de tiempo: O(n)
- Complejidad espacial: O(n)
Publicación traducida automáticamente
Artículo escrito por shubham_rana_77 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA