Stack (データ構造）

Stack （スタック）

1. スタックの概念

データを一時的に収納するために使われるデータ構造．

入出力の順は LIFO（Last In First Out）で、最後に入れたデータから先に引き出す特性を持っている

Stackにデータを入れる作業をpushと言い、引き出す作業をpopと言う

pushとpopが行われる位置をtopといい、Stackの一番底をbottomと言う

２．スタックの生成

2-1．実装する機能
push,pop,peek,indexOf,clear,capacity,size,isEmpty,isFull,print

push : スタックにデータを入れて、その後スタックポインタを増加させる
pop ： スタックのtopにあるデータを削除する同時にその値を返還させる
peek ： topにあるデータを“覗く”メソッド
indexOf ：スタックに変数ｘと同じデータがあるのか、あったらスタックのどこに入ってるのか、そのインデックスを返還させる
clear ： スタックに貯まっている全てのデータを削除させる
capacity ： スタックの容量を返還するメソッド
size ： 現在スタックに貯まってるデータの数を返還する
isEmpty ： スタックが空いているのかをチェックする
isFull ： スタックが満タンなのかをチェックする
print ： スタックに貯まってるデータをbottomからtop順に出力する

2-2 メソッドのソースコード

public class IntStack {
    private int max;
    private int ptr;
    private int[] stk;

    public IntStack(int capacity) {
    ptr= 0;
    max = capacity;
    try { 
        stk = new int[max];
    } catch (OutofMemoryError e) {
        max = 0;
    }
}

コンストラクタ - Intstack(int capacity)
コンストラクタはスタックの配列を作るなどの準備作業をする．
作った時のスタックは空いているのでスタックポインタの値は０にする．
そして受け取った因数、capacityの値でスタックの容量を表す、maxにコピーし、長さmaxの配列stkの本体を作る．

public int push(int x) throws OverflowIntStackException {
    if (ptr >= max) 
        throw new OverflowIntStackException();
    return stk[ptr++]=x;
｝
    
public int pop() throws EmptyIntStackException {
    if (ptr<=0)
        throw new EmptyIntStackException();
    return stk[--ptr];
}

public int peek() throws EmptyIntStackException {
    if (ptr<=0)
        throw new EmptyIntStackException();
    return stk[ptr-1];
}

push(int x)
受け取ったデータ、xー＞stk[ptr]、スタックポインタを増加させる（ptr++）

pop()
まずはスタックポインタ、ptrを減少させてstk[ptr]に収納されている値を返還

pop()でptrの前に“--”を付けるのはpush()が終わる時にptrが増加させるため、stk[--ptr]することでtopのデータに辿り着ける
peek()も同じく、stk[ptr-1]することでtopのデータを見れる

//indexOf(int x)

public int indexOf(int x){
    for (int i=ptr-1;i>=0;i--)
        if(stk[i]==x)
            return i;
    return -1;
}

for文を使って"top（ptr-1）"からbottom(0)まで検索を行い、xと同じデータを持っているスタックのインデックスを返還させて、もし見つからない場合はー１を返還する

//clear(),size(),capacity()

public void clear() {
    ptr = 0;
}

public int capacity() {
    return max;
}

public int size() {
    return ptr;
}

clearはptrを０に戻してスタックのリセットを行う．
sizeは今スタックに貯まっているデータの数=ptrを返還するだけで表せる
capacityは最初に設定してたmaxを返還させる

//isEmpty(),isFull() 

public boolean isEmpty() {
    return ptr <= 0;
}

public boolean isFull() {
    return ptr >= max;
}

isEmpty() - ptrが０と同じ、もしくは０より小さい場合はスタックが空いているってこと
isFull() - ptrがmaxと同じ、もしくはmaxより大きい場合はスタックが満タンってことになる

public void print(){
    if (ptr<=0) ← isEmpty()が入ってもいい
        System.out.println("stack if Empty!");
    else {
        for (int i=0;i<ptr;i++)
            System.out.print(stk[i] + " ");
        System.out.println();
        }
    }
}

print() : とりあえずptrが０と同じ、０より小さい場合はスタックが空いているのでスタックが空いているってメッセージを出力する
そうじゃないときはfor文を使ってbottomからtopのデータを全部出力させる

３．ソースコードまとめ

    private int max;
    private int ptr;
    private int[] stk;

    public IntStack(int capacity) {
        ptr = 0;
        max=capacity;
        try{
            stk=new int[max];
        } catch (OutOfMemoryError e){
            max=0;
        }
    }
    
    public int push(int x) throws OverflowIntStackException{
        if (ptr>=max){
            throw new OverflowIntStackException();
        }
        return stk[ptr++]=x;
    }

    public int pop() throws EmptyIntStackException{
        if (ptr<=0)
            throw new EmptyIntStackException();
        return stk[--ptr];
    }

    public int indexOf(int x){
        for (int i=ptr-1;i>=0;i++)
            if (stk[i]==x)
                return i;
        return -1;
    }

    public void clear(){
        ptr=0;
    }

    public int capacity(){
        return max;
    }

    public int size(){
        return ptr;
    }

    public boolean isEmpty(){
        return ptr<=0;
    }

    public boolean isFull(){
        return ptr>=max;
    }

    public class EmptyIntStackException extends RuntimeException {
        public EmptyIntStackException() {
        }
    }

    public class OverflowIntStackException extends RuntimeException {
        public OverflowIntStackException() {
        }
    }

    public int peek() throws EmptyIntStackException{
        if (ptr<=0)
            throw new EmptyIntStackException();
        return stk[ptr-1];
    }

    public void print(){
        if (ptr<=0)
            System.out.println("stack is Empty!.");
        else{
            for (int i=0;i<ptr;i++){
                System.out.print(stk[i]+" ");
            }
            System.out.println();
        }
    }
}