Solution Approach
The idea is simple; we will try to convert the input queue a[ ] to the output queue b[ ] using a stack. If we can do so, then the queue is permutable; otherwise, not.
Algorithm
- Create a function that accepts two integer arrays, a[ ] and b[ ], along with the size of the array as the parameters.
- After that, we will create a queue data structure of integer type.
- Traverse through the arrays and push/insert all the array elements a[ ] in the first queue and b[ ] in the second queue.
- Also, create an integer stack.
- Traverse until the size of the first queue is not 0. Create an integer variable and store the element at the front of the first queue, and pop it from the first queue.
- Check if the value in the integer variable is not equal to the element at the front of the second queue, and push/insert the integer variable in the Stack.
- Else pop the element at the front of the second queue.
- Traverse again while the size of the Stack is not 0. Check if the element at the top of the Stack is equal to the element at the front of the second queue, remove the element at the front of the second queue, and from the top of the Stack. Else break.
- Check if the Stack and first queue are empty. Print "Yes" or else print "No."
Java Code
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
class permutation
{
static boolean checkPermutation(int ip[], int op[], int n)
{
Queue<Integer> input = new LinkedList<>();
// Forming input queue
for (int i = 0; i < n; i++)
{
input.add(ip[i]);
}
// Forming output queue
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());
}
// 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 (checkPermutation(input, output, n))
System.out.println("Yes");
else
System.out.println("Not Possible");
}
}
You can also try this code with Online Java Compiler
Output:
Yes
C++ Code
#include<bits/stdc++.h>
using namespace std;
bool checkPermutation(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);
}
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 (checkPermutation(input, output, n))
cout << "Yes";
else
cout << "Not Possible";
return 0;
}
You can also try this code with Online C++ Compiler
Output :
Yes
Complexity Analysis
Time Complexity: O(N)
As we have only traversed the array elements of size n.
Space Complexity: O(N)
As we created two queues and stack which makes the algorithm to have linear complexity in space.
Check out this problem - Queue Implementation
Read about Application of Queue in Data Structure here.
Frequently Asked Questions
When would you use a stack in data structure?
Stack data structures are useful when the order of actions is important. They ensure that a system does not move onto a new action before completing those before.
What is the greedy approach?
It is an algorithm to get the optimal solution for the problem. In this algorithm, we always choose the next best solution that seems optimal at that step. We build solutions piece by piece to reach the optimal solution.
Stack is a recursive data structure. Why?
A stack is a recursive data structure; it's either empty or made up of a top and the remainder, a stack in and of itself.
Why are stacks useful?
They're helpful because they allow you to insert or remove data from the front of a data structure in constant time O(1) operations. A stack is commonly employed in compilers to ensure that all brackets and parentheses in a code file are balanced, that is, that they have an opening and closing counterpart. Mathematical expressions can also be evaluated using stacks.
How to Linked List using Stack?
Two stacks can be used to imitate a linked list. The "list" stack is one, while the "temporary storage" stack is the other.
- Push an item into the Stack to add it to the top.
- Pop the Stack from the head to remove it.
- To insert somewhere in the middle, pop items off the "list" Stack and place them on the temporary Stack until you reach your insertion point.
- Push the new item to the "list" Stack, remove it from the temporary Stack and re-add it to the "list" Stack. An arbitrary node can be deleted similarly.
Conclusion
In this blog, we talked about how to check if an array is stack permutation of other or not.
Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, Machine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problems, interview experiences, and interview bundle for placement preparations.
Recommended problems -
Recommended Articles: Permutation of string
Nevertheless, you may consider our paid courses to give your career an edge over others!
Do upvote our blogs if you find them helpful and engaging!
Happy Learning!!
568+ registered 
