5/1に書き始めたデータ構造の記事を今更書きます。怠惰。
データ構造
stack（スタック）とqueue（キュー）がある。くえぅえではない。
簡単なイメージは、
・スタックは「積み上げられた書類の山」。書類は上へ上へと積まれていき、あなたはそれを上から処理する。
・キューは「順番待ちの列」。お店に入ってきた人は出来ている列の後ろに並び、先頭の人から注文を受けていく。
というもの。
キューには「優先度付きキュー」というのも存在するが、これは順番待ちの列で、階級が上の人が列の先頭へと優先的に並ぶことができるような状況。まあはっきり言ってしまえば、データが入ってくると逐一それをソートするようなデータ構造のこと。
スタック
push（プッシュ）とpop（ポップ）という二つの操作からなる。前者は「データを入れる」、後者は「データを取り出す」に相当。pythonだと、コマンドとしては、列のケツに突っ込むappendと、列のケツから取り出していくpopにあたる。
上へ書類を積むという比喩を用いたけど、実際には上に相当するのはリストの末尾です。そこだけ注意。
（例）
stack（リスト名はなんでもいいんだけど）に3,4,1を順に突っ込む
stack = [] stack.append(3) stack.append(4) stack.append(1) #ここまででstack = [3,4,1]
stackから要素を「入れた順番が新しい方から」取り出す
stack = [3,4,1] a = stack.pop() #a == 1 b = stack.pop() #b == 4 c = stack.pop() #c == 3 , stack == []
練習問題↓
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_A&lang=jpjudge.u-aizu.ac.jp
逆ポーランド記法と呼ばれてるやつを計算しましょうねという問題。
リストを持っておいて、数字が入ってきたらそれをリストの末尾に追加、演算子が来たらそれをリストの後ろから数えて二つの数字に施し、一つになった数字をまたリストのケツに突っ込む。最終的にはリストの中に数字が一つだけ残るはずなので、それを出力すればよいという話。
キュー
dequeとかいうよくわからんのを使う。そもそも、このデータ構造は、リストで言えば「要素をリストのケツに突っ込んで、先頭から要素を取り出す」という風になっているので、普通のリストでやろうとすると「先頭から取り出す」の時に2番目以降の要素を一つずづずらす手間がかかる（多分O(n)）。だから、普通のリストでやるんじゃなくて、標準装備されている特殊な構造（今回はdeque）でやるんだよってことなのかな。
操作は、まずimport collectionsという呪文を唱えてから、リストqをdequeにするために、q = collections.deque()とする。それから、pushとpopに相当する操作として、リストに要素を入れるときはappend（これはリストの末尾に要素を加えるので、スタックと同じ）、リストの先頭（左端）から要素を取り出すのはpopleftというコマンドを使う。
（例）
queueに要素を入れる
import collections q = collections.deque() q.append(3) q.append(4) q.append(1) #ここまででq = [3,4,1]
queueから「入れた順番が速い方から」取り出す
q = [3,4,1] a = q.popleft() #a == 3 b = q.popleft() #b == 4 c = q.popleft() #c == 1 , q == []
練習問題↓
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_B&lang=jpjudge.u-aizu.ac.jp
いくつか仕事があって、1ターンでできる仕事の量が限られていて、その量を超過した仕事は、残りを後回しにされる。これを繰り返していつ仕事が終わりますかという問題。queueでデータを持っておいて、仕事をリストの先頭から取り出し、制限時間内でできたらリストから削除、できなかったら残りをリストの最後に入れるってのを繰り返していくアルゴリズムを実装する。
優先度付きキュー（プライオリティーキュー）
これまでにも何度か出てきたけどここでおさらい。キューとほぼ同じ構造を持っているけど、違うのは「リストに要素を入れた後でソートする」というひと手間が加えられていること。
例えば1000個の品物があって、そこから価値の高い品物ベスト10を選ぼうみたいな問題が出されたとき、（「まあリスト全部突っ込んでソートすればよくない？」みたいなツッコミはおいといて）前から順番に舐めていって、その時その時のベスト10を更新するのがこのデータ構造でできるようになる。
pythonだとheapqというコマンドを使います。ここもqueueとは違う点（queueはdequeを使うよね）なので注意します。使うコマンドは、
①heapq.heapify(リスト名） これはリストを「優先度付きキュー」として扱うようにする
②heapq.heappush(リスト名,要素） これはリストに要素を追加する（のと、それを含めてソートする）
③heapq.heappop(リスト名） これはリストの先頭（左端）から要素を取り出す
の三つ。ややこしい。
特に①は、普通に持っていたリストをいきなり優先度付きキューとして扱いたい場合に使うと覚えとくのがいいかも。空のリストを優先度付きキューとして扱いたいのなら普通にheappushとheappopだけで事足りるけど、最初からいくつか要素が入っているリストをいきなり優先度付きキューとして扱いたい場合は、一回heapifyを使って優先度付きキューに直してから使う。
（例）
優先度付きキューに要素を入れる
import heapq Q = [] heapq.heappush(Q,3) # Q == [3] heapq.heappush(Q,4) # Q == [3,4] heapq.heappush(Q,1) # Q == [1,3,4]
リストから要素を取り出す
a = heapq.heappop(Q) # a == 1 b = heapq.heappop(Q) # b == 3 c = heapq.heappop(Q) #c == 4
import heapq Q = [3,4,1] heapq.heapify(Q) # なぜかこの時点だと昇順にならず、Q = [1,4,3]になっている模様。なんで？？？？？ a = heapq.heappop(Q) # a == 1 , Q == [3,4] b = heapq.heappop(Q) # b == 3 , Q == [4] c = heapq.heappop(Q) #c == 4 , Q == [] popは正常に動作している
意図しない挙動をしてしまったけど見なかったことにしよう。いいね？
↑heapqは、「先頭要素が常に最小要素になるデータ構造」なので、全部の要素が大小の順番を保っているとは限らない。それだけの話でした。
練習問題↓
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_C&lang=jpjudge.u-aizu.ac.jp
問題自体は大したことない、素直な実装をすればいいと思うけど、「大きいほうから取り出す」、つまり「リストの末尾（右端）から取り出す」という点がpopleftと違い、一筋縄ではいかない。
残念ながら大きい方から取り出すコマンドはないが、今回の問題のような場合は「要素を入れる際にマイナスをつける」「取り出すときにまたマイナスをつける」の操作を行うことで、大きい数字はより小さい数字として扱われるので対処できる。
なんか、プライオリティーキューの練習にいいよみたいに言われてる問題がこれ。
atcoder.jp
3*N個の要素が並んだ列からN個の数字を抜いて、残りの2*N個の要素を前半、後半に分けた後で、「前半の和」と「後半の和」の差ができるだけ大きくなるようにしようねっていう問題。
結局、
①0 <= k <= Nのkに対して、前半のN+k要素の総和の最大と、後半の2*N-k要素の総和の最小を別々に求めておき、リストに入れる。
（例）
SUML = [（前半N要素の総和の最大）,（前半N+1要素の総和の最大）、......、（前半2*N要素の総和の最大）]
SUMR = [（後半2*N要素の総和の最小）、（後半2*N-1要素の総和の最小）、......、（後半N要素の総和の最小）]
②0 <=i <= N-1のiに対して、SUML[i]-SUMR[i]を求め、その最大値を答えとして返す
ってのが基本方針になり、①の所でheapqが必要になる。
（あんまり参考にならない僕の解答↓）
atcoder.jp
map
例えば
Thank you for your mail and your lectures
という文章中に出てくる単語と、その回数を見たいとき、これは有用である。
L = list(input().split()) dict = {} for i in range(len(L)): if L[i] in dict: dict[L[i]] += 1 #「リストのn番目」に相当するのが単語になったみたいな感じ。単語が目印となる else: dict[L[i]] = 1 #dict == {'Thank': 1, 'you': 1, 'for': 1, 'your': 2, 'mail': 1, 'and': 1, 'lectures': 1} #max(dict) == 'your'
