スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

マルチパラダイム時代におけるデータ構造 第11回 ー キューと押し出す。先入先出のキュー♪

 この記事は、「マルチパラダイム時代におけるデータ構造 第10回 ー 配列オブジェクトとは何か」の続きです。前回は、配列オブジェクトについて解説しました。今回は、キューという名前のデータ構造(オブジェクト)を解説します。
 配列は固定長で格納した順番は関係ありませんでしたが、データの格納順でデータライフサイクルが変わるデータ構造があります。それが今回紹介するキューです。キューは、データの格納順にデータを返します。これによりデータを入れた順番を考慮した、アルゴリズムを実現できるようになります。これから挙げる例をもとに考えてみましょう。
 例えば、整理券を配布するアルゴリズムを考えるとします。この時重要なのは、来た順番に券を配ることです。もし、自分よりも後できた人が、自分よりも先に配布券をもらっていたら誰でも気を悪くします。という事は、データの順番がわかるようなデータ構造があれば便利です。キューはこのような状況で活躍します。
 先入先出(データが発生した順番)を考えれば、キューはすぐに実装できますが、慌てずにテストを用意しましょう。

using System;
using DataStructure;

namespace Test
{
    //配列オブジェクト( Array )をテストする。
    class QueueTest<T> : IDataManagerTest<T>
    {
        //指定したデータが選択可能か否か判定する。
        protected override bool CanSelect(
            IDataManager<T> target,
            int count,
            T value )
        {
            //後で実装する
            return false;
        }

        //全てのテストを実行する。
        public void AllTestExecute(
            Func<Queue<T>> initFunc,
            T one,
            T two )
        {
            this.OneDataLifeCycleTest( initFunc(), one );
            this.TwoDataLifeCycleTest( initFunc(), one, two );
        }
    }
}

using System;
using DataStructure;

namespace Test
{
    class TestProgram
    {
        static void Main()
        {
            ConsCellTest();
            ArrayTest();
            QueueTest();
            Console.ReadLine();
        }

        //関係のないプログラムは省略・・・

        //キュー(Queue)に対するテストする。
        private static void QueueTest( )
        {
            TestFramework<QueueTest<int>>(
                "Queue",
                ( ) => new QueueTest<int>().AllTestExecute(
                    initFunc: ( ) => new Queue<int>(),
                    one: 1,
                    two: 2 ) );
        }
    }
}

選択可能かどうか判定するテストは、キューの扱い方がわからないので、ひとまず偽を返しておきます。このテストをパスするように実装すればOKです。一緒に実装していきましょう。
 キューには独自の用語があります。それは、エンキューデキューです。エンキューはデータを発生させることで、デキューは最初に格納したデータを返して、その後消滅してしまう事です。なぜ取り出したデータを消してしまうのか疑問を持つ人もいるでしょう。それについては、処理の簡素化と資源(リソース)の節約のためです。キューは先入先出なので、前に出してしまったデータを何時までも保持していれば、処理が複雑化しますし、二度と使わないので維持するだけ無駄です。ですから一度取り出したデータは消滅させます。これがわかったらあとは簡単です。さくっと実装できます。

using System;

namespace DataStructure
{
    //先入れ先出し法でデータを管理するオブジェクト(キュー)
    public class Queue<T> : IDataManager<T>
    {
        //データ管理を補助するオブジェクト。
        private IDataFreeManager<T> _element;

        //インスタンスを生成する。
        public Queue( )
        {
            this._element = new ConsCell<T>();
        }

        //データを一つ発生させる。
        public void EnQueue( T element )
        {
            this.Insert( element );
        }

        //データを選択して返しその後削除する。
        public T DeQueue( )
        {
            T result = this.Select();
            this.Delete();
            return result;
        }

        //データの個数。
        public int Count
        {
            get { return this._element.Count; }
        }

        //最初のデータを選択する。
        public T Select( )
        {
            return this._element.Select( 0 );
        }

        //最後尾にデータを発生させる。
        public void Insert( T value )
        {
            this._element.Insert( value, this.Count - 1 );
        }

        //最初のデータを消す。
        public void Delete( )
        {
            this._element.Delete( 0 );
        }
    }
}

これがわかれば先ほどのテストも実装できるはずです。

