C++のスタック（stack）を使って数値を反転する方法

はじめに

整数 Num が入力として与えられます。この記事では、スタック を使ってこの数値を反転（逆順）にする方法を解説します。

スタックとは

スタックとは、C++ における基本的なデータ構造の一つで、LIFO（Last In First Out：後入れ先出し） 方式でデータを格納します。最後に追加した要素が最初に取り出される点が大きな特徴です。

宣言方法は以下の通りです。

stack <int> stck; // stck がスタック変数になります

スタックの主な操作は次の 4 つです。

• top()：先頭要素を参照する ― stck.top() はスタックの先頭要素への参照を返します。

• pop()：先頭要素を削除する ― スタックから最上位の要素を取り除きます。

• push()：要素を追加する ― stck.push(value) は値 value をスタックに追加します。value の型はスタックの要素型と一致している必要があります。

• empty()：空かどうかを確認する ― stck.empty() はスタックが空の場合に true を返します。

具体例

例 1

入力：Num = 33267

出力：数値の逆順は 76233

説明：

まず、すべての桁をスタックにプッシュします。

7 - 6 - 2 - 3 - 3 ← 先頭（top）

各桁に桁の重みを掛けて足し合わせます。

7 × 10000 + 6 × 1000 + 2 × 100 + 3 × 10 + 3 × 1
= 70000 + 6000 + 200 + 30 + 3
= 76233

例 2

入力：Num = 111000

出力：数値の逆順は 111

説明：

まず、すべての桁をスタックにプッシュします。

0 - 0 - 0 - 1 - 1 - 1 ← 先頭（top）

各桁に桁の重みを掛けて足し合わせます。

0 × 100000 + 0 × 10000 + 0 × 1000 + 1 × 100 + 1 × 10 + 1 × 1
= 0 + 0 + 0 + 100 + 10 + 1
= 111

※ 末尾の 0 は反転すると先頭に来るため、結果からは消えている点に注意してください。

アルゴリズムの考え方

このアプローチでは、まず入力された数値を 10 で割った余り（一の位）を求めてスタックにプッシュし、数値が 0 になるまでこれを繰り返します。こうすることで、スタックには最上位の桁が先頭（トップ）に格納されます。あとはスタックから要素を取り出しながら、桁の重み（1、10、100…）を掛けて合計すれば、反転した数値が得られます。

• 入力数値 Num を受け取ります。

• stack<int> stck で整数用の空のスタックを作成します。

• 関数 pushDigts(int num1) は num1 を受け取り、各桁を最初の桁がトップになるようにスタックへ追加します。

• 剰余を格納するための変数 rem を用意します。

• while ループで num1 が 0 でない間、rem = num1 % 10 を計算します。

• rem をスタックにプッシュします。

• num1 を 10 で割り、次の桁へ処理を進めます。

• 次に関数 revrseNum() を呼び出し、スタックの要素を使って数値を反転します。

• 変数 revrs、topp、temp、i を用意します。

• スタックが空でない間、以下の手順を繰り返します。

• topp = stck.top() で先頭要素を取得します。

• stck.pop() でスタックから先頭要素を取り除きます。

• temp = topp * i を計算します。

• revrs に temp を加算します。

• i を 10 倍ずつ増やしていきます（1 → 10 → 100 …）。

• 最後に入力数値の反転結果 revrs を返します。

• main 関数の中で結果を出力します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
stack <int> stck;
void pushDigts(int num1){
    int rem;
    while (num1 > 0){
        rem = num1 % 10;
        stck.push(rem);
        num1 = num1 / 10;
    }
}
int revrseNum(){
    int revrs = 0;
    int i = 1;
    int temp;
    int topp;
    while (!stck.empty()){
        topp = stck.top();
        stck.pop();
        temp = topp * i;
        revrs = revrs + temp;
        i *= 10;
    }
    return revrs;
}
int main(){
    int Num = 43556;
    pushDigts(Num);
    cout<<"Reverse of number is: "<<revrseNum();
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

Reverse of number is: 65534

入力 43556 の各桁がスタックに格納され、LIFO の特性によって逆順の 65534 が正しく求まっていることがわかります。