データ構造学習の道一

4163 ワード

本犬はビッグデータを勉強しながらデータ構造を勉強していますが、今日からデータ構造の学習過程を記録します.
スタックとキューから始めて、言語はJavaを選んで、後で時間があれば本犬はpythonバージョンを更新します.結局pythonはもっと簡潔です.
スタック:本の定義から引っ張らないでください.結局、コンピュータを勉強しているのは1冊以上のデータ構造の本があります.白話で言えば、スタックは先に入ってから出て、後に入ってきたのは先に出て、ピストルの弾丸を想像して、最初に弾丸を入れてから発射するかどうか、スタックが相対的に良いかどうかを理解します.
 
ここで以前の学習スタックで出会った問題を分かち合って、その時私の犬の頭を困らせました.
 
a,b,cの3つの要素はどのようにスタックを出すことができますか.
答えは5種類で、残念ながら当時は頭が回らなかったが、今から見れば、当時は本当に犬の頭だった.
a,b,cは順次入ってからc,b,a(3種類)
a,b進b出,c進c出   b,c,a(一種)
a進b進,b出a出,c進c出  b,a,c(一種)
明らかに、5種類のスタックが可能です.
次に、スタックの抽象データ型(ADT)
Javaで実装するので,直接関数を定義して実装し,コンストラクション関数で初期化する.
package dataStructs;

public class myStack {
    //    
    private int top;
    //       
    private long arr[];
    //         
    public myStack(){
        arr = new long[10];
        top = -1;
    }
    //         
    public myStack(int maxsize){
        arr = new long[maxsize];
        top = -1;
    }
    //    
    public void insert(int value){
       arr[++top] = value;
    }
    //    
    public long remove(){
        return arr[top--];
    }
    //    
    public long peek(){
        return arr[top];
    }
    //      
    public boolean isEmpty(){
        return top == -1;
    }
    //     
    public boolean isFull(){
        return top == arr.length;
    }
}

テストクラスでのテスト
package dataStructs;

public class TestMyStack {
    public static void main(String[] args){
        myStack ms = new myStack(10);
        ms.insert(12);
        ms.insert(72);
        ms.insert(52);
        ms.insert(1);
        System.out.println(ms.isEmpty());
        System.out.println(ms.isFull());

        System.out.println(ms.peek());
        System.out.println(ms.peek());

        while (!ms.isEmpty()){
            System.out.println(ms.remove()+",");
        }
        System.out.println(ms.isFull());
        System.out.println(ms.isEmpty());
    }
}

最後に、出力結果は
false false 1 1 1, 52, 72, 12, false true
スタックについてはここまでです.
 
行列は、桟と同じように、底には行列がありますが、行列は先に出ていて、駅で切符を買うように、最初の一番前の人が切符を買うと出て行って、向こうから列を出て、また一人来たら、列の尾から列に入るしかありません.これが列の本質です.
次にキューのコードを見てみましょう
package dataStructs;

public class myQuene {
    //        
    private long arr[];
    //       
    private int elements;
    //     
    private int front;
    //     
    private int tail;
    //         
    public myQuene(){
        //   
        arr = new long [10];
        elements = 0;
        front = 0;
        tail = -1;
    }
    //         
    public myQuene(int maxsize){
        arr = new long [maxsize];
        elements = 0;
        front = 0;
        tail = -1;
    }
    //    
    public void insert(long value){
        //        
        if (tail == arr.length-1){
            tail=-1;
        }
        arr[++tail] = value;
        elements++;
    }
    //    
    public long remove(){
        long value = arr[front++];
        if ( front == arr.length){
            front = 0;
        }
        elements--;
        return value;
    }
    //    ,     

    public long peek() {
        return arr[front];
    }

     //      

    public boolean isEmpty() {
        return elements == 0;
    }


     //       

    public boolean isFull() {
        return elements == arr.length;
    }

}

 
 テスト:
package dataStructs;

public class TestMyQuene {
    public static void main(String[] args){
        myQuene mq = new myQuene(4);
        mq.insert(23);
        mq.insert(45);
        mq.insert(13);
        mq.insert(1);

        System.out.println(mq.isFull());
        System.out.println(mq.isEmpty());

        System.out.println(mq.peek());
        System.out.println(mq.peek());

        while (!mq.isEmpty()) {
            System.out.print(mq.remove() + " ");
        }
        System.out.println();

        mq.insert(23);
        mq.insert(45);
        mq.insert(13);
        mq.insert(1);

        while (!mq.isEmpty()) {
            System.out.print(mq.remove() + " ");
        }
    }
}

結果:
true false 23 23 23 45 13 1 23 45 13 1
これで、本犬のスタックとキューに対する粗さの理解はこれで終わります.