実装して学ぶ基本的データ構造 ~StackとQueue編~

StackとQueueに関して

まず，初めに基本的なデータ構造を学ぶとき，スタックやキューが出てくると思います．この二つが持つデータ構造からそれぞれ使いどころが変わってきます．
データの処理の仕方などを考える上で必要になってくると思うので，単にLIFOやFIFOという言葉を学ぶのではなく実践的に学ぶとそれぞれの違いが学べると思います．
以下ではスタックとキューの考え方からそれを用いたプログラミングの問題に取り組んでいます．意味を理解しながら，一緒に実装していきましょう．

Stack

Stackとは

一時的にデータを退避したいときに有効なデータ構造で，データの中で最後に入ったものが最初に取り出される後入れ先出し(LIFO:Last In First Out)の規則に従ってデータを管理する方法です．
基本的にはデータの追加・取り出し・配列が空かどうか・配列が一杯かどうかなどを操作を持っています．

逆ポーランド記法(演習問題)

逆ポーランド記法は，演算子を被演算子の後に記述するプログラムの記法.
例えば，(1+2) * (4+3)という数式があった場合逆ポーランド記法では
12+43+* と記述されます．
これを用いればプログラミングの知識で電卓のようなものを作ることができます．

入力例ではALDS1_3_A：Stackに従い，
"1 2 + 3 4 - *"
を入れたいと思います.
"-3"が出力されれば正解となります．
では，実際に実装していきましょう．

def Stack(order_list):
    cal_list = []
    for content in order_list:
        if content == "+":
            b = cal_list.pop()
            a = cal_list.pop()
            cal_list.append(a+b)
        elif content == "-":
            b = cal_list.pop()
            a = cal_list.pop()
            cal_list.append(a-b)
        elif content == "*":
            b = cal_list.pop()
            a = cal_list.pop()
            cal_list.append(a*b)
        else:
            cal_list.append(int(content))
            
    return cal_list[0]

order = "1 2 + 3 4 - *"
order_list = list(order.split())
ans = Stack(order_list)
print(ans)

実際にAOJの問題を解く場合はorder_list = input().split()として提出してみてください．
また，今回は演算子が"+ - *" の三つでしたが本来は除算も含まれるのでどうすれば機能を追加できるか試してみてください.
本来はエラー処理なども考える必要がありますが，今回は計算ロジックだけ汲み取れればいいと判断し，このようになっています．

Queue

Queueとは

待ち行列とも呼ばれ，データを到着した順に処理していくときに使うデータ構造で，データの中で最初に入ったものが最初に取り出される，先入れ先出し（FIFO: First In First Out）の規則に従ってデータを管理します．
イメージとしてはレジ待ちの行列のような感じですかね．
基本的な操作はスタックと同様です．

ラウンドロビンスケジューリング(演習問題)

ラウンドロビンスケジューリングとは，プロセスの管理方法の一つで，順番にプロセッサ(計算するところ)を割り当てる方式のことです．
一定時間プロセッサで処理を行なった後，まだプロセスが完了していなければキューの後ろにプロセスを回し，プロセッサは次のプロセスの処理を行うというのを繰り返していきます．

対応する問題はALDS1_3_B: Queueで入力例・出力例は次のようになります．

入力例		出力例
5	100
p1	150	p2	180
p2	80	p5	400
p3	200	p1	450
p4	350	p3	550
p5	20	p4	800

def round_robin(queue_list, t):
    elapsed_time = 0
    while len(queue_list) > 0:
        p, c = queue_list.pop(0)
        if c-t > 0:
            elapsed_time += t
            queue_list.append([p, c-t])
        else:
            elapsed_time += c
            print("{} {}".format(p,elapsed_time))

N, cpu_time = map(int,input().split())
queue_list = []
for i in range(N):
    process,cost = input().split()
    queue_list.append([process, int(cost)])

round_robin(queue_list, cpu_time)

pythonの場合リストの大きさはあらかじめ決めることもできますが，決めずに作ることができるので，C言語などと比べて直感的にわかりやすい形になっているかと思います．
また，競技プログラミングに合わせた形で入力を受け取っているので初めての人は見慣れないとは思います．どういった処理を行なっているのかはround_robinの部分に全て書いてあるので追ってみてください．

スズメの本棚

自分の知識の定着のために本や実装したことをまとめていきます．

実装して学ぶ基本データ構造~StackとQueue編~