ブログ名どうしようかなスマートフォン用の表示で見るブログ名どうしようかなこの広告は、90日以上更新していないブログに表示しています。Kindle版この商品を含むブログを見るこの本で、今日は「スタック」「キュー」「動的な配列」「リスト」を提供するライブラリの使い方を勉強していました。こちらで紹介されているのはC++の標準ライブラリなので、Javaで同様のデータ構造を持つクラスの使い方を調べてみました。ArrayList参考リンク使ってみたおわりに参考リンクqiita.comスタックスタックはStackクラスというものが存在しますが、こちらは推奨されていないようで、Dequeインターフェイスを使用します。先頭の要素に対してのみ、追加や削除の操作を行うようにします。要素数を調べるsize()メソッドと、要素がない場合にtrueを返すisEmpty()メソッドが使用できます。対応する○○Firstメソッドと全く同じ操作みたいです。「例外をスローする」または「戻り値でnullやfalseを返す」2つの形式のメソッドがそれぞれの操作に用意されています。peek()peekFirst()Stackと同名のメソッドでいうと、pushとpopの操作は失敗時に例外をスローしますが、peekの操作では、例外は発生せずにnullが返ってきます。「失敗が例外的ではなく通常のことである場合に使用する目的で設計されている」とのことです。固定長のクラスで実装して使った場合の為だけに特別に用意されているそうです。(Dequeの実装クラス4つの中では「LinkedBlockingDeque」だけがこれに該当する。)だから、実際に使うのは太字のメソッドになると思います。あと、キューの両端が空かどうかをnullで判定している為、nullの追加は厳禁らしいです。スタックから取り出して表示System.out.println(stack.pop());}}キューキューは専用のインターフェースが用意されています。こちらも上記のDequeと同じように、操作失敗時の挙動が異なるメソッドが、それぞれ2つずつあります。前述の通り、失敗時にnullやfalseを返す形式のメソッドは、queueインターフェースを固定長のクラスで実装した場合を想定して設計しているそうです。固定容量(バウンド)キューが原因で発生する場合のように、offerメソッドは、失敗が例外的ではなく通常のことである場合に使用する目的で設計されています。挿入の操作はoffer()メソッドを使うことを推奨されていました。こちらも同じくnullの追加は禁止されています。キューの先頭の要素を取得するpollメソッドで、要素が存在しないときの戻り値のnullと見分けが付かなくなってしまうからだそうです。要素数を調べるsize()メソッドと、要素がない場合にtrueを返すisEmpty()メソッドが使えます。name;}}動的な配列JavaにもVectorクラスは存在しますが、Vectorクラスはかなり古いクラスなので、現在はArrayListを使います。Vectorはスレッドセーフなのに対して、ArrayListは同期化されていません。同期化されていない代わりに、Vectorより高速に動くそうです。メソッドを使用してラップすることで、ArraysListも同期化を行えます。結局の所、動的な配列はArraysListを使うということになるようです。要素数を調べるsize()メソッドと、要素がない場合にtrueを返すisEmpty()メソッドが使えます。8)www.sejuku.netリストJavaの双方向連結リストは、LinkedListクラスが用意されています。使用できないので注意。ArrayListLinkedListはArrayListと同じく、Listインターフェースの実装クラスの1つですが、ArrayListのjavadocを見ると、addを除くほとんどの処理は、ArrayListの方がLinkedListよりも速いようなことが書いてあります。処理は、一定の時間で実行されます。処理も、一定の償却時間で実行されます。ほとんどの場合、ほかのすべての処理も比例的な時間で実行されます。実装の場合より小さくなります。前後のノードと連結することで順番に辿れるようになっています。それに対し、ArrayListは動的な"配列"です。各要素にはそれぞれ番号が割り振られています。先頭(または末尾)から1つずつ順番に、1万番目まで辿らなくてはなりません。ような特定の位置の要素を参照する操作は、不向きと言えます。一方で、リスト内の途中の要素を操作する場合の処理に関しては、LinkedListに軍配が上がります。それは、ArrayListではそれぞれの要素に番号が割り振られてるが為に、リストの途中に要素を追加されると、それ移行の要素の番号を全てずらしてやる必要があるからです。後続の9999個の要素にも変更を加えなければなりません。修正を加えるのは、その前後2つのノードだけで済みます。index)が呼び出されてしまう。o)メソッドを呼び出す。{e.printStackTrace();}}}おわりに恥ずかしながらArrayList以外は全く知らなかったので、かなり勉強になりました。ここらへんを勉強してると、コレクションやジェネリクスをよく分かっていないのが浮き彫りになってしまったので、そちらもちゃんと勉強する必要がありそうです。次章からはついに探索に入ります!ここまではソートの仕方と構造体の仕組みだったので、いよいよテクニックの部分に触れられると思うと楽しみです。競プロを始めて一ヶ月が経ち、今回で5回目の参加です。スフィンクスのなぞなぞ解説を見て、なるほど!と感心したので記しておきます。(1)検索リンクはてなブログブログをはじめる週刊はてなブログはてなブログProはてなブログをはじめよう!a2606さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。