システムプログラマー成長計画-組合せの威力(三)

3180 ワード

転載の際は出典と作者の連絡先を明記してください
文章の出所:http://www.limodev.cn/blog 作者の連絡先:李先静

スタック
スタックは後進先出(LIFO,last in first out)のデータ構造であり,キューの先進先出(FIFO)に比べてこの規則はあまり公平ではないようで,コンピュータはこれにかかわらない.実際、スタックは最も重要なデータ構造の一つです.スタックがなく、プッシュダウンオートマチックベースのコンパイラが動作せず、アセンブリを書くしかありません.スタックがなく、再帰/マルチレベル関数呼び出しが実現できず、プログラムが動作しません.
スタックの主なインタフェース関数は次のとおりです.
oスタックスタックを作成する_create oスタックトップ要素stack_top oはスタックトップstack_に要素を入れますpush oスタックトップ要素stack_pop o取スタック内の要素個数stack_length oスタック内の要素stack_を巡るforeach oスタックを破棄stack_destroy
スタックはチェーンテーブルと配列の特殊な形式です.次に、チェーンテーブルを再利用してスタックを実現します.
oスタックのデータ構造


struct _Stack
{
    DList* dlist;
};

ここではキューのデータ構造と同様に、チェーンテーブルで構成されています.
oスタックの作成


Stack* stack_create(DataDestroyFunc data_destroy, void* ctx)
{
    Stack* thiz = (Stack*)malloc(sizeof(Stack));

    if(thiz != NULL)
    {
        if((thiz->dlist = dlist_create(data_destroy, ctx)) == NULL)
        {
            free(thiz);
            thiz = NULL;
        }
    }

    return thiz;
}

スタックを作成するときは、自分のスペースを割り当てる以外に、双方向チェーンテーブルを簡単に作成します.
oスタックトップ要素を取る


Ret      stack_top(Stack* thiz, void** data)
{
    return_val_if_fail(thiz != NULL && data != NULL, RET_INVALID_PARAMS);

    return dlist_get_by_index(thiz->dlist, 0, data);
}

チェーンテーブルの最初の要素はスタックトップであり,スタックトップの要素はチェーンテーブルの最初の要素であると考えられる.
o要素をスタックトップに入れる


Ret      stack_push(Stack* thiz, void* data)
{
    return_val_if_fail(thiz != NULL, RET_INVALID_PARAMS);

    return dlist_prepend(thiz->dlist, data);
}

エレメントをスタックの上部に挿入すると、エレメントをチェーンヘッダーに挿入します.
oスタックトップ要素の削除


Ret      stack_pop(Stack* thiz)
{
    return_val_if_fail(thiz != NULL, RET_INVALID_PARAMS);

    return dlist_delete(thiz->dlist, 0);
}

スタックトップ要素の削除は、チェーンテーブルを削除する最初の要素です.
oスタック内の要素の数を取る


size_t   stack_length(Stack* thiz)
{
    return_val_if_fail(thiz != NULL, 0);

    return dlist_length(thiz->dlist);
}

スタック内の個数はチェーンテーブルの個数に等しい.
oスタック内の要素を巡る


Ret      stack_foreach(Stack* thiz, DataVisitFunc visit, void* ctx)
{
    return_val_if_fail(thiz != NULL && visit != NULL, RET_INVALID_PARAMS);

    return dlist_foreach(thiz->dlist, visit, ctx);
}

ループスタック内の要素は、ループチェーンテーブル内の要素と同じです.
oスタックの破棄


void stack_destroy(Stack* thiz)
{
    if(thiz != NULL)
    {
        dlist_destroy(thiz->dlist);
        thiz->dlist = NULL;

        free(thiz);
    }

    return;
}

双方向チェーンテーブルを破棄し、独自のスペースを解放します.
スタックは非常に重要なデータですが、不思議なことに私たちはそれを書く機会が少ないです.実際、私は仕事の中でスタックを書いたことがありません.これはどういうことですか.なぜなら、私たちのコンピュータ自体はスタックに基づいているので、多くのことはコンピュータが私たちが知らないうちに処理してくれました.例えば、関数呼び出し(特に再帰呼び出し)、コンピュータが処理してくれました.再帰的降下による構文解析は,関数呼び出しの再帰性を利用し,明示的な構造スタックも必要としない.

Struts 2の値スタックの詳細

nginxとIP、同ポート、異なるドメイン名の転送