//指定したデータが選択可能か否か判定する。
protected override bool CanSelect(
    IDataManager<T> target,
    int count,
    T value )
{
    bool canSelect = false;
    var q = ( Queue<T> ) target;
    var temp = new Queue<T>();
    while ( q.Count != 0 ) {
        T result = q.DeQueue();
        temp.EnQueue( result );
        if ( value.Equals( result ) ) {
            canSelect = true;
        }
    }
    target = temp;
    return canSelect;
}

デフォルトコンストラクタが必要なので、コンスセルオブジェクトにデフォルトコンストラクタを追加しました。これでOKといいたいところですが、例外が発生します。何も起こらなテストなんて意味がないのでつまらないですよね♪張り切ってデバッグしましょう♪次回、例外が発生した理由について解説します。
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

プロフィール

インドリ

Author:インドリ
みなさん、はじめまして、
コンニチハ。

ボクは、無限の夢(infinity dream)を持つネタ好きな虹色の鳥インドリ(in dre)です。
色々な情報処理技術を啄ばむから楽しみにしてね。

http://twitter.com/indori
は別人による嫌がらせ行為です。
私とは関係ないので注意して下さい。
次はなりすましブログなどをするかもしれませんが、ここ以外でブログをするつもりがないので、ここ以外にインドリのブログがあったとしても無視してください。


何度言っても分からない人がいるので、ここにコメント欄へ書き込むときの注意事項を書きます。


一、社会人としてのマナーをわきまえましょう。
一、妄想に基づく書き込みを止めてください。
一、暴言の類は書かないで下さい。
一、某誹謗中傷サイトの書き込みは彼らの妄想に基づく書き込みですから無視して、ここへ書き込まないで下さい。
一、コメント書く前に他のコメントよく読んでから行って下さい。
一、言いがかかり等の行為を禁止します。
一、その他常識的に考えて迷惑なコメントはしないで下さい。


以上のルールを守れない人のコメントは削除します。



利用上の注意
ここに紹介してある文章およびプログラムコードは正確であるように心がけておりますが、内容を保証するものではありません。当サイトの内容によって生じた損害については、一切の責任を負いませんので御了承ください。


執筆したCodeZineの記事


【VB.NETで仮想CPUを作ろう】

  1. VB.NETで仮想CPUを作ろう
  2. レジスタの実装
  3. 仮想CPUのGUI化
  4. テストドライバの改良
  5. CPUの基礎動作の実装
  6. MOV命令の実装
  7. ADD命令実装
  8. SUB命令実装
  9. INC命令&DEC命令の実装と命令長
  10. MLU命令の実装とModR/Mについて
  11. DIV命令の実装とイベント設計について
  12. 機械語駆動式 関数電卓を作ろう!
  13. 機械語駆動式 関数電卓を作ろう! 解答編(前半)
  14. 機械語駆動式 関数電卓を作ろう! 解答編(後半)


【仮想ネットワーク実装でTCP/IPを学ぼう】
  1. TCP/IPの基礎と勘所
  2. ネットワークアクセス層の勘所
  3. インターネット層の勘所
  4. トランスポート層の勘所
  5. アプリケーション層の勘所
  6. セキュリティの基礎と仮想ネットワークの仕様
  7. GDI+と独自プロトコルの定義



【並列化】
インテル Parallel Studioを使って並列化プログラミングを試してみた
並列プログラミングの効率的なデバッグを実現する「Parallel Inspector」


【TBBシリーズ】
  1. インテル スレッディング・ビルディング・ブロックの概要
  2. インテルTBBから学ぶループの並列化
  3. スレッドセーフとインテルTBBのコンテナ
  4. インテルTBBのスレッドクラス


【OpenMPシリーズ】
  1. OpenMPの基礎構文
  2. OpenMPの実行時ライブラリと並列ループ
  3. OpenMPのメモリモデルとfork- joinモデル

最近の記事
最近のコメント
月別アーカイブ
カテゴリ
Ada (9)
COBOL (5)
C (9)
C++ (11)
C# (370)
D (25)
Java (8)
Perl (1)
Ruby (14)
PHP (2)
Boo (2)
Cobra (2)
LISP (6)
F# (33)
HTML (0)
XHTML (0)
CSS (0)
XML (0)
XSLT (0)
Scala (4)
WPF (0)
WF (2)
WCF (0)
LINQ (4)
MONO (5)
Linux (0)
MySQL (0)
ブログ内検索
リンク
最近のトラックバック
RSSフィード
ブロとも申請フォーム

この人とブロともになる

QRコード
FC2カウンター
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。