Cree una estructura de datos twoStacks que represente dos pilas. La implementación de twoStacks debe usar solo una array, es decir, ambas pilas deben usar la misma array para almacenar elementos.
Las siguientes funciones deben ser compatibles con twoStacks .
- push1(int x) –> empuja x a la primera pila
- push2(int x) –> empuja x a la segunda pila
- pop1() –> saca un elemento de la primera pila y devuelve el elemento sacado
- pop2() –> saca un elemento de la segunda pila y devuelve el elemento sacado
La implementación de twoStack debería ser eficiente en cuanto al espacio.
Método 1 (Dividir el espacio en dos mitades):
Una forma sencilla de implementar dos pilas es dividir la array en dos mitades y asignar la mitad del espacio a dos pilas, es decir, usar arr[0] a arr[n/2] para stack1 y arr[(n/2) + 1] a arr[n-1] para stack2 donde arr[] es la array que se usará para implementar dos pilas y el tamaño de la array será n.
El problema con este método es el uso ineficiente del espacio de la array. Una operación de inserción de pila puede provocar un desbordamiento de pila incluso si hay espacio disponible en arr[]. Por ejemplo, digamos que el tamaño de la array es 6 y empujamos 3 elementos a la pila 1 y no empujamos nada a la segunda pila 2. Cuando empujamos el cuarto elemento a la pila 1, habrá un desbordamiento incluso si tenemos espacio para 3 elementos más en la array.
C++
#include <iostream>
#include <stdlib.h>
using namespace std;
class twoStacks {
int* arr;
int size;
int top1, top2;
public:
// Constructor
twoStacks(int n)
{
size = n;
arr = new int[n];
top1 = n / 2 + 1;
top2 = n / 2;
}
// Method to push an element x to stack1
void push1(int x)
{
// There is at least one empty
// space for new element
if (top1 > 0) {
top1--;
arr[top1] = x;
}
else {
cout << "Stack Overflow"
<< " By element :" << x << endl;
return;
}
}
// Method to push an element
// x to stack2
void push2(int x)
{
// There is at least one empty
// space for new element
if (top2 < size - 1) {
top2++;
arr[top2] = x;
}
else {
cout << "Stack Overflow"
<< " By element :" << x << endl;
return;
}
}
// Method to pop an element from first stack
int pop1()
{
if (top1 <= size / 2) {
int x = arr[top1];
top1++;
return x;
}
else {
cout << "Stack UnderFlow";
exit(1);
}
}
// Method to pop an element
// from second stack
int pop2()
{
if (top2 >= size / 2 + 1) {
int x = arr[top2];
top2--;
return x;
}
else {
cout << "Stack UnderFlow";
exit(1);
}
}
};
/* Driver program to test twoStacks class */
int main()
{
twoStacks ts(5);
ts.push1(5);
ts.push2(10);
ts.push2(15);
ts.push1(11);
ts.push2(7);
cout << "Popped element from stack1 is "
<< " : " << ts.pop1()
<< endl;
ts.push2(40);
cout << "\nPopped element from stack2 is "
<< ": " << ts.pop2()
<< endl;
return 0;
}
Java
import java.util.*;
class twoStacks
{
int[] arr;
int size;
int top1, top2;
// Constructor
twoStacks(int n)
{
size = n;
arr = new int[n];
top1 = n / 2 + 1;
top2 = n / 2;
}
// Method to push an element x to stack1
void push1(int x)
{
// There is at least one empty
// space for new element
if (top1 > 0)
{
top1--;
arr[top1] = x;
}
else
{
System.out.print("Stack Overflow"
+ " By element :" + x +"\n");
return;
}
}
// Method to push an element
// x to stack2
void push2(int x)
{
// There is at least one empty
// space for new element
if (top2 < size - 1)
{
top2++;
arr[top2] = x;
}
else
{
System.out.print("Stack Overflow"
+ " By element :" + x +"\n");
return;
}
}
// Method to pop an element from first stack
int pop1()
{
if (top1 <= size / 2)
{
int x = arr[top1];
top1++;
return x;
}
else
{
System.out.print("Stack UnderFlow");
System.exit(1);
}
return 0;
}
// Method to pop an element
// from second stack
int pop2()
{
if (top2 >= size / 2 + 1)
{
int x = arr[top2];
top2--;
return x;
}
else
{
System.out.print("Stack UnderFlow");
System.exit(1);
}
return 1;
}
};
class GFG
{
/* Driver program to test twoStacks class */
public static void main(String[] args)
{
twoStacks ts = new twoStacks(5);
ts.push1(5);
ts.push2(10);
ts.push2(15);
ts.push1(11);
ts.push2(7);
System.out.print("Popped element from stack1 is "
+ " : " + ts.pop1() +"\n");
ts.push2(40);
System.out.print("Popped element from stack2 is "
+ ": " + ts.pop2()
+"\n");
}
}
// This code is contributed by aashish1995
Python3
# Python Script to Implement two stacks in a list
import math
class twoStacks:
def __init__(self, n): # constructor
self.size = n
self.arr = [None] * n
self.top1 = math.floor(n/2) + 1
self.top2 = math.floor(n/2)
# Method to push an element x to stack1
def push1(self, x):
# There is at least one empty space for new element
if self.top1 > 0:
self.top1 = self.top1 - 1
self.arr[self.top1] = x
else:
print("Stack Overflow by element : ", x)
# Method to push an element x to stack2
def push2(self, x):
# There is at least one empty space for new element
if self.top2 < self.size - 1:
self.top2 = self.top2 + 1
self.arr[self.top2] = x
else :
print("Stack Overflow by element : ", x)
# Method to pop an element from first stack
def pop1(self):
if self.top1 <= self.size/2:
x = self.arr[self.top1]
self.top1 = self.top1 +1
return x
else:
print("Stack Underflow ")
exit(1)
# Method to pop an element from second stack
def pop2(self):
if self.top2 >= math.floor(self.size/2) + 1:
x = self.arr[self.top2]
self.top2 = self.top2 - 1
return x
else:
print("Stack Underflow ")
exit(1)
# Driver program to test twoStacks class
ts = twoStacks(5)
ts.push1(5)
ts.push2(10)
ts.push2(15)
ts.push1(11)
ts.push2(7)
print("Popped element from stack1 is : " + str(ts.pop1()))
ts.push2(40)
print("Popped element from stack2 is : " + str(ts.pop2()))
# This code is contributed by Gautam goel
C#
using System;
using System.Collections.Generic;
public class twoStacks {
public int[] arr;
public int size;
public int top1, top2;
// Constructor
public twoStacks(int n)
{
size = n;
arr = new int[n];
top1 = n / 2 + 1;
top2 = n / 2;
}
// Method to push an element x to stack1
public void push1(int x)
{
// There is at least one empty
// space for new element
if (top1 > 0) {
top1--;
arr[top1] = x;
}
else {
Console.Write("Stack Overflow"
+ " By element :" + x + "\n");
return;
}
}
// Method to push an element
// x to stack2
public void push2(int x)
{
// There is at least one empty
// space for new element
if (top2 < size - 1) {
top2++;
arr[top2] = x;
}
else {
Console.Write("Stack Overflow"
+ " By element :" + x + "\n");
return;
}
}
// Method to pop an element from first stack
public int pop1()
{
if (top1 <= size / 2) {
int x = arr[top1];
top1++;
return x;
}
else {
Console.Write("Stack UnderFlow");
}
return 0;
}
// Method to pop an element
// from second stack
public int pop2()
{
if (top2 >= size / 2 + 1) {
int x = arr[top2];
top2--;
return x;
}
else {
Console.Write("Stack UnderFlow");
}
return 1;
}
};
public class GFG {
/* Driver program to test twoStacks class */
public static void Main(String[] args)
{
twoStacks ts = new twoStacks(5);
ts.push1(5);
ts.push2(10);
ts.push2(15);
ts.push1(11);
ts.push2(7);
Console.Write("Popped element from stack1 is "
+ " : " + ts.pop1() + "\n");
ts.push2(40);
Console.Write("Popped element from stack2 is "
+ ": " + ts.pop2() + "\n");
}
}
// This code is contributed by umadevi9616
Javascript
<script>
class twoStacks
{
// Constructor
constructor(n)
{
this.arr = new Array(n);
this.size = n;
this.top1 = Math.floor(n / 2) + 1;
this.top2 = Math.floor(n / 2);
}
// Method to push an element x to stack1
push1(x)
{
// There is at least one empty
// space for new element
if (this.top1 > 0)
{
this.top1--;
this.arr[this.top1] = x;
}
else
{
document.write("Stack Overflow"
+ " By element :" + x +"<br>");
return;
}
}
// Method to push an element
// x to stack2
push2(x)
{
// There is at least one empty
// space for new element
if (this.top2 < this.size - 1)
{
this.top2++;
this.arr[this.top2] = x;
}
else
{
document.write("Stack Overflow"
+ " By element :" + x +"<br>");
return;
}
}
// Method to pop an element from first stack
pop1()
{
if (this.top1 <= this.size / 2)
{
let x = this.arr[this.top1];
this.top1++;
return x;
}
else
{
document.write("Stack UnderFlow");
}
return 0;
}
// Method to pop an element
// from second stack
pop2()
{
if (this.top2 >= Math.floor(this.size / 2) + 1)
{
let x = this.arr[this.top2];
this.top2--;
return x;
}
else
{
document.write("Stack UnderFlow");
}
return 1;
}
}
/* Driver program to test twoStacks class */
let ts = new twoStacks(5);
ts.push1(5);
ts.push2(10);
ts.push2(15);
ts.push1(11);
ts.push2(7);
document.write("Popped element from stack1 is "
+ " : " + ts.pop1() +"<br>");
ts.push2(40);
document.write("Popped element from stack2 is "
+ ": " + ts.pop2()
+"<br>");
// This code is contributed by avanitrachhadiya2155
</script>
Producción
Stack Overflow By element :7 Popped element from stack1 is : 11 Stack Overflow By element :40 Popped element from stack2 is : 15
Análisis de Complejidad:
- Complejidad del tiempo:
- Operación de empuje: O(1)
- Operación pop : O(1)
- Espacio Auxiliar: O(N).
Uso de array para implementar stack so. No es el método optimizado para el espacio como se explicó anteriormente.
Método 2 (una implementación eficiente en el espacio) :
Este método utiliza eficientemente el espacio disponible. No provoca un desbordamiento si hay espacio disponible en arr[]. La idea es comenzar dos pilas desde dos esquinas extremas de arr[]. stack1 comienza desde el elemento más a la izquierda, el primer elemento en stack1 se empuja en el índice 0. Stack2 comienza desde la esquina más a la derecha, el primer elemento en stack2 se empuja en el índice (n-1). Ambas pilas crecen (o se encogen) en dirección opuesta. Para verificar el desbordamiento, todo lo que necesitamos verificar es el espacio entre los elementos superiores de ambas pilas. Esta verificación se resalta en el siguiente código.
C++
#include <iostream>
#include <stdlib.h>
using namespace std;
class twoStacks {
int* arr;
int size;
int top1, top2;
public:
twoStacks(int n) // constructor
{
size = n;
arr = new int[n];
top1 = -1;
top2 = size;
}
// Method to push an element x to stack1
void push1(int x)
{
// There is at least one empty space for new element
if (top1 < top2 - 1) {
top1++;
arr[top1] = x;
}
else {
cout << "Stack Overflow";
exit(1);
}
}
// Method to push an element x to stack2
void push2(int x)
{
// There is at least one empty
// space for new element
if (top1 < top2 - 1) {
top2--;
arr[top2] = x;
}
else {
cout << "Stack Overflow";
exit(1);
}
}
// Method to pop an element from first stack
int pop1()
{
if (top1 >= 0) {
int x = arr[top1];
top1--;
return x;
}
else {
cout << "Stack UnderFlow";
exit(1);
}
}
// Method to pop an element from second stack
int pop2()
{
if (top2 < size) {
int x = arr[top2];
top2++;
return x;
}
else {
cout << "Stack UnderFlow";
exit(1);
}
}
};
/* Driver program to test twoStacks class */
int main()
{
twoStacks ts(5);
ts.push1(5);
ts.push2(10);
ts.push2(15);
ts.push1(11);
ts.push2(7);
cout << "Popped element from stack1 is "
<< ts.pop1();
ts.push2(40);
cout << "\nPopped element from stack2 is "
<< ts.pop2();
return 0;
}
Java
// Java program to implement two stacks in a
// single array
class TwoStacks {
int size;
int top1, top2;
int arr[];
// Constructor
TwoStacks(int n)
{
arr = new int[n];
size = n;
top1 = -1;
top2 = size;
}
// Method to push an element x to stack1
void push1(int x)
{
// There is at least one empty space for
// new element
if (top1 < top2 - 1) {
top1++;
arr[top1] = x;
}
else {
System.out.println("Stack Overflow");
System.exit(1);
}
}
// Method to push an element x to stack2
void push2(int x)
{
// There is at least one empty space for
// new element
if (top1 < top2 - 1) {
top2--;
arr[top2] = x;
}
else {
System.out.println("Stack Overflow");
System.exit(1);
}
}
// Method to pop an element from first stack
int pop1()
{
if (top1 >= 0) {
int x = arr[top1];
top1--;
return x;
}
else {
System.out.println("Stack Underflow");
System.exit(1);
}
return 0;
}
// Method to pop an element from second stack
int pop2()
{
if (top2 < size) {
int x = arr[top2];
top2++;
return x;
}
else {
System.out.println("Stack Underflow");
System.exit(1);
}
return 0;
}
// Driver program to test twoStack class
public static void main(String args[])
{
TwoStacks ts = new TwoStacks(5);
ts.push1(5);
ts.push2(10);
ts.push2(15);
ts.push1(11);
ts.push2(7);
System.out.println("Popped element from"
+ " stack1 is " + ts.pop1());
ts.push2(40);
System.out.println("Popped element from"
+ " stack2 is " + ts.pop2());
}
}
// This code has been contributed by
// Amit Khandelwal(Amit Khandelwal 1).
Python
# Python Script to Implement two stacks in a list
class twoStacks:
def __init__(self, n): # constructor
self.size = n
self.arr = [None] * n
self.top1 = -1
self.top2 = self.size
# Method to push an element x to stack1
def push1(self, x):
# There is at least one empty space for new element
if self.top1 < self.top2 - 1 :
self.top1 = self.top1 + 1
self.arr[self.top1] = x
else:
print("Stack Overflow ")
exit(1)
# Method to push an element x to stack2
def push2(self, x):
# There is at least one empty space for new element
if self.top1 < self.top2 - 1:
self.top2 = self.top2 - 1
self.arr[self.top2] = x
else:
print("Stack Overflow ")
exit(1)
# Method to pop an element from first stack
def pop1(self):
if self.top1 >= 0:
x = self.arr[self.top1]
self.top1 = self.top1 -1
return x
else:
print("Stack Underflow ")
exit(1)
# Method to pop an element from second stack
def pop2(self):
if self.top2 < self.size:
x = self.arr[self.top2]
self.top2 = self.top2 + 1
return x
else:
print("Stack Underflow ")
exit()
# Driver program to test twoStacks class
ts = twoStacks(5)
ts.push1(5)
ts.push2(10)
ts.push2(15)
ts.push1(11)
ts.push2(7)
print("Popped element from stack1 is " + str(ts.pop1()))
ts.push2(40)
print("Popped element from stack2 is " + str(ts.pop2()))
# This code is contributed by Sunny Karira
C#
// C# program to implement two
// stacks in a single array
using System;
public class TwoStacks {
public int size;
public int top1, top2;
public int[] arr;
// Constructor
public TwoStacks(int n)
{
arr = new int[n];
size = n;
top1 = -1;
top2 = size;
}
// Method to push an element x to stack1
public virtual void push1(int x)
{
// There is at least one empty
// space for new element
if (top1 < top2 - 1) {
top1++;
arr[top1] = x;
}
else {
Console.WriteLine("Stack Overflow");
Environment.Exit(1);
}
}
// Method to push an element x to stack2
public virtual void push2(int x)
{
// There is at least one empty
// space for new element
if (top1 < top2 - 1) {
top2--;
arr[top2] = x;
}
else {
Console.WriteLine("Stack Overflow");
Environment.Exit(1);
}
}
// Method to pop an element
// from first stack
public virtual int pop1()
{
if (top1 >= 0) {
int x = arr[top1];
top1--;
return x;
}
else {
Console.WriteLine("Stack Underflow");
Environment.Exit(1);
}
return 0;
}
// Method to pop an element
// from second stack
public virtual int pop2()
{
if (top2 < size) {
int x = arr[top2];
top2++;
return x;
}
else {
Console.WriteLine("Stack Underflow");
Environment.Exit(1);
}
return 0;
}
// Driver Code
public static void Main(string[] args)
{
TwoStacks ts = new TwoStacks(5);
ts.push1(5);
ts.push2(10);
ts.push2(15);
ts.push1(11);
ts.push2(7);
Console.WriteLine("Popped element from"
+ " stack1 is " + ts.pop1());
ts.push2(40);
Console.WriteLine("Popped element from"
+ " stack2 is " + ts.pop2());
}
}
// This code is contributed by Shrikant13
PHP
<?php
// PHP program to implement two
// stacks in a single array
class twoStacks
{
private $arr;
private $size;
private $top1;
private $top2;
function __construct($n)
{
$this->size = $n;
$this->arr = array();
$this->top1 = -1;
$this->top2 = $this->size;
}
// Method to push an element x to stack1
function push1($x)
{
// There is at least one empty
// space for new element
if ($this->top1 < $this->top2 - 1)
{
$this->top1++;
$this->arr[$this->top1] = $x;
}
else
{
echo "Stack Overflow";
exit();
}
}
// Method to push an element x to stack2
function push2($x)
{
// There is at least one empty space
// for new element
if ($this->top1 < $this->top2 - 1)
{
$this->top2--;
$this->arr[$this->top2] = $x;
}
else
{
echo "Stack Overflow";
exit();
}
}
// Method to pop an element
// from first stack
function pop1()
{
if ($this->top1 >= 0 )
{
$x = $this->arr[$this->top1];
$this->top1--;
return $x;
}
else
{
echo "Stack UnderFlow";
exit();
}
}
// Method to pop an element from
// second stack
function pop2()
{
if ($this->top2 < $this->size)
{
$x = $this->arr[$this->top2];
$this->top2++;
return $x;
}
else
{
echo "Stack UnderFlow";
exit();
}
}
};
// Driver Code
$ts = new twoStacks(5);
$ts->push1(5);
$ts->push2(10);
$ts->push2(15);
$ts->push1(11);
$ts->push2(7);
echo "Popped element from stack1 is " .
$ts->pop1();
$ts->push2(40);
echo "\nPopped element from stack2 is " .
$ts->pop2();
// This code is contributed by
// rathbhupendra
?>
Javascript
<script>
// javascript program to implement two stacks in a
// single array
class TwoStacks {
// Constructor
constructor(n) {
this.arr = Array(n).fill(0);
this.size = n;
this.top1 = -1;
this.top2 = this.size;
}
// Method to push an element x to stack1
push1(x) {
// There is at least one empty space for
// new element
if (this.top1 < this.top2 - 1) {
this.top1++;
this.arr[this.top1] = x;
} else {
document.write("Stack Overflow");
System.exit(1);
}
}
// Method to push an element x to stack2
push2(x) {
// There is at least one empty space for
// new element
if (this.top1 < this.top2 - 1) {
this.top2--;
this.arr[this.top2] = x;
} else {
document.write("Stack Overflow");
System.exit(1);
}
}
// Method to pop an element from first stack
pop1() {
if (this.top1 >= 0) {
var x = this.arr[this.top1];
this.top1--;
return x;
} else {
document.write("Stack Underflow");
System.exit(1);
}
return 0;
}
// Method to pop an element from second stack
pop2() {
if (this.top2 < this.size) {
var x = this.arr[this.top2];
this.top2++;
return x;
} else {
document.write("Stack Underflow");
System.exit(1);
}
return 0;
}
// Driver program to test twoStack class
}
var ts = new TwoStacks(5);
ts.push1(5);
ts.push2(10);
ts.push2(15);
ts.push1(11);
ts.push2(7);
document.write("Popped element from" + " stack1 is " + ts.pop1());
ts.push2(40);
document.write("<br/>Popped element from" + " stack2 is " + ts.pop2());
// This code contributed by Rajput-Ji
</script>
Producción:
Popped element from stack1 is 11 Popped element from stack2 is 40
Análisis de Complejidad:
- Complejidad del tiempo:
- Operación de empuje: O(1)
- Operación pop : O(1)
- Espacio Auxiliar : O(N).
Uso de array para implementar la pila, por lo que es un método optimizado para el espacio.
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