第 5 回 キュー、スタック

本日の内容

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

5-1. 動的な領域確保

C 言語では変数の宣言は常に関数の先頭に書く必要があります(C++ や Java では使う前であればどこでも宣言できます)。 また配列変数は常にあらかじめサイズが決められていました。 C 言語で、手続きが始まった後に変数領域を確保することは可能でしょうか?

このために用意されているのが、malloc 関数です。 利用する時は stdlib.h ヘッダファイルを読み込む必要があります。 malloc 関数は引数にサイズを指定するとそのメモリを動的に確保して、その メモリの先頭番地をポインタの形で返す関数です。 戻ってくる値は (void *) 型のポインタで、適切なポインタに代入できます。 また、確保した領域を使い終えたら free 関数で解放する必要 があります。 解放をきちんとやらないとメモリの利用状況が不安定になります。この状態を メモリリークと言います。 解放しないとプログラムが突然終了したり、 OS が不安定になったりしますの で、このmalloc と free は気をつけて使う必要があります。 但し、プログラムが終了する時は、 OS が free の処理をします。

例えば、二つの文字列つなげるのに、あらかじめ多めに領域を取らずに動的に 割り当てるには次のようにします。 なお処理の途中で malloc が領域確保に失敗した時は NULL が返ります。 


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void){
  char x[]="abcd"; /* 配列は領域を確保する */
  char y[]="efgh";
  char *z;         /* ポインタは領域を確保しない */
  if((z=malloc((strlen(x)+strlen(y)+1)*sizeof(char))==NULL){
    fprintf(stderr,"領域を確保できませんでした\n");
    return 1;
  }
  strcpy(z,x);
  strcat(z,y);
  printf("文字列 %s と %s をつなげると %s。\n",x,y,z);
  free(z);
  return 0;
}

なお、プログラム中でエラーを発生する場合、標準出力にエラーメッセージを 書かず、必ず標準エラー出力に書いて下さい。 以下に各言語の表を示します。

標準入力標準出力標準エラー出力
Cstdinstdoutstderr
C++std::cinstd::coutstd::cerr
Javajava.lang.Sytem.injava.lang.System.outjava.lang.System.err

さて、お手持ちのパソコンでどれくらいのメモリーを取得できるのでしょうか? 次のプログラムは NULL が返ってくるまで 1MB のメモリーを取得し続けるプ ログラムです。 著者のノートパソコンは512MB のメモリを持っていますが、それで実行した場 合 1000 を越える値が出ました。 最近の OS はみな仮想記憶をサポートしているため、実メモリよりも多くの領 域を確保できます。 


#include <stdio.h>
#include <stdlib.h>
int main(void){
  long int i;
  for(i=0;malloc(1024*1024)!=NULL;i++);
  printf("%d\n",i);
  /* OS に free を任す */
  return 0;
}

5-2. キュー

FIFO(First In First Out)とは、データの処理の順番として、先に 入ったものは先に出されるという意味です。 これは日常生活では順番待ちなどで生じる現象です。 この仕組みをコンピュータ上で実現するには、来たデータを順番に並べて格納 し、来た順にアクセスできるように来た順にデータを取り出せるようにします。 このようなデータ記憶の方式をキュー(queue)と言います。 また、待ち行列とも言います。 キューはデータを送る側と受ける側が同期していないような状況で良く使われ ます。 例えば、プリンタ出力やメールの送受などの通信のやりとりの他、プログラム の内部処理におけるイベントやファイルの入出力でも使用されます。

キューに対する操作は、次の 3 つからなります。

  1. キューが空かどうか調べる(empty)
  2. キューに要素を入れる(enqueue)
  3. キューから要素を取り出す(dequeue)

配列を使った処理

C 言語で、まず配列を使用して実現する方法を考えます。 配列を使うと言うことは、最初から有限の領域になりますので、キューが溢れ る可能性があります。 しかし、まずはそれは考慮しないで実装することにします。 始めに、大きな配列が用意されているとします。 この配列を利用してキューを作ります。 キューに要素を入れるには、要素を入れるべき位置(ポインタ)に要素を入れ、 位置(ポインタ)を一つずらします。 これを素朴に書いたプログラムは次のようになります。 


#define MAX 50
static int q[MAX];
static int *e=q;
void enqueue(int x){
  *e++=x;
}

但し、これではまずいです。 というのは、書き込む要素が多くなると配列で確保した領域をはみ出してしま うからです。 これに関しては後ほどなんらかの措置をすることにします。 まずは、 dequeue の仕組みを先に考えましょう。 簡単で素朴なアイディアとして、常に配列の先頭をデータの先頭にすることが 考えられます。 しかし、このためには、配列の先頭から要素を取り出す度に、 queue の内容を前に詰めて、取り出したあとを埋めなければなりません。 この手間は毎回配列の長さ分だけ要素を動かさなければならないので、煩瑣で す。 したがって、効率を考えると、詰めずに済ませる方法を検討すべきです。 そこで、 enqueue と同様に要素を取り出すためのポインタを考えます。 要素を取り出したら次の要素を指すようにします。すると、前に詰める必要が なくなるため速く要素を取り出せます。 さて、最後に残った問題は、配列の容量をすぐに使い切ってしまうことです。

キューの動作

ここで、 dequeue の動作を考えると、一回要素を取り出してしまった部分は 使用しません。そこで、これを再利用することを考えます。 そのために、各 enqueue、dequeue のポインタが配列で用意した領域を使い切っ たら、配列の先頭に戻るようにします。 こうすることにより、毎回取り出す手間はポインタを移動することだけ で、配列内の要素を移動したりする必要がありません。 しかも、 enqueue と dequeue の要素の出し入れのスピードを合わせられれば 利用できる回数に制限がなくなります。 したがって、制約を取り除き、さらに多くのデータを高速に処理することができます。 以下に配列を用いたキューのプログラムを示します。 


#define MAX 50
static int q[MAX];
static int *e=q;
static int *d=q;
int enqueue(int x){
  int *next;
  next=e+1;
  if(next>=q+MAX){next=q;}
  if(next==d){ return 0;}
  *e=x;
  e=next;
  return 1;
}
int empty(void){
  return e==d;
}
int dequeue(void){
  int value;
  if(empty()){
    /* 要素がないのに要素を取り出そうとした時 */
    return 0; /* C++ ならエラーを発生できるのだが…… */
  }
  value=*d++;
  if(d>=q+MAX){
    d=q;
  }
  return value;
}

演習5-1

この queue をテストするため、次のプログラムを用意しました。 これを実際に実行して正常に動くか確かめなさい。 


#include <stdio.h>
int enqueue(int x);
int empty(void);
int dequeue(void);
int main(void){
  enqueue(5);
  enqueue(2);
  enqueue(8);
  while(!empty()){
    printf("%d\n",dequeue());
  }
  return 0;
}

線形リストを使った処理

配列を使用したキューは、あらかじめ配列の容量を決めておく必要があるため、 見積りより多くの要素を保存しようとすると破綻します。 配列を使う限り、大量のデータを受け入れられるようにするためには、あらか じめ必要なメモリをすべて最初に確保するプログラムを書く必要があります。 しかし、これは必要なメモリの容量の上限値を計算して与える必要があります し、実際に使う、使わないに関わらず、確実に大量のメモリ領域を最初から抑 えてしまうので、他のプログラムとの共存が難しくなります。 従って、多くのデータを受け入れるためには、メモリを動的に必要なだけ確保 して使用するテクニックが必要です。 言い換えれば、個々のデータに対して個別にメモリを確保するテクニックが必 要です。

さて、上のプログラムで示したように、キューを実現するには、注目している場所の データの出し入れと、次の領域の確保ができれば良いです。 これさえできれば、 別に配列のように整数変数で特定の要素を取り出すなどの機能は必要はあ りません。 そこで、ここでは線形リストという構造を使うテクニックを学び ます。 線形リストとは要素が一直線に並んでいて、隣接している要素が関連づいてい るものです。 構造として、「値」と「次の要素の位置」の二つを持ちます。

線形リスト

このような構造を線形リストと言います。 線形リストを用いると、データを一つずつ確保、廃棄ができるようになるの で、データの量に応じてメモリを使用することができます。 さて、この線形リストを使って大量のデータに対応できるキューを実現します。 C 言語で線形リストを作るには構造体とポインタを使用します。 構造体には、次の要素を指すためのポインタと値を入れる要素を持たせます。 このポインタの型はそのポインタを含む構造体自身を指すポインタの型になり ます。 


struct llist {
 struct llist *pointer;
 int value;
};

この構造体に対して、 enqueue、dequeue を行うには、データの格納、取り出 しを行う位置を記憶するため、構造体へのポインタを用意します。 


static struct llist *e, *d;

さて、線形リストを利用したキューに対する各処理は次のように書けます。

empty
dequeue ポインタ d が NULL かどうか
enqueue
  1. 1 新しい領域を確保し、
  2. 1 値を代入、
  3. 1 構造体内のポインタは NULL にする。
  4. 1 今、dequeue に指しているものがある時は、
  5. 1 enqueue の指している領域のポインタに新しい領域を代入することでつなげ、
  6. 1 enqueue ポインタを新しい領域を指すようにする。
  7. 1 ない場合は初めの一個目の要素なので、
  8. 1 dequeue ポインタに新しい領域の番地を入れて、
  9. 1 enqueue ポインタも新しい領域を指すようにする。
dequeue
ポインタが NULL だったらエラー。 そうでなければ、要素をとりだし、次の領域のポインタを代入し、今の領域を 捨てる。

これを実現すると下記のようになります。llist は自分自身の型を指すポイン タを含んでいることに注意して下さい。 


#include <stdlib.h>
struct llist {
 struct llist *pointer;
 int value;
};
static struct llist *e=NULL; /* 複数の関数からアクセスするので */
static struct llist *d=NULL; /* グローバル変数 */
int empty(void){
  return d==NULL;
}
int enqueue(int x){
  struct llist* next;
  next = malloc( sizeof (struct llist));
  if(next==NULL){ /* メモリが確保できないと NULL が返される */
    return 0;
  }
  next->value=x;
  next->pointer=NULL;
  if(d==NULL){
    d=next;
  }else{
    e->pointer=next;
  }
  e=next;
  return 1;
}  
int dequeue(void){
  int x;
  struct llist *next;
  if(empty()){
    /* 要素がないのに要素を取り出そうとした時 */
    return 0; /* C++ ならエラーを発生できるのだが…… */
  }
  x=d->value;
  next=d->pointer;
  free(d);
  d=next;
  return x;
}

なお、ここで、typedef struct llist { ... } LLIST; とする と、それ以降 struct llist と書かなければならない部分を LLIST と短く書 くことが出来ます。 書き直すと次のようになります。 


#include <stdlib.h>
typedef struct llist {
 struct llist *pointer;
 int value;
} LLIST;
static LLIST *e=NULL;
static LLIST *d=NULL;
int empty(void){
  return d==NULL;
}
int enqueue(int x){
  LLIST* next;
  next = malloc( sizeof (LLIST));
  if(next==NULL){ /* メモリが確保できないと NULL が返される */
    return 0;
  }
  next->value=x;
  next->pointer=NULL;
  if(d==NULL){
    d=next;
  }else{
    e->pointer=next;
  }
  e=next;
  return 1;
}  
int dequeue(void){
  int x;
  LLIST *next;
  if(empty()){
    /* 要素がないのに要素を取り出そうとした時 */
    return 0; /* C++ ならエラーを発生できるのだが…… */
  }
  x=d->value;
  next=d->pointer;
  free(d);
  d=next;
  return x;
}

演習5-2

演習5-1 で使ったテストを利用し、上のプログラムのテストをし、正常に動作 するか確かめなさい。

5-3. スタック

スタックのプログラム

FILO(First In Last Out)あるいは LIFO(Last In First Out)とは、データ処理の順番として、一番最後 に来たものから順に遡って処理をするという意味です。 そして、これを実現するデータ構造をスタックと言います。 スタックにデータを入れることを pushと言い、データを取り出す ことを popと言います。 また、データを入れる位置と取り出す位置は常に同じ位置になりますが、そこ を指すポインタをスタックポインタと言います。 スタックも直線的にデータを並べれば実現できるので、キューと同様に配列や 線形リストを使うと実現できます。 スタックを実現するプログラムを以下に示します。 


#define MAX 50
static int q[MAX];
static int stackpointer=0;
int push(int x){
  if(stackpointer+1>=MAX){
    return 0;
  }
  q[++stackpointer]=x;
  return 1;
}
int empty(void){
  return stackpointer==0;
}
int pop(void){
  if(empty()){
    /* 要素がないのに要素を取り出そうとした時 */
    return 0; /* C++ ならエラーを発生できるのだが…… */
  }
  return q[stackpointer--];
}


#include <stdlib.h>
typedef struct st {
  struct st *pointer;
  int value;
} STACK;
static STACK *stackpointer=NULL;
int empty(void){
  return stackpointer==NULL;
}
int push(int x){
 STACK *next= malloc(sizeof(STACK));
  if(next==NULL){ /* メモリが確保できないと NULL が返される */
    return 0;
  }
  next->value = x;
  next->pointer=stackpointer;
  stackpointer=next;
  return 1;
}
int pop(void){
  int x=stackpointer->value;
  STACK *p=stackpointer;
  stackpointer=p->pointer;
  free(p);
  return x;
}

演習5-3

スタックを実現するこれらのコードをテストしなさい。

スタックは、式やプログラムの解釈と密接な関係がありとても重要です。 サブルーチンを呼び出す時などに利用されます。 一方、式の処理にも利用されています。

カッコの処理

まずカッコの処理について考えてみます。 カッコの処理の基本として正しく閉じているか閉じてないかを判断することを 考えます。 カッコが一種類だけなら、スタックを使わずとも、整数変数を一つ用意して、 開きカッコで数を足し、閉じカッコで数を減らしていき、一回もマイナスにな らずに最後 0 で終るかどうか判断することで処理できます。 しかし、 HTML や XML のタグのように対応する開始タグと終了タグの種類が 多い場合どうすれば良いでしょうか? この場合、閉じカッコは一番近い開きカッコに対応するということを利用し、 開きカッコをスタックに順に push していき、閉じカッコが出現したらスタッ クから開きカッコを pop して対応しているかを調べることで処理できます。 開きタグと閉じタグの文法は次のようになっています。

開きタグ
<要素名 オプション1="値1" オプション2="値2" ... >
閉じタグ
</要素名>

この文法を踏まえ、開きタグと閉じタグの対応を確認するプログラムを示しま す。スタックには要素名を指す文字のポインタを入れます。 なお、このプログラムでは要素名を解釈中かそうでないかという状態を保持す るフラグという手法を使っています。 あと、要素名を取り出すたびに文字列の領域を確保し、要素名をスタックから 取り出した後領域を解放してます。

なお、C 言語の string.h には strdup という関数があります。 これは文字列へのポインタを引数とするとその文字列を複製し、 複製先の先頭番地を返すものです。 これを使うと文字列のコピーが簡単に作れます。 但し、メモリの確保に失敗すると NULL を返します。 そこで、スタックに push する際、 NULL を積もうとすると push 自体が失敗 するようにしておきます。 


#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 50
int push(char *); /* NULL を push しようとすると 0 を返す */
char * pop(void);
int empty(void);

void error(int i){
  fprintf(stderr,"error %d\n",i);
  exit(i);
}
char * bufferpointer;
int index;
void reset_buffer(char * p){
  bufferpointer = p;
  index = 0;
}
void store_buffer(char c){
  bufferpointer[i]=c;
  i++;
  if(i>=MAX){
    error(5); /* buffer overflow */
  }
}
int main(void){
  int flag=0;
  char buffer[MAX];
  int c;
  char *str;
  while((c=getchar())!=EOF){
    if(!flag){  /* flag==0 タグの外 */
      if(c=='<'){
        reset_buffer(buffer);
	flag=1;
      }
    }else{ /* flag==1 タグ内解析中 */
      if((c!=' ')&&(c!='>')){/* タグの要素名の採集 */
	store_buffer(c);
      }else{ /* 要素名終了 */
	store_buffer('\0');
	flag=0;
	if(buffer[0]!='/'){ /* 開始タグ処理(プッシュ) */
	  if(!push(strdup(buffer))){
            error(4);
          }
          printf("%s is pushed\n",buffer);
	}else{ /* 終了タグ処理 */
	  if(empty()){error(1);}/* 開始タグ無し */
          str=pop();
          printf("%s is popped\n",str);
          if(strcmp(str,buffer+1)!=0){
            free(str);
            error(2); /* 不一致 */
          }
          free(str);/* Ok なら文字領域開放*/
	}
      }
    }
  }
  if(!empty()){
    error(3);
  }
  printf("Ok.\n");
  return 0;
}

なお、実際の HTML や XML は全てのタグが閉じているわけではありません。 HTML、 XML とも DOCTYPE 宣言 <!DOCTYPE ... > という終了タ グのないタグを冒頭に置きますので、上記のプログラムでは不十分です。 さらに、 HTML では開始タグや終了タグを省略できます。一方 XML では基本的 に終了タグは省略できませんが、 <hr /> のように最後に / を付けて 開始タグと終了タグを兼用出来ます。 したがって、これらに対応しないチェックプログラムは実用的ではありません。 なお、XML への対応はそれなりに簡単にできますが、 HTML 対応はかなり複雑 になります。

演習5-4

stack に入れられる要素を文字へのポインタに改造し、上のプログラムを動か しなさい。 そして、テストデータを作り、正常に動作することを確かめなさい。 但し、上のプログラムでは終了状態として Ok, error 1, error 2, error 3, error 5 があるので、これら全てが正常に発生するようにテストデータを作りなさい。

数式処理

次に、数式を考えます。 数式は数と演算子と呼ばれるものからできています。 +,-,*,/ など我々が使う演算子は、通常、その演算子をはさむ両方の値に対し て計算を行い、答を出します。 その際、どのような順番で計算しても良いわけではなく、各演算子には優先順 位があります。 また、数式はカッコを利用して演算の順序を指定できます。 例えば、 2*3+4*5 を考えた時、これは ((2*3)+(4*5))と同じ意味になります。 これは演算子の優先順位を考慮すれば冗長な表現ですが、一方で厳密に演算の 順序を定めていることになります。 このように厳密に演算順序をカッコにより定められた式は、各カッコの中の値 を順に計算していけば全体の式の値を計算することができます。

ここで、カッコつきの演算を抽象的に考えてみます。 演算子というのは両隣の値から一つの値を計算するものなので、これは二つの 引数を持つ関数と考えることができます。 つまり、 (2*3) は 2 と 3 が引数になるわけです。 いまのところカッコの中は数が 2 つと演算子がひとつという関係です。 そこで、演算子が真中にあるという書き方の他に、先頭に置くという方式と、 最後に置くと言う方式も考えられます。

中置記法
((2*3)+(4*5))
前置記法
(+ (* 2 3)(* 4 5))
後置記法(逆ポーランド記法)
((2 3 *)(4 5 *) +)

このうち注目したいのは逆ポーランド記法です。 これは、演算子が閉じカッコの前にあります。 そのため、 演算子が現れたら、直前の二つの値に対して計算をして、カッコの中の値を求 めます。 演算子の直後でカッコが閉じるということは、カッコの内側から計算するには、 最も最初に計算しなければならない演算子から順番に現れることを意味します。 そのため、逆ポーランド記法では一番内側のカッコから自然に計算が出来ます。 さらに、演算子の直後に必ず閉じ括弧があるということを利用すると、逆ポーランド記 法では演算子の優先順位を決めなくても、カッコ無しの式で計算の順序に曖昧 さは生じません。 つまり 2 3 * 4 5 * + と書いても正しく計算が可能です。

さらに逆ポーランド記法に対しては、左から式を見ていき、演算子が現れたら一番近い二 つの値に対して計算を行えばいいので、スタックを利用すれば計算が出来ます。

逆ポーランド記法を(足し算だけ)計算するプログラムを以下に示します。 


#include <stdio.h>
#include <stdlib.h>
typedef struct st {
  struct st *pointer;
  int num;
} STACK;
STACK *stackpointer=NULL;
int empty(void){
  return stackpointer==NULL;
}
int push(int x){
  STACK *next=malloc(sizeof(stack));
  if(next==NULL){ /* メモリが確保できないと NULL が返される */
    return 0;
  }
  next->num = x;
  next->pointer=stackpointer;
  stackpointer=next;
  return 1;
}
int pop(void){
  int x=stackpointer->num;
  STACK *p=stackpointer;
  stackpointer=p->pointer;
  free(p);
  return x;
}
int main(void){
  char *p;
  char first;
  int i;
  int x,y;
  char *formula[] ={"1","2","+","3","+",NULL};
  for(i=0; formula[i]!=NULL; i++){
    first=*(formula[i]);
    switch(first){
    case '0':
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':
    case '8':
    case '9':
      push(atoi(formula[i]));
      break;
    case '+':
      y=pop();
      x=pop();
      push(x+y);
      break;
    }
  }
  printf("%d\n",pop());
  return 0;
}

演習5-5

上のプログラムを改造してかけ算も計算できるようにしなさい。 そして、 2 3 * 4 5 * + が正しく計算できるか確かめなさい。

5-4. C++ でのキューとスタック

C++ では STL でキューとスタックが用意されています。 以下のプログラムはその使用例です。 キューでは enqueue, dequeue の代わりに push(), pop() が使われ、 先頭の要素は pop() で得ずに front() をつかいます。 


#include <iostream>
#include <queue>
#include <deque> // または list
int main(){
  std::queue<int, std::deque<int> > q;
  q.push(5);
  q.push(2);
  q.push(8);
  while(!q.empty()){
    std::cout << q.front() << std::endl;
    q.pop();
  }
}

一方スタックでも pop() で値を取り出さずに top() で取り出してから pop() で値を取り除きます。 


#include <iostream>
#include <stack>
#include <deque> // または list か vector
int main(){
  std::stack<int, std::deque<int> > q;
  q.push(5);
  q.push(2);
  q.push(8);
  while(!q.empty()){
    std::cout << q.top() << std::endl;
    q.pop();
  }
}

5-5. Java でのキューとスタック

Java では java.util.LinkedList という線形リストのクラスに先頭と最後の 要素の出し入れをするメソッドが実装されています。 また C++ と同様に要素を取り出すメソッドと、要素を消すメソッドは別になっ ています。

Java 5

Java は version 5 から型を引数にしたクラスを使用できるようになりました。 これは総称(Generics)と呼ばれる機能です。 LinkedList のような複数の要素を取り扱うクラスを使う場合、あらかじめ取 り扱う型を宣言して使用します。これは C++ の Template と同様です。 但し、C++ と違い、総称で指定できる型はオブジェクトに限られ、int や double のような基本型は指定できません。これらに対してはラッパークラス を指定します。 但し、 Java 5 からはオートボクシング/アンボクシング機能と呼 ばれる、ラッパークラスと基本型の自動変換を実現しています。 そのため、宣言時にはラッパークラスで宣言して、手続きでは基本型をそのまま 使用しても、自動的に変換が行われます。

Java 1.4

なお、 Java 1.4 まではこの総称の機能はありませんでした。 そのため、従来の LinkedList など Collection 型のクラスライブラリは要素 に java.lang.Object 型の要素を取ることになっていました。 オブジェクト指向言語では親クラスの変数はサブクラスのオブジェクトを指す ことができるからです。 そのため、格納時はオブジェクトなら何でも格納することができます。但し通 常複数の種類のオブジェクトを入れるような使い方はしないことが多いです。 さて、取り出す時は java.lang.Object 型として得られるため、そのままでは もとのオブジェクトの機能を使うことが出来ません。 そのため、元の型にキャストをして使うことになります。 但し、 java.lang.Object 型に対してはどんなクラスでもキャストできてしま うため、もし間違ったキャストを指定しても、コンパイル時のチェックは出来 ず、実行時にキャストに関するエラーが発生していまいます。

さらに int などの基本型はオブジェクトではないので、そのままでは java.lang.Object 型の変数に代入できません。 この場合、ラッパークラスというクラスを使って基本型を java.lang.Object のサブクラスのインスタンスへ変換する必要があります。 int であれば java.lang.Integer というクラスを使ってオブジェクトに変換 します。 これで、格納することができます。 一方、値を取り出す時は、java.lang.Object 型の値として取り出したあと、 java.lang.Integer でキャストし、インタフェースである intValue() メソッ ドで元の値に変換します。

以下は Java でのプログラム例です。

Java 5

class TestQueue {
    public static void main(String[] arg){
	java.util.List<Integer> aList 
          = new java.util.LinkedList<Integer>();
	aList.addLast(5);
	aList.addLast(2);
	aList.addLast(8);
	while(!aList.isEmpty()){
	    System.out.println(aList.removeFirst());
	}
    }
}
Java 1.4

class TestQueue {
    public static void main(String[] arg){
	java.util.List aList = new java.util.LinkedList();
	aList.addLast(new Integer(5));
	aList.addLast(new Integer(2));
	aList.addLast(new Integer(8));
	while(!aList.isEmpty()){
	    System.out.println(((Integer)aList.removeFirst()).intValue());
	}
    }
}
Java 5

class TestStack {
    public static void main(String[] arg){
	java.util.List<Integer> aList
           = new java.util.LinkedList<Integer>();
	aList.addFirst(5);
	aList.addFirst(2);
	aList.addFirst(8);
	while(!aList.isEmpty()){
	    System.out.println(aList.removeFirst());
	}
    }
}
Java 1.4

class TestStack {
    public static void main(String[] arg){
	java.util.List aList = new java.util.LinkedList();
	aList.addFirst(new Integer(5));
	aList.addFirst(new Integer(2));
	aList.addFirst(new Integer(8));
	while(!aList.isEmpty()){
	    System.out.println(((Integer)aList.removeFirst()).intValue());
	}
    }
}
坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科