Stack Permutation Using Stack

Optimized Approach

The idea is to try to convert the input queue to the output queue using a stack, if we are able to do so then the queue is permutable otherwise not.

Follow the steps mentioned below to implement the approach:

Continuously pop elements from the input queue and check if it is equal to the top of output queue or not, if it is not equal to the top of output queue then we will push the element to stack.
Once we find an element in input queue such the top of input queue is equal to top of output queue, we will pop a single element from both input and output queues, and compare the top of stack and top of output queue now. If top of both stack and output queue are equal then pop element from both stack and output queue. If not equal, go to step 1.
Repeat above two steps until the input queue becomes empty. At the end if both of the input queue and stack are empty then the input queue is permutable otherwise not.

Below is the implementation of the above approach:

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>

Output

Yes

Time Complexity: O(N)
Auxiliary Space: O(N)

Stack Permutations (Check if an array is stack permutation of other)

A stack permutation is a permutation of objects in the given input queue which is done by transferring elements from the input queue to the output queue with the help of a stack and the built-in push and pop functions.

The rules are:

Only dequeue from the input queue.
Use inbuilt push, and pop functions in the single stack.
Stack and input queue must be empty at the end.
Only enqueue to the output queue.

There are a huge number of permutations possible using a stack for a single input queue.
Given two arrays, both of unique elements. One represents the input queue and the other represents the output queue. Our task is to check if the given output is possible through stack permutation.

Examples:

Input: arr1[] = [ 1, 2, 3 ] , arr2[] = [ 2, 1, 3 ]
Output: YES
Explanation:
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: arr1[] = [ 1, 2, 3 ] , arr2[] = [ 3, 1, 2 ]
Output: Not Possible

Tags:

#Combinatorial #DSA #Queue #Stack #Combinatorial #Queue #Stack