スタックと待ち行列
前回の授業では、リストの先頭にデータを挿入する処理と、末尾に追加する処理について説明したが、この応用について説明する。
計算処理中に一時的なデータの保存として、スタック(stack)と待ち行列・キュー(queue)がよく利用される。それを配列を使って記述したり、任意の大きさにできるリストを用いて記述することを示す。
スタック
配列を用いたスタック
一時的な値の記憶によく利用されるスタック(stack)は、データの覚え方の特徴からLIFO( Last In First out )とも呼ばれる。配列を使って記述すると以下のようになるであろう。
import java.util.*;
public class Main {
static final int STACK_SIZE = 10 ;
static int[] stack = new int[ STACK_SIZE ] ;
static int sp = 0 ;
static void push( int x ) {
stack[ sp++ ] = x ;
}
static int pop() {
return stack[ --sp ] ;
}
public static void main(String[] args) throws Exception {
push( 11 ) ;
push( 22 ) ;
push( 33 ) ;
System.out.println( pop() ) ;
System.out.println( pop() ) ;
System.out.println( pop() ) ;
}
}
配列を使った Stack をオブジェクト指向で記述するなら、以下のように書ける。
import java.util.*;
class Stack {
static final int STACK_SIZE = 10 ;
int[] array ;
int sp ;
Stack() {
this.array = new int[ STACK_SIZE ] ;
this.sp = 0 ;
}
void push( int x ) {
array[ sp++ ] = x ;
}
int pop() {
return array[ --sp ] ;
}
} ;
public class Main {
public static void main(String[] args) throws Exception {
Stack stack = new Stack() ;
stack.push( 11 ) ;
stack.push( 22 ) ;
stack.push( 33 ) ;
System.out.println( stack.pop() ) ;
System.out.println( stack.pop() ) ;
System.out.println( stack.pop() ) ;
}
}
C言語で書いた場合
#define STACK_SIZE 32
int stack[ STACK_SIZE ] ;
int sp = 0 ;
void push( int x ) { // データをスタックの一番上に積む
stack[ sp++ ] = x ;
}
int pop() { // スタックの一番うえのデータを取り出す
return stack[ --sp ] ;
}
void main() {
push( 1 ) ; push( 2 ) ; push( 3 ) ;
printf( "%d\n" , pop() ) ; // 3
printf( "%d\n" , pop() ) ; // 2
printf( "%d\n" , pop() ) ; // 1
}
++,–の前置型と後置型の違い
// 後置インクリメント演算子 int i = 100 ; printf( "%d" , i++ ) ; // これは、 printf( "%d" , i ) ; i++ ; // と同じ。100が表示された後、101になる。 // 前置インクリメント演算子 int i = 100 ; printf( "%d" , ++i ) ; // これは、 i++ ; printf( "%d" , i ) ; // と同じ。101になった後、101を表示。
リスト構造を用いたスタック
しかし、この中にSTACK_SIZE以上のデータは貯えられない。同じ処理をリストを使って記述すれば、配列サイズの上限を気にすることなく使うことができるだろう。では、リスト構造を使ってスタックの処理を記述してみる。
import java.util.*;
class ListNode {
int data ;
ListNode next ;
ListNode( int d , ListNode n ) {
this.data = d ;
this.next = n ;
}
}
public class Main {
static ListNode stack = null ;
static void push( int x ) {
stack = new ListNode( x , stack ) ;
}
static int pop() {
int ans = stack.data ;
stack = stack.next ;
return ans ;
}
public static void main(String[] args) throws Exception {
push( 1 ) ;
push( 2 ) ;
push( 3 ) ;
System.out.println( pop() ) ;
System.out.println( pop() ) ;
System.out.println( pop() ) ;
}
}
struct List* stack = NULL ;
void push( int x ) { // リスト先頭に挿入
stack = cons( x , stack ) ;
}
int pop() { // リスト先頭を取り出す
int ans = stack->data ;
struct List* d = stack ;
stack = stack->next ; // データ 0 件で pop() した場合のエラー対策は省略
free( d ) ;
return ans ;
}
オブジェクト指向っぽく書くならば、下記のようになるだろう。初期状態で stack = null にしておくと、stack.push() ができないので、stack の先頭には、ダミーデータを入れるようにプログラムを書くと以下のようになるだろう。
import java.util.*;
class ListNode {
int data ;
ListNode next ;
ListNode( int d , ListNode n ) {
this.data = d ;
this.next = n ;
}
ListNode() { // stack初期化用のコンストラクタ
this.data = -1 ;
this.next = null ;
}
void push( int x ) {
this.next = new ListNode( x , this.next ) ;
}
int pop() {
int ans = this.next.data ;
this.next = this.next.next ;
return ans ;
}
} ;
public class Main {
public static void main(String[] args) throws Exception {
ListNode stack = new ListNode() ; // stack初期化用のコンストラクタを使う
stack.push( 1 ) ;
stack.push( 2 ) ;
System.out.println( stack.pop() ) ;
System.out.println( stack.pop() ) ;
}
}
キュー(QUEUE)
２つの処理の間でデータを受け渡す際に、その間に入って一時的にデータを蓄えるためには、待ち行列(キュー:queue)がよく利用される。 データの覚え方の特徴からFIFO(First In First Out)とも呼ばれる。
配列を用いたQUEUE / リングバッファ
配列にデータを入れる場所(wp)と取り出す場所のポインタ(rp)を使って蓄えれば良いが、配列サイズを超えることができないので、データを取り出したあとの場所を循環して用いるリングバッファは以下のようなコードで示される。
import java.util.*;
public class Main {
static final int QUEUE_SIZE = 32 ;
static int[] queue = new int[ QUEUE_SIZE ] ;
static int wp = 0 ;
static int rp = 0 ;
static void put( int x ) {
queue[ wp++ ] = x ;
if ( wp >= QUEUE_SIZE ) // wp = wp % QUEUE_SIZE ; or wp = wp & (QUEUE_SIZE - 1) ;
wp = 0 ;
}
static int get() {
int ans = queue[ rp++ ] ;
if ( rp >= QUEUE_SIZE ) // rp = rp % QUEUE_SIZE ; or rp = rp & (QUEUE_SIZE - 1) ;
rp = 0 ;
return ans ;
}
public static void main(String[] args) throws Exception {
// Your code here!
put( 1 ) ;
put( 2 ) ;
put( 3 ) ;
System.out.println( get() ) ;
System.out.println( get() ) ;
System.out.println( get() ) ;
}
}
#define QUEUE_SIZE 32
int queue[ QUEUE_SIZE ] ;
int wp = 0 ; // write pointer(書き込み用)
int rp = 0 ; // read pointer(読み出し用)
void put( int x ) { // 書き込んで後ろ(次)に移動
queue[ wp++ ] = x ;
if ( wp >= QUEUE_SIZE ) // 末尾なら先頭に戻る
wp = 0 ;
}
int get() { // 読み出して後ろ(次)に移動
int ans = queue[ rp++ ] ;
if ( rp >= QUEUE_SIZE ) // 末尾なら先頭に戻る
rp = 0 ;
return ans ;
}
void main() {
put( 1 ) ; put( 2 ) ; put( 3 ) ;
printf( "%d\n" , get() ) ; // 1
printf( "%d\n" , get() ) ; // 2
printf( "%d\n" , get() ) ; // 3
}
このようなデータ構造も、get() の実行が滞るようであれば、wp が rp に循環して追いついてしまう。このため、上記コードはまだエラー対策としては不十分である。どのようにすべきか？
リスト構造を用いたQUEUE
前述のリングバッファもget()しないまま、配列上限を越えてput()を続けることはできない。
この配列サイズの上限問題を解決したいのであれば、リスト構造を使って解決することもできる。この場合のプログラムは、以下のようになるだろう。
import java.util.*;
class ListNode {
int data ;
ListNode next ;
ListNode( int d , ListNode n ) {
this.data = d ;
this.next = n ;
}
} ;
public class Main {
static ListNode top = new ListNode( -1 , null ) ;
static ListNode tail = top ;
static void put( int x ) {
tail.next = new ListNode( x , null ) ;
tail = tail.next ;
}
static int get() {
int ans = top.next.data ;
top.next = top.next.next ;
return ans ;
}
public static void main(String[] args) throws Exception {
put( 1 ) ;
put( 2 ) ;
put( 3 ) ;
System.out.println( get() ) ;
System.out.println( get() ) ;
System.out.println( get() ) ;
}
}
Javaで書かれた ListNode を用いた待ち行列のイメージ図は下記のように示される。
struct List* queue = NULL ;
struct List** tail = &queue ;
void put( int x ) { // リスト末尾に追加
*tail = cons( x , NULL ) ;
tail = &( (*tail)->next ) ;
}
int get() { // リスト先頭から取り出す
int ans = queue->data ;
struct List* d = queue ;
queue = queue->next ;
free( d ) ;
return ans ;
}
ただし、上記のプログラムは、データ格納後にget()で全データを取り出してしまうと、tail ポインタが正しい位置になっていないため、おかしな状態になってしまう。
また、このプログラムでは、rp,wp の2つのポインタで管理することになるが、 2重管理を防ぐために、リストの先頭と末尾を1つのセルで管理する循環リストが使われることが多い。
理解確認
- 配列を用いたスタック・待ち行列は、どのような処理か？図などを用いて説明せよ。
- リスト構造を用いたスタック・待ち行列について、図などを用いて説明せよ。
- スタックや待ち行列を、配列でなくリスト構造を用いることで、どういう利点があるか？欠点があるか説明せよ。
- 配列を用いたリングバッファが用いられている身近な例にはどのようなものがあるか？
- 配列を用いたリングバッファを実装する場合配列サイズには 2n 個を用いることが多いのはなぜだろうか？
リスト処理のレポート課題(前期期末)
プログラムは書いて・動かして・間違って・直す が重要ということで、以下に前期期末試験前までに取り組むレポート課題をしめす。
レポート課題(プログラム例)
Java を用いて、後に示すデータ処理をするためのリスト構造を定義し、与えられたデータを追加していく処理を作成せよ。
課題の説明用に、複素数のリスト構造を定義し、指定した絶対値以下の複素数を抜き出す関数をつくった例を示す。
import java.util.* ;
class ComplexListNode {
double re ;
double im ;
ComplexListNode next ;
ComplexListNode( double r , double i , ComplexListNode n ) {
this.re = r ;
this.im = i ;
this.next = n ;
}
} ;
public class Main {
// 先頭からデータを挿入する方式
static ComplexListNode top = null ;
// 全リストを表示する処理
static void print( ComplexListNode p ) {
for( ; p != null ; p = p.next ) {
System.out.println( "(" + p.re + ")+j(" + p.im + ")" ) ;
}
}
// top に要素を追加する処理(先頭に入れる)
static void add( double r , double i ) {
top = new ComplexListNode( r , i , top ) ;
}
// 特定のデータを対象にした処理の例
static ComplexListNode filter_lessthan( ComplexListNode p , double v_abs ) {
ComplexListNode ans = null ;
for( ; p != null ; p = p.next ) {
if ( Math.sqrt( p.re * p.re + p.im * p.im ) <= v_abs )
ans = new ComplexListNode( p.re , p.im , ans ) ;
}
return ans ;
}
public static void main(String[] args) throws Exception {
add( 1.0 , 2.0 ) ;
add( -1.0 , -1.0 ) ;
add( 2.0 , -1.0 ) ;
add( 1.0 , 0 ) ;
print( top ) ;
ComplexListNode less_than_2 = filter_lessthan( top , 2 ) ;
System.out.println( "less than 2" ) ;
print( less_than_2 ) ;
}
}
((( 実行結果の例 )))
(1.0)+j(0.0)
(2.0)+j(-1.0)
(-1.0)+j(-1.0)
(1.0)+j(2.0)
less than 2
(-1.0)+j(-1.0)
(1.0)+j(0.0)
レポート内容
上記のプログラムをまねて、以下のレポート課題を作成すること。テーマは ((出席番号-1)%3+1) を選択すること。
- 年号のデータが、年号の名称と年号の始まりの年月日がYYYYMMDD形式で
- “Meiji”,18681023
- “Taisho”,19120730
- “Showa”,19261225
- “Heisei”,19890108
- “Reiwa”,20190501
の様に与えられる。このデータ構造を覚えるリスト構造を作成せよ。また ListNode のデータで、西暦の日付のリストが seireki_list = new ListNode( 19650207, new ListNode( 20030903 , null ) ) ; のように与えられたら、そのデータを和暦で表示するプログラムを作成せよ。 (参考2023年前期期末)
- 市町村名,月,日,最高気温,最低気温のデータが、
- “fukui”,8月,4日,27.6℃,22.3℃
- “fukui”,8月,5日,31.5℃,23.3℃
- “fukui”,8月,7日,34.7℃,25.9℃
- “obama”,8月,6日,34.2℃,23.9℃
の様に与えられる。このデータ構造で覚えるリスト構造を作成せよ。また、この中から真夏日(最高気温が30℃以上)でかつ熱帯夜(最低気温が25℃)の日のリストを抽出し表示するプログラムを作成せよ。(参考2022年前期期末)
- ホスト名と、IPアドレス(0～255までの8bitの値✕4個で与えるものとする)のデータ構造で、
- “www.fukui-nct.ac.jp”,104,215,54,205
- “perrine.tsaitoh.net”,192,168,11,2
- “dns.fukui-nct.ac.jp”,10,10,21,51
- “dns.google.com”,8,8,8,8
の様に与えられる。このデータ構造をリスト構造で覚えるプログラムを作成せよ。また、この中からプライベートアドレスのリストを抽出し表示するプログラムを作成せよ。プライベートアドレスは 10.x.x.x, 172.16～31.x.x,192.168.x.x とする。(参考2019年前期期末)
プログラムを作るにあたり、リスト構造には add( 与えられたデータ… ) のように呼び出してリストに追加すること。この時、生成されるリストが、登録の逆順になるか(先頭に挿入)、登録順(末尾に追加)になるかは、自分の理解度に応じて選択すること。抽出する処理を書く場合も登録順序どおりにするかは自分の理解度に応じて選べばよい。
また、理解度に自信がある人は、add() などの処理を「オブジェクト指向」のように記述する方法を検討すること。
あくまで、リスト構造の理解を目的とするため、ArrayList<型> , LinkedList<型> のようなクラスは使わないこと。(ただし考察にて記述性の対比の対象として使うのはOK。複素数の場合の LinkedList を使った例を以下に示す。)
import java.util.* ;
import java.util.stream.Collectors ;
class Complex {
double re ;
double im ;
Complex( double r , double i ) {
this.re = r ;
this.im = i ;
}
public double abs() {
return Math.sqrt( re * re + im * im ) ;
}
@Override
public String toString() {
return "(" + re + ")+j(" + im + ")" ;
}
} ;
public class Main {
public static LinkedList<Complex> top = new LinkedList<Complex>() ;
// 絶対値が指定した値以下の要素だけを集める関数
public static LinkedList<Complex> filter_lessthan(
LinkedList<Complex> list , double v_abs ) {
var ans = new LinkedList() ;
for( var c : list ) {
if ( Math.sqrt( c.re * c.re + c.im * c.im ) <= v_abs )
ans.add( c ) ;
}
return ans ;
}
public static void main( String[] args ) throws Exception {
// リストに複素数を追加
top.add( new Complex( 1.0 , 2.0 ) ) ;
top.add( new Complex( -1.0 , -1.0 ) ) ;
top.add( new Complex( 2.0 , -1.0 ) ) ;
top.add( new Complex( 1.0 , 0 ) ) ;
for( var c : top ) {
System.out.println( c ) ;
}
System.out.println( "---" ) ;
// static な関数でフィルタリング
for( var c : filter_lessthan( top , 2.0 ) ) {
System.out.println( c ) ;
}
/* Stream API を使ってフィルタリング
for( var c : top.stream() // LinkedList を Stream に変換
.filter( c->c.abs() < 2.0 ) // filter条件をラムダ式で渡す
.collect( Collectors.toList() ) // Collectorsで結果を集める
) {
System.out.println( c ) ;
}
*/
}
}
- LinkedListを使ったプログラム例(Paiza.io)