学生向けプログラミング入門 | 無料

学生向けにプログラミングを無料で解説。Java、C++、Ruby、PHP、データベース、Ruby on Rails, Python, Django

C++プログラミング入門その29 キュー・スタック

>>この記事には書き直した新しいページがあります。<<


<<前  [TOP]  次>>


Visual Studioで新規プロジェクトを作り、以下のcppファイルを作成して下さい。


【QUE_STUCK.cpp】

#include<iostream>
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#include<fstream>

/*header of STUCK*/
typedef struct STUCK {
	struct STUCK *prev;
	void *data;
}STUCK;

STUCK *newObj(void *data);
void *get_stuck(void);
void add_stuck(void *data);

static STUCK *First=NULL;

STUCK *newObj(void *data){
        STUCK *p;
        p = (STUCK *)malloc(sizeof(STUCK));
        p->prev=NULL;
        p->data=data;
        return p;
}

void *get_stuck(void) {
	STUCK *lp = First;
	void *data;

	if(lp ==NULL) {		/*データにキューがないとき*/
		return NULL;
	}
	data = lp->data;
	lp = lp->prev;
	free(First);
	First = lp;
	return data;
}

void add_stuck(void *data) {
	STUCK *lp = First;
	STUCK *newl,*p;

	if(lp == NULL) {	/*リストが空なら*/
		First = newObj(data);
	}
	else {
		p=lp;
        newl = newObj(data);
        newl->prev = p;
		lp=newl;
		First = newl;
	}
}

void main() {

	char *s1;
	char *s2;
	char *s3;
	char *s4;

	float zenki;
    float kouki;
    float report;
    float shutsuseki;

	char buf1[512];
	char buf2[512];
	char buf3[512];
	char buf4[512];

	int i=0;

	std::ifstream fin;
	fin.open("C:\\test\\Data.txt",std::ios::in);

	while (fin >> buf1 >> buf2  >> buf3 >> buf4 >> zenki >> kouki >> report >> shutsuseki ){
		s1 = (char *)malloc( strlen(buf1) + 1 );
		strcpy_s(s1, strlen(buf1) + 1,  buf1);

		s2 = (char *)malloc( strlen(buf2) + 1 );
		strcpy_s(s2, strlen(buf2) + 1, buf2);

		s3 = (char *)malloc( strlen(buf3) + 1 );
		strcpy_s(s3, strlen(buf3) + 1, buf3);

		s4 = (char *)malloc( strlen(buf4) + 1 );
		strcpy_s(s4, strlen(buf4) + 1, buf4);

		add_stuck(s1);
		add_stuck(s2);
		add_stuck(s3);
		add_stuck(s4);
	}
	for ( ; First;) {
		std::cout <<(char *)( First->data) << std::endl;
		get_stuck();
	}
}



リストで何度も使ってきたように、構造体で新しい型を定義することができます。

struct List {
    struct List *next;
    void *data;
};

これは、新しいstruct List型という型を作っていることになるのですが、表現方法としてはintなどに対して、struct Listと書くのはあまり型という感じがしないかもしれません。
そこで、このstruct Listを省略して書く方法が用意されています。
このため新しい宣言がtypedfで、次のようになります。

typedf struct List LIST;

このように書くことで、新しい型名LISTが定義されます。
以降は、struct Listの変わりにLISTが使えるようになります。

LIST *newl;

なお、2度に分けて書かずに以下のように書くこともできます。

typed struct List {
    struct List *next;
    void *data;
 } LIST;

この際、LISTは変数名ではなく、新しい型の名前であることに注意してください。


キューは入出力機構の実装によく用いられるメカニズムで、最初に入ってきたデータから処理し、その後で入ってきたデータは、最後の列に並んでいくという処理をします。


まず、データが入ってくる場合ですが、入ってくるデータはすべてリストの最後に付け加えます。
つまり、キューからデータを取り出す場合には必ず、リストの先頭から取り出すようにします。
ヘッダーは次のようになります。

/* header of QUE */

 typed struct Que {
    struct Que *next;
    void *data;
 } QUE;

 static QUE *First;

ここでtypedfを用いて、QUEを作っていますが、リストの最初の要素の場所をどうやって保持するかという点がリストの実現方法と少し異なります。
この例では、最初からモジュール内部にFirstという静的外部変数 staticを用意しています。
このstaticを宣言すると、モジュールの外側からは、この変数が利用できなくなります。
もちろん、モジュール内部では、普通にいつも通り使えます。


キューからデータを取り出す関数は、最初の要素からデータを取り出し、その要素をリストから取り除きます。
ただし、もしキューにある要素がない場合は、NULLを返します。

