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

11.List11.List

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

4.Data Structure4.Data Structure

データ構造とは データ構造(データこうぞう、英: data structure)は、計算機科学において、データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のことである。 ソフトウェア開発において、データ構造についてどのような設計を行うかは、プログラム(アルゴリズム)の効率に大きく影響する。そのため、さまざまなデータ構造が考え出されている。 配列 配列(はいれつ)は同じ型の変数を複数取り扱うために考案された仕組みです。配列は変数名にカッコ付きの整数を添えることで順番を決め,要素を区別します。配列によってまとめられた,一つひとつの変数を要素(ようそ)と呼びます。要素を区別するために添えた数字を添字(そえじ)と呼びます。 配列は大変シンプルで,コレクションクラスに比較すると必要とするメモリ量が少なく,アクセスが高速なことがメリットです。データを単純に格納して,順番に参照する程度の用途であれば,コレクションクラスに比較して配列のほうが有利です。 最も基本的な配列の使用例を次に示します。配列の要素数を含めて宣言し,配列の添字を明記して要素に値を代入し,添字を指定して要素の値を呼び出します。 String names[] = {“Tim Bray”,        // 0番目の要素 “Brian Kernighan”, // 1番目の要素 […]

3.Algorithms3.Algorithms

アルゴリズムとは アルゴリズム(英: algorithm)とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。「算法(さんぽう)」と訳されることもある。 基本的なアルゴリズム 順次 条件判定と分岐 (if, switch) 繰り返し (while, for)   順次 順次実行構造は,上に書かれた命令が先に実行され,下に書かれた命令が後に実行される構造のことです。なるべくこのようなシンプルで自然な構造になるようコードを書くべきです。 典型的な順次実行の例として,GSWPよりサンプルコードを引用します。 // Example 03-13 from "Getting […]