配列を利用してスタックを実現する(Java実装)
スタック紹介
スタックは先入後に出るシーケンス表です。
スタックは、線形表の要素の挿入と削除を制限するために、線形表の同じ端だけで行うことができる特殊な線形表であり、挿入と削除を許可する端は変化の一端として、スタックトップと呼ばれ、他端は固定の端と呼ばれ、スタックの底と呼ばれています。
最初にスタックに入れた要素はスタックの底にあり、最後に入れた要素はスタックの上にある。
最初にスタックから出る要素はスタックの一番上にあり、最後にスタックから出る要素はスタックの底にある。
分析
配列を用いてスタックの実現をシミュレートするには、まず配列の長さが固定されていることを考慮して、スタックを使用すると、特定の長さ、すなわち最大長さMaxSizeを与える必要がある。配列のインデックス値が0から始まるので、衝突を起こさないように-1から開始するために、スタックトップポインタをカスタマイズします。
スタックは空です。top=-1の場合、すなわち初期化データに等しく、配列内に何の要素も存在しない場合、スタックは空であることを示します。
スタック満:要素を追加すると、スタックトップポインタは後ろに移動しますが、配列の長さを考慮して固定されています。満杯の場合があります。判定条件は、top=MaxSize-1の場合、スタックが満杯となります。例えば、3つのサイズの配列を定義して、一つのデータ1を入れて、topは-1から0になり、もう一つのデータ2を入れて、topは0から1になり、もう一つのデータ3を入れて、topは1から2になります。この時、配列はもういっぱいです。判定条件はtop=MaxSizeで、スタックがいっぱいです。
倉庫に入る前に、まずスタックが満杯かどうかを判断します。でないと、倉庫に入ることができません。top+1は、配列インデックスをtopとする要素に付加されたデータを割り当てます。
倉庫を出す前に、まずスタックが空かどうかを判断します。でないと、倉庫から出られません。空でない場合は、スタックの一番上の要素、つまりインデックス値がtopの要素を取ってからtop-1を返します。
巡回スタック:遍歴する時もスタックの中が空かどうかを判断して、データを遍歴するのもスタックのトップの要素から遍歴し始めて、ずっとスタックの底まで遍歴して終わりました。
コードの実装
スタックは先入後に出るシーケンス表です。
スタックは、線形表の要素の挿入と削除を制限するために、線形表の同じ端だけで行うことができる特殊な線形表であり、挿入と削除を許可する端は変化の一端として、スタックトップと呼ばれ、他端は固定の端と呼ばれ、スタックの底と呼ばれています。
最初にスタックに入れた要素はスタックの底にあり、最後に入れた要素はスタックの上にある。
最初にスタックから出る要素はスタックの一番上にあり、最後にスタックから出る要素はスタックの底にある。
分析
配列を用いてスタックの実現をシミュレートするには、まず配列の長さが固定されていることを考慮して、スタックを使用すると、特定の長さ、すなわち最大長さMaxSizeを与える必要がある。配列のインデックス値が0から始まるので、衝突を起こさないように-1から開始するために、スタックトップポインタをカスタマイズします。
スタックは空です。top=-1の場合、すなわち初期化データに等しく、配列内に何の要素も存在しない場合、スタックは空であることを示します。
スタック満:要素を追加すると、スタックトップポインタは後ろに移動しますが、配列の長さを考慮して固定されています。満杯の場合があります。判定条件は、top=MaxSize-1の場合、スタックが満杯となります。例えば、3つのサイズの配列を定義して、一つのデータ1を入れて、topは-1から0になり、もう一つのデータ2を入れて、topは0から1になり、もう一つのデータ3を入れて、topは1から2になります。この時、配列はもういっぱいです。判定条件はtop=MaxSizeで、スタックがいっぱいです。
倉庫に入る前に、まずスタックが満杯かどうかを判断します。でないと、倉庫に入ることができません。top+1は、配列インデックスをtopとする要素に付加されたデータを割り当てます。
倉庫を出す前に、まずスタックが空かどうかを判断します。でないと、倉庫から出られません。空でない場合は、スタックの一番上の要素、つまりインデックス値がtopの要素を取ってからtop-1を返します。
巡回スタック:遍歴する時もスタックの中が空かどうかを判断して、データを遍歴するのもスタックのトップの要素から遍歴し始めて、ずっとスタックの底まで遍歴して終わりました。
コードの実装
package cn.mrlij.stack;
import java.util.Arrays;
import java.util.Scanner;
/**
*
*
* @author dreamer
*
*/
public class ArrayStackDemo {
public static void main(String[] args) {
//
ArrayStack a = new ArrayStack(5);
boolean flag = true;//
Scanner sc = new Scanner(System.in);
String key = "";//
while (flag) {
System.out.println("show: ");
System.out.println("exit: ");
System.out.println("push: ");
System.out.println("pop: ");
key = sc.nextLine();
switch (key) {
case "show":
a.show();
break;
case "exit":
flag = false;
System.out.println(" !");
break;
case "push":
System.out.println(" :");
int val = sc.nextInt();
a.push(val);
break;
case "pop":
try {
int pop = a.pop();
System.out.println(" :" + pop);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
default:
break;
}
}
}
}
class ArrayStack {
private int MaxSize;//
private int[] arr;// ,
private int top = -1;// , -1
public ArrayStack(int maxSize) {
this.MaxSize = maxSize;
arr = new int[MaxSize];
}
//
public boolean isEmpty() {
return top == -1;
}
//
public boolean isFull() {
System.out.println(" :" + top + " :" + MaxSize);
return top == MaxSize - 1;
}
//
public void push(int val) {
// ,
if (isFull()) {
System.out.println(" ~~");
return;
}
top++;
arr[top] = val;
}
//
public int pop() {
//
if (isEmpty()) {
throw new RuntimeException(" , !");
}
int val = arr[top];
top--;
return val;
}
public void show() {
if (isEmpty()) {
System.out.println(" ");
return;
}
for (int i = top; i >= 0; i--) {
System.out.print(arr[i] + "\t");
}
System.out.println();
}
}
以上が本文の全部です。皆さんの勉強に役に立つように、私たちを応援してください。