C++で最近使用したアプリ（MRU）を表示するプログラムの実装方法

数値 k と、システム上で開かれているアプリのIDを格納した n 個の整数要素を持つ配列 arr[n] が与えられたとします。この課題では、キーボードの Alt + Tab を押したときのように、最近使用した順に k 個のアプリを表示します。各IDの位置は、システム内のそれぞれ異なるアプリを表しています。

配列の構成は次のとおりです。

• arr[0] のIDは、現在使用中のアプリです。
• arr[1] のIDは、直前に使用されたアプリです。
• arr[n-1] のIDは、最も長く使用されていないアプリです。

補足： Alt + Tab キーを押すと、インデックス0（現在使用中のアプリ）から順に、開いているすべてのアプリを移動するポインタが動作します。

例

入力: arr[] = {1, 2, 3, 4, 5}, k=2
出力: 3 1 2 4 5
説明: ID 3 のアプリへ切り替えたい場合、そのアプリが現在使用中のアプリ（先頭）となり、
その他のアプリは最近使用された順に並び替えられます。

入力: arr[] = {6, 1, 9, 5, 3}, k=3
出力: 5 6 1 9 3

解決のためのアプローチ

• 配列 arr[n] と値 k を入力として受け取ります。
• ユーザーが切り替えたいアプリのインデックス（k）を取得します。
• インデックス k にあるIDを現在のアプリ（先頭）とし、残りの要素は順序を保ったまま後ろへずらします。
• 結果を出力します。

アルゴリズム

Start
Step 1-> k個の最近使用アプリを求める関数を宣言
    void recently(int* arr, int size, int elem)
    int index = 0 を宣言
    index = (elem % size) を設定
    int temp = index, id = arr[index] を宣言・設定
    temp > 0 の間ループ
        arr[temp] = arr[--temp] を設定
    End
    arr[0] = id を設定
Step 2-> 配列要素を出力する関数を宣言
    void print(int* arr, int size)
    i = 0; i < size; i++ の For ループ
        arr[i] を出力
    End
Step 3-> main() 内での処理
    int elem = 3 を宣言・設定
    int arr[] = { 6, 1, 9, 5, 3 } として配列を宣言
    int size = sizeof(arr) / sizeof(arr[0]) でサイズを計算
    recently(arr, size, elem) を呼び出す
    print(arr, size) を呼び出す
Stop

C++での実装例

#include <bits/stdc++.h>
using namespace std;
// 配列を「最近使用した順」に更新する関数
void recently(int* arr, int size, int elem) {
    int index = 0;
    index = (elem % size);
    int temp = index, id = arr[index];
    while (temp > 0) {
        arr[temp] = arr[--temp];
    }
    arr[0] = id;
}
// 配列要素を出力する関数
void print(int* arr, int size) {
    for (int i = 0; i < size; i++)
    cout << arr[i] << " ";
}
int main() {
    int elem = 3;
    int arr[] = { 6, 1, 9, 5, 3 };
    int size = sizeof(arr) / sizeof(arr[0]);
    recently(arr, size, elem);
    cout<<"array in most recently used fashion : ";
    print(arr, size);
    return 0;
}

出力結果

array in most recently used fashion : 5 6 1 9 3

アルゴリズムのポイント

このアルゴリズムの核となるのは、elem % size によって対象アプリのインデックスを求め、その位置にあるIDを一時保存したうえで、先頭までの要素をひとつずつ後ろへシフトする処理です。最後に保存しておいたIDを arr[0] に代入することで、対象アプリが「現在使用中」の状態になります。

計算量は、シフト処理が最大でインデックスの位置分だけ発生するため O(k)、追加のメモリは不要で O(1) となります。Alt + Tab のようなアプリ切り替え履歴の管理は、OSやランチャーアプリなどでも実際に使われている基本的な考え方です。