Dadas dos pilas S1 y S2 , la tarea es verificar si ambas pilas son iguales o no en el mismo orden sin perder las pilas originales. Si ambas pilas son iguales, imprima «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: S1 = {3, 4, 2, 1}, S2 = {3, 4, 2, 1}
Salida: SíEntrada: S1 = {3, 4, 6}, S2 = {7, 2, 1}
Salida: No
Enfoque: El problema dado se puede resolver moviendo cierta cantidad de elementos entre las dos pilas dadas para verificar cada elemento correspondiente en las dos pilas. Siga los pasos a continuación para resolver el problema:
- Almacene el tamaño de la pila S1 y S2 , en una variable N y M respectivamente.
- Si N no es igual a M , imprima “ No ” y regrese.
- Iterar sobre el rango [1, N] y realizar las siguientes operaciones:
- Empuje los elementos superiores (N – i) de la pila S1 a la pila S2 .
- Ahora, almacene el elemento superior de la pila S1 en una variable, digamos val .
- Ahora, empuje los 2 * (N – i) elementos superiores de la pila S2 a la pila S1 .
- Si el valor de val no es igual al valor superior de la pila S2 , imprima » No » y regrese.
- De lo contrario, restaure las pilas empujando los elementos superiores (N – i) de la pila S1 a la pila S2 .
- Después de completar los pasos anteriores, si ninguno de los casos anteriores satisface, imprima » Sí «.
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;
// Function to push the elements from
// one stack element into another stack
void pushElements(stack<int> s1, stack<int> s2, int len)
{
int i = 1;
while (i <= len) {
// Update the stack
if (s1.size() > 0) {
s2.push(s1.top());
s1.pop();
}
// Increment i
i++;
}
}
// Function to compare two given stacks
string compareStacks(stack<int> s1, stack<int> s2)
{
// Stores the size of S1 stack
int N = s1.size();
// Stores the size of S2 stack
int M = s2.size();
// If N is not equal to M
if (N != M) {
return "No";
}
// Traverse the range [1, N]
for (int i = 1; i <= N; i++) {
// Push N-i elements to stack
// S2 from stack S1
pushElements(s1, s2, N - i);
// Stores the top value of S1
int val = s1.top();
// Pushes the 2 * (N-i)
// elements from S2 to S1
pushElements(s2, s1, 2 * (N - i));
// If val is not equal
// to the top of S2
if (val != s2.top())
return "No";
// Restores the stacks
pushElements(s1, s2, N - i);
}
// Return
return "Yes";
}
// Driver Code
int main()
{
stack<int> S1, S2;
S1.push(1);
S1.push(2);
S1.push(4);
S1.push(3);
S2.push(1);
S2.push(2);
S2.push(4);
S2.push(3);
cout << (compareStacks(S1, S2));
}
// This code is contributed by ukassp.
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to compare two given stacks
static String compareStacks(
Stack<Integer> s1,
Stack<Integer> s2)
{
// Stores the size of S1 stack
int N = s1.size();
// Stores the size of S2 stack
int M = s2.size();
// If N is not equal to M
if (N != M) {
return "No";
}
// Traverse the range [1, N]
for (int i = 1; i <= N; i++) {
// Push N-i elements to stack
// S2 from stack S1
pushElements(s1, s2, N - i);
// Stores the top value of S1
int val = s1.peek();
// Pushes the 2 * (N-i)
// elements from S2 to S1
pushElements(s2, s1, 2 * (N - i));
// If val is not equal
// to the top of S2
if (val != s2.peek())
return "No";
// Restores the stacks
pushElements(s1, s2, N - i);
}
// Return
return "Yes";
}
// Function to push the elements from
// one stack element into another stack
static void pushElements(
Stack<Integer> s1, Stack<Integer> s2,
int len)
{
int i = 1;
while (i <= len) {
// Update the stack
s2.push(s1.pop());
// Increment i
i++;
}
}
// Driver Code
public static void main(String[] args)
{
Stack<Integer> S1 = new Stack<>();
Stack<Integer> S2 = new Stack<>();
S1.push(1);
S1.push(2);
S1.push(4);
S1.push(3);
S2.push(1);
S2.push(2);
S2.push(4);
S2.push(3);
System.out.println(
compareStacks(S1, S2));
}
}
Python3
# Python3 program for the above approach # Function to compare two given stacks def compareStacks(s1, s2): # Stores the size of S1 stack N = len(s1) # Stores the size of S2 stack M = len(s2) # If N is not equal to M if (N != M): return "No" # Traverse the range [1, N] for i in range(1, N + 1): # Push N-i elements to stack # S2 from stack S1 pushElements(s1, s2, N - i) # Stores the top value of S1 val = s1[-1] # Pushes the 2 * (N-i) # elements from S2 to S1 pushElements(s2, s1, 2 * (N - i)) # If val is not equal # to the top of S2 if (val != s2[-1]): return "No" # Restores the stacks pushElements(s1, s2, N - i) # Return return "Yes" # Function to push the elements from # one stack element into another stack def pushElements(s1, s2, len): i = 1 while (i <= len): # Update the stack s2.append(s1[-1]) del s1[-1] # Increment i i += 1 # Driver Code if __name__ == '__main__': S1 = [] S2 = [] S1.append(1) S1.append(2) S1.append(4) S1.append(3) S2.append(1) S2.append(2) S2.append(4) S2.append(3) print(compareStacks(S1, S2)) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG {
// Function to compare two given stacks
static String compareStacks(
Stack<int> s1,
Stack<int> s2)
{
// Stores the size of S1 stack
int N = s1.Count;
// Stores the size of S2 stack
int M = s2.Count;
// If N is not equal to M
if (N != M) {
return "No";
}
// Traverse the range [1, N]
for (int i = 1; i <= N; i++) {
// Push N-i elements to stack
// S2 from stack S1
pushElements(s1, s2, N - i);
// Stores the top value of S1
int val = s1.Peek();
// Pushes the 2 * (N-i)
// elements from S2 to S1
pushElements(s2, s1, 2 * (N - i));
// If val is not equal
// to the top of S2
if (val != s2.Peek())
return "No";
// Restores the stacks
pushElements(s1, s2, N - i);
}
// Return
return "Yes";
}
// Function to push the elements from
// one stack element into another stack
static void pushElements(
Stack<int> s1, Stack<int> s2,
int len)
{
int i = 1;
while (i <= len) {
// Update the stack
s2.Push(s1.Pop());
// Increment i
i++;
}
}
// Driver Code
public static void Main(String[] args)
{
Stack<int> S1 = new Stack<int>();
Stack<int> S2 = new Stack<int>();
S1.Push(1);
S1.Push(2);
S1.Push(4);
S1.Push(3);
S2.Push(1);
S2.Push(2);
S2.Push(4);
S2.Push(3);
Console.WriteLine(
compareStacks(S1, S2));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program for the above approach
// Function to push the elements from
// one stack element into another stack
function pushElements(s1, s2, len)
{
var i = 1;
while (i <= len) {
// Update the stack
if (s1.length > 0) {
s2.push(s1[s1.length-1]);
s1.pop();
}
// Increment i
i++;
}
}
// Function to compare two given stacks
function compareStacks(s1, s2)
{
// Stores the size of S1 stack
var N = s1.length;
// Stores the size of S2 stack
var M = s2.length;
// If N is not equal to M
if (N != M) {
return "No";
}
// Traverse the range [1, N]
for (var i = 1; i <= N; i++) {
// Push N-i elements to stack
// S2 from stack S1
pushElements(s1, s2, N - i);
// Stores the top value of S1
var val = s1[s1.length-1];
// Pushes the 2 * (N-i)
// elements from S2 to S1
pushElements(s2, s1, 2 * (N - i));
// If val is not equal
// to the top of S2
if (val != s2[s2.length-1])
return "No";
// Restores the stacks
pushElements(s1, s2, N - i);
}
// Return
return "Yes";
}
// Driver Code
var S1 = [], S2 = [];
S1.push(1);
S1.push(2);
S1.push(4);
S1.push(3);
S2.push(1);
S2.push(2);
S2.push(4);
S2.push(3);
document.write(compareStacks(S1, S2));
//This code is contributed by rutvik_56.
</script>
Producción:
Yes
Complejidad Temporal: O(N 2 )
Espacio Auxiliar: O(1), ya que no se ha tomado ningún espacio extra.