キューとは

キューは、FIFO(First In First Out)と呼ばれるデータ構造になります。
スタックは、後から挿入されたものから取り出されていましたが、
キューは最初に挿入したものが、最初に取り出されます。

イメージでいうと、レジの会計でしょうか。

例を見ていきましょう

数字を1,3,5の順でキューに挿入します。

1

3 1

5 3 1

次にこれらを取り出します。
最初に挿入した1から取り出されます。

5 3

5

以上です。

スタックとは

ブロックを上から積み重ねていくようなデータ構造のことを言います。

スタックのデータ構造はLIFO(last in first out)(後入れ先出し)です。

後入れ先出しというように、後から挿入したデータが最初に取り出されるデータ構造のこといいます。

例を見てきましょう

スタックの構造

スタックに以下の数字1,3,5を挿入していきます。挿入することをpushといいます。

push 1
1

push 3
3 1

push 5
5 3 1

スタックは順に積み重なる構造になるので、最初に挿入した1がデータ構造の最後に来ます。

次は、スタックに挿入されたデータを取り出して見ましょう。
スタックからデータを取り出すことをpopと言います。

pop
3 1

pop
1

再度データを挿入してみます。

push 7
7 1

push 9
9 7 1

挿入する場合は、先頭から挿入されるため、最初に挿入した1は
最後まで残ることになります。

文字列が回文かどうかを判定する

問題：与えられた文字列が回文かどうかを調べる関数を作成せよ

回文とは

上から読んでも下から読んでも同じである文字列のことをいいます。
例えば

abcba,abba

などです。

回文と判定するには

回文の文字列を見るとなんとなく想像できるかと思いますが、
奇数個の文字列が2個以上存在すると回文ではなくなってしまいます。
文字数に着目して、この条件が正しいかどうかチェックしましょう

奇数個の文字列

abcba abcdabd

これらの文字列は回文です。
法則に着目すると、奇数の数の文字が一つしかないことに気づきます。
では今度は偶数個の文字列です。

abcbca,abcdcbda

偶数個の回文には、偶数個の文字しか置けないことに気が付きます
よって奇数個の文字が2つ以上あるとき回文でないことが判定できます。

これらを踏んでのkotlinのサンプルコードです

kotlin

fun main(args : Array) {
    if(isPalindrome("eeffkabcabcdd")){
        println("回文です")
    }
    else{
        println("回文ではありません")
    }
}

// 回文かどうかチェックする
fun isPalindrome(str : String) : Boolean{
    var tables = getCharFrequencyTable("ababc")
    return !isOddNumOne(tables)
}

/**
 * 文字に対応する数値を返す
 * アルファベット以外なら-1を返す
 */
fun getCharNumber(c : Char) : Int{
    val a = Character.getNumericValue('a')
    val z = Character.getNumericValue('z')
    val charInt = Character.getNumericValue(c)
    // アルファベット範囲内
    if(charInt >= a && charInt <= z){
        return charInt - a
    }
    return -1
}

// 各文字が何個含まれるのかを保持する配列を返す
fun getCharFrequencyTable(str : String) : IntArray{
    var tables = IntArray(Character.getNumericValue('z') - Character.getNumericValue('a') + 1)
    for(c in str) {
        val charInt = getCharNumber(c)
        if(charInt != -1){
            tables[charInt]++
        }
    }
    return tables
}

// 奇数の文字数が複数ないか
fun isOddNumOne(tables : IntArray) : Boolean{
    var isOdd : Boolean = false
    for(num in tables){
        if(num % 2 != 0){
            if(isOdd){
                return false;
            }
            isOdd = true
        }
    }
    return false
}

同じ文字列かどうかを判定する

問題:2つの文字列があり、片方の文字列がもう片方を並べ替えたものになっているかどうかを判定するプログラムを書け

2つの文字列が同じ文字と文字数が使われていること(順列の性質)を利用します。

文字コード分の配列を整数型で確保して、片方の文字数を加算、
もう片方の文字列を減産し、各々の文字数が不一致ならば、違う文字列だと判断することができますね。

コードを見ていきましょう

kotlin

fun isPermutation(str1 : String,str2 : String) : Boolean {
    // 長さが違えば異なる文字列
    if(str1.length != str2.length){
        return false
    }
    // ascii仮定
    var letters = IntArray(128)
    for(char in str1){
        // 対応する文字コード数のindexを加算する
        letters[char.toInt()]++
    }

    // 一致チェック
    for(char in str2){
        letters[char.toInt()]--
        // ある文字数が多い場合一致しないことになる
        if(letters[char.toInt()] < 0){
            return false

        }
    }
    return true
}

文字コードをasciiと解釈しています

重複しない文字列

問題

入力されたUNICODE文字列が、重複する文字がないかどうか判定するプログラムを書く

ASCIIコードは128種類らしいので、文字列の長さが128を超えたとすると、重複していることになります。
128個と要素数が決まっているので、boolean型で配列を確保して判定するのが
すぐ思いつくやり方だろうか

kotlin

fun isUniqueChars(str: String): Boolean {
    if (str.length > 128) return false
    var charSet = BooleanArray(128);

    for (char in str) {
        var value: Int = char.toInt();
        if (charSet[value]) {
            return false
        }
        charSet[value] = true
        return true
    }
    return true
}