c言語で実現された多形スタック――小柄精悍

1、データ構造——スタック
スタックはデータ構造として、端のみに挿入および削除操作を行うことができる特殊な線形表です.それは先進的な後に出る原則によってデータを保存して、先に入るデータはスタックの底に押し込まれて、最後のデータはスタックの上で、データを読む必要がある時スタックのてっぺんからデータをイジェクトします(最後のデータは最初に読まれます).スタックはメモリとして機能し、スタックの挿入と削除操作において、スタックの底のポインタを変更する必要はない.
スタックは、同じ端に挿入と削除を許可する特殊な線形表である.挿入と削除を許可する端はスタックトップ(top)、他端はスタック底(bottom)といいます.スタックの底は固定していますが、スタックの上は浮動しています.スタックの要素の個数がゼロの時を空スタックと呼びます.挿入は一般的に進スタック(PUSH)と呼ばれ、削除は退スタック(POP)と呼ばれます.スタックは後進先出表ともいいます.
スタックは、関数呼び出し時にブレークポイントを保存し、再帰時にスタックを使用することができます.
2、スタックの多形性
スタックの多形性とは、スタックが任意のタイプのデータを記憶し、使用中にそのデータ構造を失わないことを意味する.この時は多くの人が次のようなスタックの基本的なフォーマットを考えるべきです.

typedef struct list
{
        struct list *next;
        void *data;
}List_head;

typedef struct
{
        List_head *top;
};

は、データを格納する際に、dataポインタを格納するデータ構造のアドレスに向けることで、dataを通じて特定のデータを見つけることができ、スタックを使用して異なるタイプのデータを記憶することができるという役割を果たし、このような特性は多状態である.
しかし、私はいつもこの基本的な構造がずるずると感じています.このスタックの中には**dataポインタがあります.pushの前に具体的なデータアドレスをdataに割り当ててList_を作ります.head、このスタックが長いと、このスタック自体を維持するために多くの出費が必要です.
私たちはlinuxカーネルを勉強していますが、linuxカーネルコードは一本のチェーンと一つの塊のデータ構造のように構成されています.この優れたカーネルはチェーンの処理に没頭していると言えます.ここではlinuxカーネル組織のチェーンを採用したという考えの中の簡単で実用的なスタックを紹介します.
3、シンプルで実用的なスタック
スタックの基本構造

typedef struct list
{
  struct list *next;
}List_head;

typedef struct
{
  List_head *top;
}Stack;

と上の方はdataポインタが少なくなりました.このようなスタックはとてもシンプルです.メンテナンスも簡単です.
以下はその関連操作の実現を見ます.

//     
void initStack(Stack * s)
{
   s->top=NULL;
}

//   
void push(Stack *s, List_head *p)
{
    p->next=s->top;
    s->top=p;
}

//   
List_head *pop(Stack *s)
{
    List_head *p=s->top;
    s->top=p->next;
    return p;
}

//        
int isEmpty(Stack *s)
{
   return s->top==NULL;
}

会いたいですが、このようなスタックにはList_しか保存されていません.headのような構造で、List_headの中には、それより先にpushをスタックに入れたList_だけが保存されています.ヘッド構造体このようなスタックは役に立たないようです.
このようなスタックの特徴は、占有空間が特に小さく、List_のみであることである.headのような構造はチェーンテーブルを形成し、このスタックを維持するためのオーバヘッドも非常に小さいが、様々なデータ構造を記憶し管理することができる.
Linuxカーネルでは、チェーンに加入する必要があるデータ構造の中に「ダメ」なメンバータイプのList_があります.headは、この不器用そうなメンバーで、チェーンの管理を実現しました.
だから、私たちはただ私たちがスタックなどの操作を必要とするデータ構造にList_を追加するだけです.ヘッドタイプのメンバーが実現できます.以下は2つのカスタムデータ構造です.

// here, you can define any struct that include the type List_head
 typedef struct
{
  List_head member;
  int data;
}MY;

typedef struct
{
  List_head member;
  double data;
}You;
 

私達はこの二つのデータのメンバーだけを倉庫に入れて倉庫を出す必要があります.このスタックは干す紐のように様々な服を干していますが、ここに来てもう一つの重要なステップが欠けています.OFの偉大さが実現する.ここは自分で実現します.リストという名前で.イベントのマクロ

#define list_entry(type,pos,member) \
(type*)((char*)pos-(int)(&((type*)0)->member))

このマクロの使い方はとても巧みで、詳しく説明しません.読者はこのマクロをよく読んでください.このマクロを利用して、私たちはメンバーによってその所在する構造変数のアドレスを取得することができます.
4、試験用例

int main()
{
  Stack s;
  MY  p1,p2,p3,*h;
  You q1,q2,q3,*w;
  List_head *p;
  initStack(&s);

  p1.data = 1;
  p2.data = 2;
  p3.data = 3;
  push(&s,&p1.member);
  push(&s,&p2.member);
  push(&s,&p3.member);
  while(!isEmpty(&s))
  {
    p=pop(&s);

	//        
    h=list_entry(MY,p,member);
    printf("%d
",h->data);
  }
  return 0;
}

結果はみんなに貼り付けませんでした.