Getting Started Algorithm

Getting Started Algorithm 2018/12/19 ヤフー福岡 Tech Meetup#2

YAMASAKI SHOHEI 山崎 勝平 @sinn_shoyan

Introduction • データ構造とアルゴリズムのはじめかた • キューの紹介 • Javaのキューの実装(登録と削除のみ)

データ構造とアルゴリズムの はじめかた • データ構造がおすすめ • データ構造は普段のプログラミングで親しんでいるので とっつきやすい

データ構造とは 種類 内容 リスト 線形データ構造 連想記憶 (ハッシュテーブル、辞書、マップ) スタック、キュー ツリー構造 グラフデータ構造 ヒープ構造

キューとは head tail 追加するデータ • 待ち行列と言われるデータ構造 • データの順番を保持する必要がある場合に役立つ

キューの実装 • 配列(Array) • 連結リスト (Linked list) • 循環リスト (Circularly-linked list)

連結リストとは 3 5 8 NULL • データを一方向に繋いだデータ構造 • ノードというデータを繋げて作成する • リストの最後のノードのリンクはNULL

ノードとは データ リンク データと次のノードへのリンクを持つ構造体

Javaでのノード実装 class Node { E data; Node next; Node(E d, Node node) { data = d; next = node; } }

キューとは head tail 追加するデータ • 待ち行列と言われるデータ構造 • データの順番を保持する必要がある場合に役立つ

Javaでのキューの実装 public class LinkedQueue<E> { // Queueの最初のデータ Node head; // Queueの最後のデータ Node tail; LinkedQueue() { head = null; tail = null; } }

データの登録 5 8 NULL tail 13 NULL 新ノード • 新ノードを作成する • 新ノードのリンクはNULL

データの登録 5 8 13 NULL tail 新ノード • tailノードのリンクを新ノードに設定する

データの登録 5 8 13 NULL tail • tailポインタを新ノードを指すように更新する

Javaで実装 public boolean enQueue(E data) { Node node = new Node(data, null); if (head == null) { head = node; } else { tail.next = node; } tail = node; return true; }

データの削除 3 5 8 NULL head • headのノードを削除する場合

データの削除 3 5 8 NULL head • headポインタを次のノードに設定する

データの削除 3 5 8 NULL head 削除する • 先頭のノードを削除する

Javaで実装 public E deQueue() { if (head == null) { throw new NoSuchElementException(); } E data = head.data; head = head.next; if (head == null) { tail = null; } return x; }

このような感じで使います LinkedQueue<Integer> q = new LinkedQueue<>(); q.enQueue(1); q.enQueue(2); System.out.println(q.deQueue()); => 1 System.out.println(q.deQueue()); => 2

ソースコード • https://github.com/shoyan/algorithm/blob/master/ src/main/java/linkedqueue/LinkedQueue.java