Una permutación de pila es una permutación de objetos en la cola de entrada dada que se realiza mediante la transferencia de elementos de la cola de entrada a la cola de salida con la ayuda de una pila y las funciones incorporadas de inserción y extracción.
Las reglas bien definidas son:
- Quite solo de la cola de entrada.
- Utilice las funciones push, pop incorporadas en la pila única.
- La pila y la cola de entrada deben estar vacías al final.
- Solo encolar a la cola de salida.
Hay una gran cantidad de permutaciones posibles usando una pila para una sola cola de entrada.
Dadas dos arrays, ambas de elementos únicos. Uno representa la cola de entrada y el otro representa la cola de salida. Nuestra tarea es verificar si la salida dada es posible a través de la permutación de la pila.
Ejemplos:
Input : First array: 1, 2, 3
Second array: 2, 1, 3
Output : Yes
Procedure:
push 1 from input to stack
push 2 from input to stack
pop 2 from stack to output
pop 1 from stack to output
push 3 from input to stack
pop 3 from stack to output
Input : First array: 1, 2, 3
Second array: 3, 1, 2
Output : Not Possible
La idea para hacer esto es que intentaremos convertir la cola de entrada en cola de salida usando una pila, si podemos hacerlo, entonces la cola es permutable, de lo contrario no.
A continuación se muestra el algoritmo paso a paso para hacer esto :
- Extraiga continuamente elementos de la cola de entrada y verifique si es igual a la parte superior de la cola de salida o no, si no es igual a la parte superior de la cola de salida, empujaremos el elemento para apilarlo.
- Una vez que encontremos un elemento en la cola de entrada, de modo que la parte superior de la cola de entrada sea igual a la parte superior de la cola de salida, extraeremos un solo elemento de las colas de entrada y salida, y compararemos la parte superior de la pila y la parte superior de la cola de salida ahora. Si la parte superior de la pila y la cola de salida son iguales, extraiga el elemento tanto de la pila como de la cola de salida. Si no es igual, vaya al paso 1.
- Repita los dos pasos anteriores hasta que la cola de entrada se vacíe. Al final, si tanto la cola de entrada como la pila están vacías, la cola de entrada es permutable; de lo contrario, no.
A continuación se muestra la implementación de la idea anterior:
C++
// Given two arrays, check if one array is
// stack permutation of other.
#include<bits/stdc++.h>
using namespace std;
// function to check if input queue is
// permutable to output queue
bool checkStackPermutation(int ip[], int op[], int n)
{
// Input queue
queue<int> input;
for (int i=0;i<n;i++)
input.push(ip[i]);
// output queue
queue<int> output;
for (int i=0;i<n;i++)
output.push(op[i]);
// stack to be used for permutation
stack <int> tempStack;
while (!input.empty())
{
int ele = input.front();
input.pop();
if (ele == output.front())
{
output.pop();
while (!tempStack.empty())
{
if (tempStack.top() == output.front())
{
tempStack.pop();
output.pop();
}
else
break;
}
}
else
tempStack.push(ele);
}
// If after processing, both input queue and
// stack are empty then the input queue is
// permutable otherwise not.
return (input.empty()&&tempStack.empty());
}
// Driver program to test above function
int main()
{
// Input Queue
int input[] = {1, 2, 3};
// Output Queue
int output[] = {2, 1, 3};
int n = 3;
if (checkStackPermutation(input, output, n))
cout << "Yes";
else
cout << "Not Possible";
return 0;
}
Java
// Given two arrays, check if one array is
// stack permutation of other.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
class Gfg
{
// function to check if input queue is
// permutable to output queue
static boolean checkStackPermutation(int ip[],
int op[], int n)
{
Queue<Integer> input = new LinkedList<>();
// Input queue
for (int i = 0; i < n; i++)
{
input.add(ip[i]);
}
// Output queue
Queue<Integer> output = new LinkedList<>();
for (int i = 0; i < n; i++)
{
output.add(op[i]);
}
// stack to be used for permutation
Stack<Integer> tempStack = new Stack<>();
while (!input.isEmpty())
{
int ele = input.poll();
if (ele == output.peek())
{
output.poll();
while (!tempStack.isEmpty())
{
if (tempStack.peek() == output.peek())
{
tempStack.pop();
output.poll();
}
else
break;
}
}
else
{
tempStack.push(ele);
}
}
// If after processing, both input queue and
// stack are empty then the input queue is
// permutable otherwise not.
return (input.isEmpty() && tempStack.isEmpty());
}
// Driver code
public static void main(String[] args)
{
// Input Queue
int input[] = { 1, 2, 3 };
// Output Queue
int output[] = { 2, 1, 3 };
int n = 3;
if (checkStackPermutation(input, output, n))
System.out.println("Yes");
else
System.out.println("Not Possible");
}
}
// This code is contributed by Vivekkumar Singh
Python3
# Given two arrays, check if one array is
# stack permutation of other.
from queue import Queue
# function to check if Input queue
# is permutable to output queue
def checkStackPermutation(ip, op, n):
# Input queue
Input = Queue()
for i in range(n):
Input.put(ip[i])
# output queue
output = Queue()
for i in range(n):
output.put(op[i])
# stack to be used for permutation
tempStack = []
while (not Input.empty()):
ele = Input.queue[0]
Input.get()
if (ele == output.queue[0]):
output.get()
while (len(tempStack) != 0):
if (tempStack[-1] == output.queue[0]):
tempStack.pop()
output.get()
else:
break
else:
tempStack.append(ele)
# If after processing, both Input
# queue and stack are empty then
# the Input queue is permutable
# otherwise not.
return (Input.empty() and
len(tempStack) == 0)
# Driver Code
if __name__ == '__main__':
# Input Queue
Input = [1, 2, 3]
# Output Queue
output = [2, 1, 3]
n = 3
if (checkStackPermutation(Input,
output, n)):
print("Yes")
else:
print("Not Possible")
# This code is contributed by PranchalK
C#
// Given two arrays, check if one array is
// stack permutation of other.
using System;
using System.Collections.Generic;
class GFG
{
// function to check if input queue is
// permutable to output queue
static bool checkStackPermutation(int []ip,
int []op, int n)
{
Queue<int> input = new Queue<int>();
// Input queue
for (int i = 0; i < n; i++)
{
input.Enqueue(ip[i]);
}
// Output queue
Queue<int> output = new Queue<int>();
for (int i = 0; i < n; i++)
{
output.Enqueue(op[i]);
}
// stack to be used for permutation
Stack<int> tempStack = new Stack<int>();
while (input.Count != 0)
{
int ele = input.Dequeue();
if (ele == output.Peek())
{
output.Dequeue();
while (tempStack.Count != 0)
{
if (tempStack.Peek() == output.Peek())
{
tempStack.Pop();
output.Dequeue();
}
else
break;
}
}
else
{
tempStack.Push(ele);
}
}
// If after processing, both input queue and
// stack are empty then the input queue is
// permutable otherwise not.
return (input.Count == 0 && tempStack.Count == 0);
}
// Driver code
public static void Main(String[] args)
{
// Input Queue
int []input = { 1, 2, 3 };
// Output Queue
int []output = { 2, 1, 3 };
int n = 3;
if (checkStackPermutation(input, output, n))
Console.WriteLine("Yes");
else
Console.WriteLine("Not Possible");
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Given two arrays, check if one array is
// stack permutation of other.
// function to check if input queue is
// permutable to output queue
function checkStackPermutation(ip, op, n)
{
let input = [];
// Input queue
for (let i = 0; i < n; i++)
{
input.push(ip[i]);
}
// Output queue
let output = [];
for (let i = 0; i < n; i++)
{
output.push(op[i]);
}
// stack to be used for permutation
let tempStack = [];
while (input.length != 0)
{
let ele = input.shift();
if (ele == output[0])
{
output.shift();
while (tempStack.length != 0)
{
if (tempStack[tempStack.length - 1] == output[0])
{
tempStack.pop();
output.shift();
}
else
break;
}
}
else
{
tempStack.push(ele);
}
}
// If after processing, both input queue and
// stack are empty then the input queue is
// permutable otherwise not.
return (input.length == 0 && tempStack.length == 0);
}
// Input Queue
let input = [ 1, 2, 3 ];
// Output Queue
let output = [ 2, 1, 3 ];
let n = 3;
if (checkStackPermutation(input, output, n))
document.write("Yes");
else
document.write("Not Possible");
// This code is contributed by rameshtravel07.
</script>
Producción
Yes
Otro enfoque: –
Idea: comenzaremos a iterar en la array de entrada y almacenaremos su elemento uno por uno en una pila y si la parte superior de nuestra pila coincide con un elemento en la array de salida, sacaremos ese elemento de la pila y compararemos el siguiente elemento de la array de salida con la parte superior de nuestra apilar si nuevamente coincide, luego nuevamente pop hasta que nuestra pila no esté vacía
Implementación:
C++
// Given two arrays, check if one array is
// stack permutation of other.
#include<bits/stdc++.h>
using namespace std;
// function to check if input array is
// permutable to output array
bool checkStackPermutation(int ip[], int op[], int n)
{
// we will be pushing elements from input array to stack uptill top of our stack
// matches with first element of output array
stack<int>s;
// will maintain a variable j to iterate on output array
int j=0;
// will iterate one by one in input array
for(int i=0;i<n;i++)
{
// pushed an element from input array to stack
s.push(ip[i]);
// if our stack isn't empty and top matches with output array
// then we will keep popping out from stack uptill top matches with
// output array
while(!s.empty() and s.top()==op[j])
{
s.pop();
// increasing j so next time we can compare next element in output array
j++;
}
}
// if output array was a correct permutation of input array then
// by now our stack should be empty
if(s.empty())
{
return true;
}
return false;
}
// Driver program to test above function
int main()
{
// Input Array
int input[] = {4,5,6,7,8};
// Output Array
int output[] = {8,7,6,5,4};
int n = 5;
if (checkStackPermutation(input, output, n))
cout << "Yes";
else
cout << "Not Possible";
return 0;
}
Java
// Java program to check if one array is
// stack permutation of other.
import java.util.Stack;
class Rextester {
// function to check if input array is
// permutable to output array
static Boolean checkStackPermutation(int ip[], int op[],
int n)
{
// we will be pushing elements from input array to
// stack uptill top of our stack matches with first
// element of output array
Stack<Integer> s = new Stack<Integer>();
// will maintain a variable j to iterate on output
// array
int j = 0;
// will iterate one by one in input array
for (int i = 0; i < n; i++) {
// pushed an element from input array to stack
s.push(ip[i]);
// if our stack isn't empty and top matches with
// output array then we will keep popping out
// from stack uptill top matches with output
// array
while (!s.isEmpty() && s.peek() == op[j]) {
s.pop();
// increasing j so next time we can compare
// next element in output array
j++;
}
}
// if output array was a correct permutation of
// input array then by now our stack should be empty
if (s.isEmpty()) {
return true;
}
return false;
}
// Driver program to test above function
public static void main(String args[])
{
// Input Array
int input[] = { 4, 5, 6, 7, 8 };
// Output Array
int output[] = { 8, 7, 6, 5, 4 };
int n = 5;
if (checkStackPermutation(input, output, n))
System.out.println("Yes");
else
System.out.println("Not Possible");
}
}
// This code is contributed by Lovely Jain
Python3
# Given two arrays, check if one array is
# stack permutation of other.
# function to check if input array is
# permutable to output array
def checkStackPermutation(ip, op, n):
# we will be appending elements from input array to stack uptill top of our stack
# matches with first element of output array
s = []
# will maintain a variable j to iterate on output array
j = 0
# will iterate one by one in input array
for i in range(n):
# appended an element from input array to stack
s.append(ip[i])
# if our stack isn't empty and top matches with output array
# then we will keep popping out from stack uptill top matches with
# output array
while(len(s) > 0 and s[- 1] == op[j]):
s.pop()
# increasing j so next time we can compare next element in output array
j += 1
# if output array was a correct permutation of input array then
# by now our stack should be empty
if(len(s) == 0):
return True
return False
# Driver program to test above function
# Input Array
input = [4,5,6,7,8]
# Output Array
output = [8,7,6,5,4]
n = 5
if (checkStackPermutation(input, output, n)):
print("Yes")
else:
print("Not Possible")
# This code is contributed by shinjanpatra
Javascript
<script>
// Given two arrays, check if one array is
// stack permutation of other.
// function to check if input array is
// permutable to output array
function checkStackPermutation(ip, op, n)
{
// we will be pushing elements from input array to stack uptill top of our stack
// matches with first element of output array
let s = [];
// will maintain a variable j to iterate on output array
let j = 0;
// will iterate one by one in input array
for(let i = 0; i < n; i++)
{
// pushed an element from input array to stack
s.push(ip[i]);
// if our stack isn't empty and top matches with output array
// then we will keep popping out from stack uptill top matches with
// output array
while(s.length > 0 && s[s.length - 1] == op[j])
{
s.pop();
// increasing j so next time we can compare next element in output array
j++;
}
}
// if output array was a correct permutation of input array then
// by now our stack should be empty
if(s.length == 0)
{
return true;
}
return false;
}
// Driver program to test above function
// Input Array
let input = [4,5,6,7,8];
// Output Array
let output = [8,7,6,5,4];
let n = 5;
if (checkStackPermutation(input, output, n))
document.write("Yes");
else
document.write("Not Possible");
// This code is contributed by shinjanpatra
</script>
Producción
Yes
Complejidad de tiempo – O(N)
Complejidad de espacio – O(N)
Este artículo es una contribución de Suprotik Dey . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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