6.Stack and Queue

キューとスタックは、古典的なデータ構造として広く知られているものですが、 実装上はリストの一種と考えることができます。

キュー

キュー (Queue) は「先入れ先出し (First-In First-Out, FIFO)」を表すデータ構造です。 データを取り出す際、先に格納したものから順に取り出します。

  • 銀行や病院やたい焼き屋の待ち行列 (先に並んだ人からサービスを受ける)
  • コンピューターでプリンタへの出力処理や、ウィンドウシステムのメッセージハンドラ、プロセスの管理など、データを入力された順番通りに処理する必要がある処理に用いられる。

データを追加する操作をエンキュー(enqueue)。
データを取り出す操作をデキュー(dequeue)という。

スタック

スタック(Stack)は、 「あと入れ先出し (Last-In First-Out, LIFO)」あるいは「先入れあと出し(First-In Last-Out, FILO)」を表すデータ構造です。 データを取り出す際、最も後に格納したものから順に取り出します。

  • 積ん読 (本を重ねて積んでいくと上からしか取れない)
  • コンピューターで割込みやサブルーチンを支援するために極めて有用である

 

 

スタックにデータを入れる操作をプッシュ(push)という。
スタックからデータを取り出す操作をポップ(pop)という。

キューとスタックの実装

オブジェクトの後入れ先出し(LIFO)スタックを表すStackクラスは、JDK 1.0から導入されていました。これに対して、オブジェクトの先入れ先出し(FIFO)を表す待ち行列(キュー)は、特に用意されていませんでしたが、JDK 5.0からQueueインターフェイスが新たに導入されました。

一例として、LinkedListオブジェクトによるキューと、Stackクラスによるスタックを試すプログラムを作成しました。

import java.util.*;

String[] item = {"Apple", "Banana", "Cocoa"};
Queue q = new LinkedList();
Stack s = new Stack();
for(String i: item) {
  q.offer(i); // enqueue
  s.push(i);  // push
}
while(q.size() > 0) {
  println("QUEUE:" + q.poll());
}
while(s.size() > 0) {
  println("STACK:" + s.pop());
}

 

2016-09-04 (5)

キューがスタックに近い形で利用可能になっているのが、実感できます。

参考:

  • http://www.atmarkit.co.jp/fjava/javatips/182java064.html ーーGenericsを用いたスタックとキューのサンプルプログラム

Leave a Reply

Your email address will not be published. Required fields are marked *

CAPTCHA


Related Post

12.Map12.Map

Map構造 コレクションクラス Map構造は、キーと値をセットにしたものを1つの要素として管理するデータ構造です。 「HashMap」「TreeMap」の2種類があります。 要素がキーと値で管理されているので、キーを指定して値の取得や更新、削除を行います。 Map構造は、キーによって値を管理するためキーの重複は不可です。 (同じキーがセット(put)された場合は上書きされます。) マップ(HashMap) HashMap は、名前(キー)と値の組み合わせを要素として持つ配列です。 HashMapは格納順は管理されません。キーと値にnullを使用することが可能です。 HashMap hm = new HashMap(); hm.put("Brian Kernighan","A REGULAR EXPRESSION […]

11.List11.List

List構造 コレクションクラス List構造は、要素を順番付けして管理するデータ構造です。 「ArrayList」「LinkedList」の2種類があります。 要素がインデックス(番号)順に並んでいるので、番号を指定して要素の取得、挿入、更新、削除ができます。また、Iteratorや拡張for構文を使って先頭から順番に要素を取得することも出来ます。 ArrayListは要素の取得が早いが挿入や削除が遅い、LinkedListは要素の挿入や削除は早いが取得が遅いという特徴があります。 List構造は、要素の重複は可能です。 リスト(ArrayList) ArrayList は配列を扱う一般的なクラスです。 下記などのメソッドが用意されています。 list.add(o) – オブジェクト o を配列の末尾に追加する list.add(n, o) – オブジェクトを […]

Algorithms and Data StructuresAlgorithms and Data Structures

授業概要  ソートとコレクションを中心にアルゴリズムとデータ構造に関する基本を学習する。 Java言語によるプログラミング技術の基本事項を習得する。 特にアルゴリズムとデータ構造の理解を中心に、講義および演習を行う。 授業の到達目標 ・オブジェクト指向言語の概念を理解するとともに、Javaを用いて課題を解決するスキルを身につける。 ・アプリケーションの開発に必要な概念を理解するとともに、Java言語を用いて実用的なWebアプリケーションの開発が行えるようになる。 事前・事後学習の内容 予習としてMyWasedaに掲載するレジュメの事前読了を求めることがあります。各回の予習には90分~120分かかると想定されます。 授業計画 1: 本講義の目的と進め方について説明する。最終的に作成するアプリケーションの実例を説明する。 2: 基本概念を理解する。Javaのインストールからコマンドライン実行の方法を学ぶ。 3: 基本的なアルゴリズムを学ぶ。 4: 基本的なデータ構造を学ぶ。 5: 探索アルゴリズムを学ぶ。 […]