Do you think IIT Guwahati certified course can help you in your career?
Introduction
This article will determine whether a queue can be sorted into another queue using a stack. A stack is a linear data structure in which elements can only be added or removed from the top side of the list. The LIFO (Last In First Out) principle dictates that the element placed last is the first to come out of a stack. Pushing an element into a stack is called a push operation while removing an element from a stack is referred to as a pop operation. With a pointer called top, we always maintain track of the final entry in the list in the stack.
A queue is a linear data structure that operates on first-in, first-out (FIFO). Queue supports Enqueue and dequeue activities. The advantage of utilising linked lists instead of arrays to create a queue is that it allows the Queue to grow as needed, i.e., memory may be allocated dynamically.
Problem Statement
The statement "Check if a queue can be sorted into another queue using a stack" implies that you are given a queue with n components, each of which is a permutation of numbers 1 to n. Examine whether this queue may be stacked and arranged in increasing order in any other queue.
1. Set the value of a variable next to 1 to indicate that it should be inserted into queue 2.
2. If next is equal to the front of queue 1 or the top of the stack, remove the front or top as needed and shift it to queue 2, incrementing next by 1.
3. If none of them is next, remove the front of queue 1 and push it to the stack; otherwise, return false if the front of queue 1 is greater than the top of the stack.
4. If all of the elements are present in queue 2, and both queue 1 and stack are empty, the queue can be sorted; return true.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
bool letscheckIt(queue<int> &theQ) {
stack<int> containstack;
// Next, set the value of a variable to 1.
int next = 1;
while (!theQ.empty() || !containstack.empty()) {
// If next is at the front of the queue, remove it and increment next.
if (!theQ.empty() && theQ.front() == next) {
theQ.pop();
next++;
}
// If next is at the top of the stack, delete it and increment next.
else if (!containstack.empty() && containstack.top() == next) {
containstack.pop();
next++;
} else {
// If q isn't filled in, return false.
if (theQ.empty()) {
return false;
}
// Remove the front of the queue and transfer it to the top of the stack
else {
int front = theQ.front();
theQ.pop();
if (containstack.empty()) {
containstack.push(front);
} else {
// Return false if the front of the queue is higher than the top of the stack.
if (front > containstack.top()) {
return false;
} else {
containstack.push(front);
}
}
}
}
}
return true;
}
int main() {
queue<int> takingInQ1;
takingInQ1.push(8);
takingInQ1.push(7);
takingInQ1.push(5);
takingInQ1.push(6);
takingInQ1.push(4);
takingInQ1.push(3);
takingInQ1.push(2);
takingInQ1.push(1);
if (letscheckIt(takingInQ1)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
queue<int> takingInQ2;
takingInQ2.push(4);
takingInQ2.push(1);
takingInQ2.push(2);
takingInQ2.push(3);
if (letscheckIt(takingInQ2)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
return 0;
}
Output
False
True
Implementation in java
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
class CheckIfAQueueCanBeSortedIntoAnotherQueueUsingAStack {
private static boolean letscheckIt(Queue<Integer> theQ) {
// Next, set the value to one.
int next = 1;
Stack<Integer> containstack = new Stack<>();
while (!theQ.isEmpty() || !containstack.isEmpty()) {
// If next is at the front of the queue, remove it and increment next.
if (!theQ.isEmpty() && theQ.peek() == next) {
theQ.poll();
next++;
}
// If next is at the top of the stack, delete it and increment next.
else if (!containstack.isEmpty() && containstack.peek() == next) {
containstack.pop();
next++;
} else {
// If q isn't filled in, return false. if (theQ.isEmpty()) {
return false;
}
// Remove the front of the queue and transfer it to the top of the stack else {
int front = theQ.poll();
if (containstack.isEmpty()) {
containstack.push(front);
} else {
// Return false if the front of the queue is higher than the top of the stack.
if (front > containstack.peek()) {
return false;
} else {
containstack.push(front);
}
}
}
}
}
return true;
}
public static void main(String[] args) {
Queue<Integer> takingInQ1 = new LinkedList<>();
takingInQ1.add(8);
takingInQ1.add(7);
takingInQ1.add(5);
takingInQ1.add(6);
takingInQ1.add(4);
takingInQ1.add(3);
takingInQ1.add(2);
takingInQ1.add(1);
System.out.println(letscheckIt(takingInQ1));
Queue<Integer> takingInQ2 = new LinkedList<>();
takingInQ2.add(4);
takingInQ2.add(1);
takingInQ2.add(2);
takingInQ2.add(3);
System.out.println(letscheckIt(takingInQ2));
}
}
Output
False
True
Complexity
Time Complexity:
O(n): Where ‘n’ stands for number of elements
Reason: As we traversed the entire input, the time complexity is O(N). The algorithm's time complexity is linear, where n is the size.
Space Complexity:
O(n): Where ‘n’ stands for number of elements.
Reason: Because the items are held in a queue or stack, the space complexity is O(N). The algorithm is linear in space, where n is the size.
Is it possible to use a stack to implement a queue?
We must consider two stacks in order to implement the Queue utilising Stack. There are two ways to use Stack to implement Queue: Increasing the cost of a dequeue operation. Making an en queue action more expensive.
Is it possible to implement a queue using a stack, and if so, how?
Two Stacks can be used to implement Queue. When two Stacks are combined, we can receive all of the operations supported by Queue. Using two stacks, you can achieve all of the queue's use-cases.
What is an example of FIFO?
Consider what would happen if a corporation bought 100 products for $10 each, then bought 100 more for $15 each. The firm then sold 60 goods. Because the first goods acquired are the first goods sold, the cost of goods sold for each of the 60 items is $10/unit using the FIFO technique.
What is the best way to tell if a programme uses a stack or queue data structure?
The main distinction between Stack and Queue Data Structures is that Stack uses a LIFO data structure, whereas Queue uses a FIFO data structure. The acronym LIFO stands for Last In First Out. It means that when we put data into a Stack, the final element is processed first. FIFO, on the other hand, stands for First In First Out.
Is it true that a linked list is LIFO?
The sequence in which elements are placed into LinkedList is preserved.
The LinkedList class can represent a first-in, first-out (FIFO) or last-in, first-out (LIFO) storage system.
Conclusion
This article has determined whether a queue can be sorted into another queue using a stack.
Want to learn more about the Data Structure in java? Click here.
Take a look at how theQueue is implemented. It will make the concept more obvious.
Are you preparing to ace product-based company interviews with Amazon, Google, Microsoft, and others?
Please take a look at ourcourseon operating systems.
130+ registered 
