Reverse First K Elmeents Of Queue Geeks For Geeks
Problem Link:
https://practice.geeksforgeeks.org/problems/reverse-first-k-elements-of-queue/1#
(It is also the problem of the day for 13 January.)
Solution 1:
Using LinkedList
class GfG {
// Function to reverse first k elements of a queue.
public Queue<Integer> modifyQueue(Queue<Integer> q, int k) {
int count=0;
//Queue<Integer>aa=new ArrayDeque<Integer>();
Queue<Integer>aa=new LinkedList<Integer>();
Stack<Integer>stack=new Stack<Integer>();
while(count<k){
++count;
stack.push(q.poll());
}
while(!stack.isEmpty()){
aa.add(stack.pop());
}
while(!q.isEmpty()){
aa.add(q.poll());
}
//Queue<Integer>
return aa;
}
}
TIME COMPLEXITY: O(Total Elements in q)[GFG Time:1.1/2.8]
SPACE COMPLEXITY: O(Total Elements in q)[Given is queue]
AUXILARY SPACE: O(Total Elements in q)[Here in the worst case the stack created will have all the elements of the queue if k=queue.size()]
TOTAL TEST CASES:121
=========================================================================
Solution 2:
Using ArrayDeque
class GfG {
// Function to reverse first k elements of a queue.
public Queue<Integer> modifyQueue(Queue<Integer> q, int k) {
int count=0;
Queue<Integer>aa=new ArrayDeque<Integer>();
//Queue<Integer>aa=new LinkedList<Integer>();
Stack<Integer>stack=new Stack<Integer>();
while(count<k){
++count;
stack.push(q.poll());
}
while(!stack.isEmpty()){
aa.add(stack.pop());
}
while(!q.isEmpty()){
aa.add(q.poll());
}
//Queue<Integer>
return aa;
}
}
TIME COMPLEXITY: O(Total Elements in q)[GFG Time:1/2.8]
SPACE COMPLEXITY: O(Total Elements in q)[Given is queue]
AUXILARY SPACE: O(Total Elements in q)[Here in the worst case the stack created will have all the elements of the queue if k=queue.size()]
TOTAL TEST CASES:121
-----------------------------------------------------------------------------------------------------------------------------
APPROACH USED:
Here we need to revere the first k elements, so for that, we will use the stack as it is based on LIFO while the queue is based on FIFO. So whatever elements from the top will be removed from the queue will be inserted at top of the stack.
Later in question after k elements we want the remaining elements to be in the same order as in the actual queue.
So for that, we can either go with LinkedList or ArrayList or queue itself.
The best data structure will be the queue. It is so because in the question itself they want to queue as returned output, so we can use queue now and return it later.
Which queue in the queue is implemented by linked list or by ArrayDeque?
Both will work fine. The difference is linked list is unidirectional while the array deque is bidirectional.
Both will preserver insertion order of elements.
Later first we add the stack element in the final queue as we want the first k elements to be in reverse order so after adding the stack element the final queue will have the reverse of the first k elements of actual given queue.
Later we will add the reaming elements simply by traversal.
Return the final queue.
"Thanks For Reading.😇"
"Share Further To Increase Knowledge Treasure.😊"
Comments
Post a Comment