void *get_que(void) {
    QUE *lp = First;
    void *data;

    if(lp==NULL){    /* データがキューにないとき */
        return NULL;
    }
    data = lp->data;
    lp = lp->next;
    free(First);
    First=lp;
    return data;
}

次に、キューに一個新たにデータを追加する関数では、リストの最後にデータを作って追加します。
キューにデータがない場合にのみ、Firstを更新します。

void add_que(void *data) {
    QUE *lp = First;

    if(lp!=NULL) {
        while(lp->next!=NULL) {
            lp=lp->next;
        }
        lp = lp->next = (QUE*)malloc(sizeof(QUE));
    }
    else {
        lp = First=(QUE*)malloc(sizeof(QUE));
    }
    lp->data = data;
    lp->next = NULL;
    return;
 }



スタックは机の上に本を重ねて置いていくようなものだと考えます。
つまり、最初に置かれた本は一番下にあり、スタックに本を積んでいき、取り出すときには一番上に置かれた本が取り出されます。
従って、最初に置かれた本は最後に取り出されることになります。


スタックを実現するには、リストの最後にデータを追加し、常にリストの最後のデータを取り出すようにすればよいです。


サンプルプログラムについて少し説明します。
このプログラムは、スタックをリストを使って実装しています。


get_stuck()関数でデータを取り出して、取り出したデータを消去しています。
実行結果は、データが逆順に出力されます。
これがスタックの動作です。





Visual Studioで新規プロジェクトを作り、以下のcppファイルを作成して下さい。


【QUE_STUCK2.cpp】

#include<iostream>
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#include<fstream>

/*header of STUCKQUE*/
typedef struct STUCKQUE {
	struct STUCKQUE *prev;
	struct STUCKQUE *next;
	void *data;
}STUCKQUE;

STUCKQUE *newObj(void *data);
void *get_stuck(void);
void *get_que(void);
void add_stuckque(void *data);

static STUCKQUE *First=NULL;
static STUCKQUE *After=NULL;

STUCKQUE *newObj(void *data){
        STUCKQUE *p=NULL;
        p = (STUCKQUE *)malloc(sizeof(STUCKQUE));
        p->prev=NULL;
		p->next=NULL;
        p->data=data;
        return p;
}
void *get_stuck(void) {
        STUCKQUE *lp = After;
        void *data;
        if(lp ==NULL) {         /*データにキューがないとき*/
                return NULL;
        }
        data = lp->data;
        lp = lp->prev;
        free(After);
        After = lp;
        return data;
}

void *get_que(void) {
        STUCKQUE *lp = First;
        void *data;
        if(lp==NULL) { 		/*データがないとき*/
                return NULL;
        }
        data = lp->data;
        lp = lp->next;
        free(First);
        First = lp;
        return data;
}

void add_stuckque(void *data) {
	STUCKQUE *newl = NULL, *p = NULL;
	if(First == NULL) {	/*リストが空なら*/
		First = newObj(data);
	}
	if(After == NULL) {     /*リストが空なら*/
                After = newObj(data);
     	}
	else {
		p=First;
		newl=newObj(data);
        	while(p->next!=NULL){
                	p=p->next;
        	}
        	p->next=newl;
        	newl->prev=p;
        	After=newl;
     	}
}

void main() {
	char *s;
	char buf[512];

	std::ifstream fin;
	fin.open("C:\\test\\Welcome.txt", std::ios::in);

	while (fin >> buf) {

		s = (char *)malloc(strlen(buf) + 1);
		strcpy_s(s, strlen(buf) + 1, buf);

		add_stuckque(s);

	}
	/* キューとて使うとき */
	for (; First;) {
		std::cout << (char *)(First->data) << std::endl;
		get_que();
	}
}



双方向リンクリストを使うと、キュートしても、スタックとしても使えるようなデータ構造が記述できます。
これを仮にスタックキューと呼びます。
スタックキューでは、便宜上、常にデータを取り出す際には、最後尾のデータが取り出されるものしています。
従って、スタックとして使うときには、最後尾にデータを追加し、キューとして使うときには、最前列にデータを追加すればよいです。
このようなスタックキューを設計し、モジュールとして使えるようにしました。


このサンプルプログラムではキューとして使う場合の記述をしています。
もし、スタックとして使用する場合は、最後の部分を以下のように書き換えます。

/* スタックとして使うとき */
	for ( ; After;) {
            	std::cout <<(char *)( After->data)<< std::endl;
		get_stuck();
    	}
}



キューとして使う場合([QUE_STUCK2.cpp])の実行結果です。



スタックとして使用する場合の実行結果です。



<<前  [TOP]  次>>