配列を使用する代わりに、リンクされたリストを使用してスタックを実装することもできます。リンク リストはメモリを動的に割り当てます。ただし、両方のシナリオの時間計算量は、すべての操作 (プッシュ、ポップ、ピーク) で同じです。

スタックのリンク リスト実装では、ノードはメモリ内に非連続に保持されます。各ノードには、スタック内のその直接の後続ノードへのポインタが含まれています。メモリ ヒープ内に残っている領域がノードを作成するのに十分でない場合、スタックはオーバーフローしていると言われます。

スタック内の最上位のノードのアドレス フィールドには常に null が含まれます。スタックのリンクリスト実装で各操作がどのように実行されるかを説明します。

スタックへのノードの追加（プッシュ操作）

スタックにノードを追加することを、 押す 手術。リンク リスト実装での要素のスタックへのプッシュは、配列実装の場合とは異なります。要素をスタックにプッシュするには、次の手順が必要です。

1. まずノードを作成し、それにメモリを割り当てます。
2. リストが空の場合、項目はリストの開始ノードとしてプッシュされます。これには、ノードのデータ部分に値を割り当てることと、ノードのアドレス部分に null を割り当てることが含まれます。
3. リストにすでにノードがいくつかある場合は、(スタックのプロパティを侵害しないように) リストの先頭に新しい要素を追加する必要があります。この目的のために、開始要素のアドレスを新しいノードのアドレス フィールドに割り当て、新しいノードをリストの開始ノードにします。

時間計算量 : o(1)





C 実装:

 void push () { int val; struct node *ptr =(struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf('not able to push the element'); } else { printf('Enter the value'); scanf('%d',&val); if(head==NULL) { ptr->val = val; ptr -> next = NULL; head=ptr; } else { ptr->val = val; ptr->next = head; head=ptr; } printf('Item pushed'); } } 

スタックからのノードの削除 (POP 操作)

スタックの先頭からノードを削除することを、 ポップ 手術。スタックのリンク リスト実装からのノードの削除は、配列実装の場合とは異なります。スタックから要素をポップするには、次の手順に従う必要があります。

アンダーフロー状態を確認します。アンダーフロー状態は、すでに空のスタックからポップしようとしたときに発生します。リストの先頭ポインタが null を指している場合、スタックは空になります。それに応じてヘッド ポインタを調整します。スタックでは、要素は一方の端からのみポップされるため、ヘッド ポインタに格納されている値を削除し、ノードを解放する必要があります。ヘッド ノードの次のノードがヘッド ノードになります。

時間計算量 : o(n)

Cの実装

 void pop() { int item; struct node *ptr; if (head == NULL) { printf('Underflow'); } else { item = head->val; ptr = head; head = head->next; free(ptr); printf('Item popped'); } } 

ノードを表示する（トラバース）

スタックのすべてのノードを表示するには、スタックの形式で編成されたリンク リストのすべてのノードを走査する必要があります。この目的のために、次の手順に従う必要があります。

1. ヘッドポインタを一時ポインタにコピーします。
2. 一時ポインタをリストのすべてのノードに移動し、すべてのノードに付加された値フィールドを出力します。

時間計算量 : o(n)

C 実装

 void display() { int i; struct node *ptr; ptr=head; if(ptr == NULL) { printf('Stack is empty
'); } else { printf('Printing Stack elements 
'); while(ptr!=NULL) { printf('%d
',ptr->val); ptr = ptr->next; } } } 

リンク リストを使用してすべてのスタック操作を実装する C のメニュー駆動プログラム:

 #include #include void push(); void pop(); void display(); struct node { int val; struct node *next; }; struct node *head; void main () { int choice=0; printf('
*********Stack operations using linked list*********
'); printf('
----------------------------------------------
'); while(choice != 4) { printf('

Chose one from the below options...
'); printf('
1.Push
2.Pop
3.Show
4.Exit'); printf('
 Enter your choice 
'); scanf('%d',&choice); switch(choice) { case 1: { push(); break; } case 2: { pop(); break; } case 3: { display(); break; } case 4: { printf('Exiting....'); break; } default: { printf('Please Enter valid choice '); } }; } } void push () { int val; struct node *ptr = (struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf('not able to push the element'); } else { printf('Enter the value'); scanf('%d',&val); if(head==NULL) { ptr->val = val; ptr -> next = NULL; head=ptr; } else { ptr->val = val; ptr->next = head; head=ptr; } printf('Item pushed'); } } void pop() { int item; struct node *ptr; if (head == NULL) { printf('Underflow'); } else { item = head->val; ptr = head; head = head->next; free(ptr); printf('Item popped'); } } void display() { int i; struct node *ptr; ptr=head; if(ptr == NULL) { printf('Stack is empty
'); } else { printf('Printing Stack elements 
'); while(ptr!=NULL) { printf('%d
',ptr->val); ptr = ptr->next; } } }