配列をつかったスタック
配列を使って,C言語で作成するようなスタックを作る.ここで紹介するJavaプログラムは,Java言語で書かれてはいるが,オブジェクト指向に則っていないプログラムである.則っていない,すなわち,C言語で表すことができるプログラムから,オブジェクト指向に則った記述に変えていくことにする.
Stackクラスの中に,スタックのデータを入れる配列stackと,配列内に入っているデータの数を覚えておくvolumeを用意する.これらの配列とデータ数を使って,データを入れるサブルーチンpushとデータを取り出すサブルーチンpopを作る.
#include <stdio.h>
#define defaultSize 5
int stack[defaultSize];
int volume = 0;
//データ追加関数
void push(int number)
{
if (defaultSize > volume)
{
stack[volume] = number;
volume++;
printf("%d inserted\n", number);
}
else
{
printf("over flow!\n");
}
}
//データ取得関数
int pop()
{
int returnValue = 0;
if (volume > 0)
{
returnValue = stack[volume - 1];
stack[volume - 1] = 0;
volume--;
}
else
{
printf("under flow!\n");
returnValue = -1;
}
return returnValue;
}
//状態表示関数
void printStack()
{
printf("|");
for (int i = 0; i < defaultSize; i++)
{
printf("%d",stack[i]);
printf("|");
}
printf("\n");
}
void main()
{
push(10); printStack();
push(20); printStack();
push(30); printStack();
push(40); printStack();
push(50); printStack();
push(60); printStack();
printf("%d poped\n", pop()); printStack();
printf("%d poped\n", pop()); printStack();
printf("%d poped\n", pop()); printStack();
printf("%d poped\n", pop()); printStack();
printf("%d poped\n", pop()); printStack();
printf("%d poped\n", pop()); printStack();
}
class Stack
{
static int defaultSize = 5;
static int stack[] = new int[defaultSize];
static int volume = 0;
//データ追加関数
static void push(int number)
{
if(stack.length > volume)
{
stack[volume] = number;
volume++;
System.out.printf("%d inserted\n",number);
}
else
{
System.out.printf("over flow!");
}
}
//データ取得関数
static int pop()
{
int returnValue = 0;
if(volume > 0)
{
returnValue =stack[volume -1];
stack[volume -1] = 0;
volume--;
}
else
{
System.out.printf("under flow!");
returnValue = -1;
}
return returnValue;
}
//状態表示関数
static void printStack()
{
System.out.printf("|");
for(int i=0; i < stack.length; i++)
{
System.out.printf("%d", stack[i]);
System.out.printf("|");
}
System.out.printf("\n");
}
public static void main(String[] args)
{
push(10);printStack();
push(20);printStack();
push(30);printStack();
push(40);printStack();
push(50);printStack();
push(60);printStack();
System.out.printf("%d poped\n",pop());printStack();
System.out.printf("%d poped\n",pop());printStack();
System.out.printf("%d poped\n",pop());printStack();
System.out.printf("%d poped\n",pop());printStack();
System.out.printf("%d poped\n",pop());printStack();
System.out.printf("%d poped\n",pop());printStack();
}
}
main関数から,データを追加する関数:push,データを取得する関数:popを呼び出して,データの追加,データの取得を行っている.データを追加したあと,その都度,スタックの状態を表示して,データの格納状態を確認している.
ここで対象としているデータは正の整数のみとする.
push関数では,追加するデータを引数にとる.引数にて渡されたデータを,既に格納されているデータ群に隣接する最上位の場所に格納する.データを格納することができない場合には,falseを返す.
pop関数では,最近追加されたデータを取り出す.返り値として,取り出したデータを取得する.データを取り出すことができない場合には(-1)を返す.
サブルーチンの修飾子に「static」とついているが,これは,クラスで固有の変数や関数であることを定義するために用いている.Mainクラスを単独で実行するために必要であり,オブジェクトの生成タイミングなどがその理由である.ただし,その理由の詳しい説明については,クラスの実体化を学んだ頃に,staticがある状態とstaticがない状態の違いを詳しく述べる.
実行例
10inserted
|10|0|0|0|0|
20inserted
|10|20|0|0|0|
30inserted
|10|20|30|0|0|
40inserted
|10|20|30|40|0|
50inserted
|10|20|30|40|50|
over flow!
|10|20|30|40|50|
50
|10|20|30|40|0|
40
|10|20|30|0|0|
30
|10|20|0|0|0|
20
|10|0|0|0|0|
10
|0|0|0|0|0|
under flow!
-1
|0|0|0|0|0|
演習
上記の「配列を使ったスタック」と同様に,配列を用いたデータ構造にて,「配列を使ったキュー」のJavaプログラムを作成せよ.
キューの形式は,常にqueue[0]に最古のデータが位置しているように,データを取り出した時には,データ全体を整理することにする.
配列を使ったキュー.
データ構造
- キューの容量:5個に固定
- キューに保存するデータ型:整数
- 保存データ個数:その時々の保存データ個数を覚えておく変数を用意
関数
キュー追加関数
- 関数名:enqueue
- 引数:追加する整数値
- 戻り値:追加成功(true),追加失敗(false)
キュー取得関数
- 関数名:dequeue
- 引数:なし
- 戻り値:取り出した値.取り出すデータがないときは(-1)
キュー表示関数
- 関数名:printQueue
- 引数:なし
- 戻り値:なし
メイン関数
キューの動作が正常であることを十分確認できるように,関数を呼び出して確かめられる内容にする.