Bir növbə probleminin ilk K elementlərini geri qaytararkən a queue və k rəqəmi, növbənin standart əməliyyatlarını istifadə edərək növbənin ilk k elementlərini tərsinə çevirin.
Mündəricat
Nümunələr
Input:
növbə = 10 -> 15 -> 31 -> 17 -> 12 -> 19 -> 2
k = 3
Çıxış:
növbə = 31 -> 15 -> 10 -> 17 -> 12 -> 19 -> 2
Input:
növbə = 12 -> 14 -> 16 -> 7 -> 9
k = 2
Çıxış:
növbə = 14 -> 12 -> 16 -> 7 -> 9
Bir sıra ilk K elementlərinin tərsinə çevrilməsi üçün alqoritm
Sıranın ilk k elementlərini geri qaytarmaq üçün bir yığın istifadə edə bilərik.
- Sıranın ilk k elementlərini çıxarın və yığına itələyin.
- Yığın bütün elementlərini açın və növbənin sonuna qədər itələyin.
- Növbənin ön hissəsindən açılan (n - k) elementlər və onları növbənin sonuna qədər itələyin, burada n növbədəki elementlərin ümumi sayıdır.
- Əvvəlcə növbənin k elementləri tərs çevrilir, növbə elementlərini çap edin.
Bir növbənin ilk K elementlərinin tərsinə çevrilməsinə dair izahat
Bir nümunəyə baxaq,
növbə = 10 -> 7 -> 4 -> 3
k = 2
Step 1
Sıranın ilk k elementlərini çıxarın və yığına itələyin.
növbə = 10 -> 7 -> 4 -> 3 və yığın = boş
Təkrarlama 1
növbə = 7 -> 4 -> 3 və yığın = 10
Təkrarlama 2
növbə = 4 -> 3 və yığın = 7 -> 10
Step 2
Yığın bütün elementlərini açın və növbənin sonuna qədər itələyin.
növbə = 4 -> 3 və yığın = 7 -> 10
Təkrarlama 1
növbə = 4 -> 3 -> 7 və yığın = 10
Təkrarlama 2
növbə = 4 -> 3 -> 7 -> 10 və yığın = boş
Step 3
(N - k) elementləri növbənin ön hissəsindən çıxarın və növbənin sonuna qədər itələyin
növbə = 4 -> 3 -> 7 -> 10
Təkrarlama 1
növbə = 3 -> 7 -> 10 -> 4
Təkrarlama 2
növbə = 7 -> 10 -> 4 -> 3
JAVA Kodu
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class ReversingTheFirstKElementsOfAQueue {
private static void reverseKElements(Queue<Integer> queue, int k) {
if (k < 0 || k >= queue.size() || queue.isEmpty()) {
System.out.println("Invalid Input");
return;
}
int n = queue.size();
// remove first k elements of queue and push in stack
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < k; i++) {
int curr = queue.poll();
stack.push(curr);
}
// Pop out elements from stack and add to the end of the queue
while (!stack.isEmpty()) {
int curr = stack.pop();
queue.add(curr);
}
// Remove first (n - k) elements of the queue and add them to the end
for (int i = 0; i < n - k; i++) {
int curr = queue.poll();
queue.add(curr);
}
// Print the elements of the queue
for (Integer i : queue) {
System.out.print(i + " ");
}
System.out.println();
}
public static void main(String[] args) {
// Example 1
Queue<Integer> q1 = new LinkedList<>();
int k1 = 3;
q1.add(10);
q1.add(15);
q1.add(31);
q1.add(17);
q1.add(12);
q1.add(19);
q1.add(2);
reverseKElements(q1, k1);
// Example 2
Queue<Integer> q2 = new LinkedList<>();
int k2 = 2;
q2.add(12);
q2.add(14);
q2.add(16);
q2.add(7);
q2.add(9);
reverseKElements(q2, k2);
}
}
31 15 10 17 12 19 2 14 12 16 7 9
C ++ kodu
#include<bits/stdc++.h>
using namespace std;
void reverseKElements(queue<int> &queue, int k) {
if (k < 0 || k >= queue.size() || queue.empty()) {
cout<<"Invalid Input"<<endl;
return;
}
int n = queue.size();
// remove first k elements of queue and push in stack
stack<int> st;
for (int i = 0; i < k; i++) {
int curr = queue.front();
queue.pop();
st.push(curr);
}
// Pop out elements from stack and add to the end of the queue
for (int i = 0; i < k; i++) {
int curr = st.top();
st.pop();
queue.push(curr);
}
// Remove first (n - k) elements of the queue and add them to the end
for (int i = 0; i < n - k; i++) {
int curr = queue.front();
queue.pop();
queue.push(curr);
}
// Print the elements of the queue
for (int i = 0; i < n; i++) {
int curr = queue.front();
queue.pop();
cout<<curr<<" ";
queue.push(curr);
}
cout<<endl;
}
int main() {
// Example 1
queue<int> q1;
int k1 = 3;
q1.push(10);
q1.push(15);
q1.push(31);
q1.push(17);
q1.push(12);
q1.push(19);
q1.push(2);
reverseKElements(q1, k1);
// Example 2
queue<int> q2;
int k2 = 2;
q2.push(12);
q2.push(14);
q2.push(16);
q2.push(7);
q2.push(9);
reverseKElements(q2, k2);
}
31 15 10 17 12 19 2 14 12 16 7 9
Bir növbənin ilk K elementlərini geri çevirmək üçün mürəkkəblik analizi
Zaman Mürəkkəbliyi = O (n + k)
Kosmik Mürəkkəblik = Tamam)
burada n növbədəki elementlərin sayıdır.
