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

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

C++ | 26 | キューとスタック

C++ プログラミング チュートリアル

↓↓クリックして頂けると励みになります。

ランキング参加中
プログラミング



【25 | リストとファイル入出力】 << 【ホーム】 >> 【27 | ファイルへの書き込み】


キューとスタック
キューとスタック



C++におけるキュー（Queue）とスタック（Stack）は、データを保持するための抽象的なデータ構造です。
これらは、データの挿入と取り出しの方法によって異なります。

キュー（Queue）:
キューは、先入れ先出し（FIFO：First In, First Out）のデータ構造です。
つまり、最初に追加された要素が最初に取り出されます。
キューは、要素の挿入が末尾に行われ、要素の取り出しは先頭から行われます。

スタック（Stack）:
スタックは、後入れ先出し（LIFO：Last In, First Out）のデータ構造です。
つまり、最後に追加された要素が最初に取り出されます。
スタックは、要素の挿入と取り出しが一方の端（通常は先頭）からのみ行われます。

これらのデータ構造は、データを一時的に保持し、特定の順序で処理する場合に非常に便利です。
例えば、グラフの幅優先探索（BFS）でキューが使用され、深さ優先探索（DFS）でスタックが使用されることがあります。


Visual Studio Codeで以下の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;
	}
}

int 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("Data.txt",std::ios::in);

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

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

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

		s4 = (char *)malloc( strlen(buf4) + 1 );
		strcpy(s4, 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()関数でデータを取り出して、取り出したデータを消去しています。
実行結果はデータが逆順に出力されます。
これがスタックの動作です。


このサンプルプログラムは以下の「Data.txt」ファイルを読み込みます。
【Data.txt】

yamada 2001 1 1 70 65 15 15
suzuki 2001 2 3 80 90 10 13
satou 2001 3 2 80 60 13 12
tanaka 2000 11 1 65 70 12 15



プログラムを実行して動作を確認してください。

~/Desktop/Programming/CPP $ cd "/Users/**/Desktop/Programming/CPP/" && g++ QUE_STUCK.cpp -o QUE_STUCK && "/Users/**
/Desktop/Programming/CPP/"QUE_STUCK

1
11
2000
tanaka
2
3
2001
satou
3
2
2001
suzuki
1
1
2001
yamada



Visual Studio Codeで以下の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;
     	}
}

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

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

	while (fin >> buf) {

		s = (char *)malloc(strlen(buf) + 1);
		strcpy(s, 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」）の実行結果です。
このサンプルプログラムは「Welcome.txt」ファイルを読み込みます。
【Welcome.txt】

#include <iostream>

int main() {

	std::cout << "ようこそ！C++の世界へ！";
	std::cout << std::endl;

}


~/Desktop/Programming/CPP $ cd "/Users/**/Desktop/Programming/CPP/" && g++ QUE_STUCK2.cpp -o QUE_STUCK2 && "/Users/**/Desktop/Programming/CPP/"QUE_STUCK2

#include
<iostream>
int
main()
{
std::cout
<<
"ようこそ！C++の世界へ！";
std::cout
<<
std::endl;
}



スタックとして使う場合のプログラムを以下に書いておきます。

#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;
     	}
}

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

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

	while (fin >> buf) {

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

		add_stuckque(s);

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



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

~/Desktop/Programming/CPP $ cd "/Users/**/Desktop/Programming/CPP/" && g++ tempCodeRunnerFile.cpp -o tempCodeRunnerFile 
&& "/Users/**/Desktop/Programming/CPP/"tempCodeRunnerFile

}
std::endl;
<<
std::cout
"ようこそ！C++の世界へ！";
<<
std::cout
{
main()
int
<iostream>
#include



【25 | リストとファイル入出力】 << 【ホーム】 >> 【27 | ファイルへの書き込み】





↓↓クリックして頂けると励みになります。

ランキング参加中
プログラミング

YAE C5 CLINIC(札幌美容クリニック)

関連記事（外部サイト）