We need to reverse the order of the first k members of a queue of numb

1.	We need to reverse the order of the first k members of a queue of numbers, leaving the other elements in the same relative order, given an integer k and a queue of integers. Only the standard operations like enqueue, dequeue, size and front are allowed.
Answer» Using an auxiliary stack is the strategy. Create a stack that is empty. Dequeue the first k items from the provided queue one by one and then stack the dequeued items. Backfill the queue with the CONTENTS of the stack. Dequeue (size-k) elements from the front and ADD them to the same queue one by one. Here is the C++ implementation of the algorithm discussed: // C++void reverseFirstKElements(int k, queue<int>& Q){ if (Q.empty() \|\| k > Q.size()) return; if (k <= 0) return; stack<int> S; int i = 1; /* PUSH the first k elements of the Queue into the Stack/ while (i <= k) { S.push(Q.front()); Q.pop(); i++; } / ENQUEUE the elements of the stack at the end of the queue/ while (S.empty() == false) { Q.push(S.top()); S.pop(); } / the remaining elements to be enqueued at the end of the Queue*/ for (int i = 0; i < Q.size() - k; i++) { Q.push(Q.front()); Q.pop(); }} We dequeue the first k elements from the queue Q and push them into the stack S. We then insert the elements from S to Q. Then (size-k) elements are removed from the front and ADDED to Q one by one.

We need to reverse the order of the first k members of a queue of numbers, leaving the other elements in the same relative order, given an integer k and a queue of integers. Only the standard operations like enqueue, dequeue, size and front are allowed.

Answer»

Using an auxiliary stack is the strategy.

Create a stack that is empty.
Dequeue the first k items from the provided queue one by one and then stack the dequeued items.
Backfill the queue with the CONTENTS of the stack.
Dequeue (size-k) elements from the front and ADD them to the same queue one by one.

Here is the C++ implementation of the algorithm discussed:

// C++void reverseFirstKElements(int k, queue<int>& Q){ if (Q.empty() || k > Q.size()) return; if (k <= 0) return; stack<int> S; int i = 1; /* PUSH the first k elements of the Queue into the Stack*/ while (i <= k) { S.push(Q.front()); Q.pop(); i++; } /* ENQUEUE the elements of the stack at the end of the queue*/ while (S.empty() == false) { Q.push(S.top()); S.pop(); } /* the remaining elements to be enqueued at the end of the Queue*/ for (int i = 0; i < Q.size() - k; i++) { Q.push(Q.front()); Q.pop(); }}

We dequeue the first k elements from the queue Q and push them into the stack S. We then insert the elements from S to Q. Then (size-k) elements are removed from the front and ADDED to Q one by one.

We need to reverse the order of the first k members of a queue of numbers, leaving the other elements in the same relative order, given an integer k and a queue of integers. Only the standard operations like enqueue, dequeue, size and front are allowed.

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment