Stack Permutations (Check if an Array is Stack Permutation of Another)

Last Updated on October 10, 2022 by Gokul Kannan

Problem Statement:

You will be given 2 arrays. You have to tell whether the 2 arrays are stack permutations of each other or not.

Basically, there will be 2 input arrays. You have 2 consider the first array as the input array and the second as the output array. You have to treat the input array as a queue and only dequeue operation is possible in the input array. Assume that there is a stack in which push and pop operations are allowed. Now, you have to tell whether we can generate the second array (output array) from the first array by using the Stack.

Allowed Operations and Constraints

• Only dequeue from the input queue.
• Push and pop operations in a single stack.
• Only enqueue in the output queue.
• The stack and input queue must be empty at the end.

Example

Let us say the following are the two input arrays.

Here, the second array is a stack permutation of the first array.

So, we got the output list. Hence these two arrays are stack permutable.

Approach

Below is the algorithm that we will follow.

• Create an empty stack.
• We have to pop elements from the input queue (array) and check if it is equal to the top of the output queue. If the element is equal to the top of the output queue, we will push the element into the stack.
• If we find an element in the input queue that is equal to the top of the output queue, we will pop an element from both the input and output queues and compare the top of the stack with the top of both the queues. If the tops are equal, then pop an element from the stack and input queue. Else, repeat step 2.
• We have to repeat the above steps until the first array becomes empty. At the last, the stack and the queue should both be empty. Else, the arrays are not stack permutable.

Now that we have understood the algorithm, let us implement the above approach in a program.

Code Implementation

#include<bits/stdc++.h>
using namespace std;

bool checkStackPermutation(int ip[], int op[], int n)
{
	queue<int> input;
	for (int i=0;i<n;i++)
		input.push(ip[i]);

	queue<int> output;
	for (int i=0;i<n;i++)
		output.push(op[i]);

	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);
	}

	return (input.empty()&&tempStack.empty());
}
int main()
{

	int input[] = {1, 2, 3};

	int output[] = {2, 1, 3};

	int n = 3;

	if (checkStackPermutation(input, output, n))
		cout << "Yes";
	else
		cout << "Not Stack Permutable";
	return 0;
}

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class Gfg
{
	static boolean checkStackPermutation(int ip[],
									int op[], int n)
	{
		Queue<Integer> input = new LinkedList<>();

		for (int i = 0; i < n; i++)
		{
			input.add(ip[i]);
		}

		Queue<Integer> output = new LinkedList<>();
		for (int i = 0; i < n; i++)
		{
			output.add(op[i]);
		}

		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);
			}
		}
    	return (input.isEmpty() && tempStack.isEmpty());
	}
    
	public static void main(String[] args)
	{
		int input[] = { 1, 2, 3 };

		int output[] = { 2, 1, 3 };
		int n = 3;
		if (checkStackPermutation(input, output, n))
			System.out.println("Yes");
		else
			System.out.println("Not Stack Permutable");
	}
}

Time Complexity: The time complexity of the above approach is O(N) as we have to traverse the first list completely and empty it to fill the output list.

Space Complexity (Auxiliary Space): It is also O(N) as we have to use an array as well as an output array of size N.

We tried to discuss Stack Permutations. We hope this article gives you a better understanding of Stack Permutations, PrepBytes also provides a good collection of Foundation Courses that can help you enhance your coding skills. Want to make sure you ace the interview in one go? Join our Placement Program which will help you get prepared and land your dream job at MNCs. Mentors of Prepbytes are highly experienced and can provide you with basic, in-depth subject knowledge for better understanding.