Reverse First K Elements Of A Queue

Reverse First K Elements Of a Queue

Difficulty: Medium

Understanding The Problem

Problem Description

Given an integer k and queue Q of integers. Write a program to reverse the order of the first k elements of the queue. The other elements will be in the same relative order. The following standard operations are allowed on the queue:

enqueue(x) : Insert an item x to the rear of queue
dequeue() : Remove an item from the front of queue
size() : Returns the number of items in the queue.
peek() : Get the front item.
empty() : Return whether the queue is empty.

Example 1

Input: Q = [1, 2, 3, 4, 5]
       k = 5
Output: Q = [5, 4, 3, 2, 1]
Explanation: The first 5 elements of Q are reversed.

Example 2

Input: Q = [1, 2, 3, 4, 5, 6]
       k = 4
Output: Q = [4, 3, 2, 1, 5, 6]
Explanation: The first 4 elements of Q are reversed.

Solution

The problem asked us to reverse the first K elements of the queue and we can use the predefined operations given above. To reverse some segment of the queue, we can use an auxiliary stack (How?).

If we insert all the elements of the queue in a stack using the dequeue operation, then we will have a stack that will be seen reversed of the queue.

For example, If we have a queue of numbers sorted in ascending order, then inserting all elements of the queue into a stack one by one, then the top of the resultant stack will have the smallest element, i.e. the stack will be in descending order. We can use this concept here.

We will take an auxiliary empty stack. We will dequeue the first K elements of the queue and push them into the stack one by one. Now, we will pop all elements of the stack and enqueue into the queue one by one. In this way, we will have the input queue with the first K elements in the reversed order at the rear of the queue. We will dequeue (size — k) elements from the front and enqueue in the same queue one by one. Thus, we will have the resultant queue with the first K elements in reversed order.

Look at the below example for clear understanding, Here queue is given to you and K is 4:

Solution Steps

Create an empty stack.
Dequeue K items from the queue and push them into the stack, one by one.
Enqueue the contents of the stack at the back of the queue
Dequeue (size-k) elements from the front and enqueue them one by one in the same queue.

Pseudo Code

int[] reverseQueueFirstKElements(queue Q, int k) {
    if (queue is Empty or k > queue.size()) 
            return Q
    Stack stack
    for (int i = 0 to i < k) { 
        stack.push(queue.peek()) 
        queue.dequeue() 
    }
    while (stack is not empty()) { 
        queue.enqueue(stack.top())
        stack.pop()
    } 
    for (int i = 0 to i < queue.size() - k) { 
        queue.enqueue(queue.peek())
        queue.dequeue()
    }
    return queue
}

Complexity Analysis

Time Complexity: O(n+k)

Where n is the queue size and k is the number of elements to be reversed.

Space Complexity: O(n)

Critical Ideas To Think

How did we rotate the first K elements?
Can we solve this problem by using two auxiliary queues instead of one auxiliary stack?
Why did we enqueue the items from the same queue in the last loop? And why such operation is performed for size — k times only?