スタックデータ構造を使って連結リストを逆順に出力する方法【C言語】

連結リスト（リンクリスト）が与えられたとき、スタックというデータ構造を活用して、リストの要素を末尾から先頭へ向かって出力するプログラムを作成します。

入力 : 10 -> 5 -> 3 -> 1 -> 7 -> 9
出力: 9 -> 7 -> 1 -> 3 -> 5 -> 10

この問題では、スタックから要素をポップ（取り出し）していくアプローチを採用します。具体的には、top を stack[0] の位置から始め、stack[n] の要素まで順番に処理を進めていきます。

アルゴリズム

START
Step 1 -> 構造体 Linked_list を作成する
   int 型の data を宣言
   struct linked_list *next を宣言
End
Step 2 -> int stack[30], top = -1 を宣言する
Step 3 -> struct linked_list* head = NULL を宣言する
Step 4 -> 関数 int printfromstack(int stack[]) を作成する
   top >= 0 の間ループする
   stack[--top] を出力する
End
Step 5 -> 関数 int push(struct linked_list** head, int n) を作成する
   struct linked_list* newnode = (struct linked_list*)malloc(sizeof(struct linked_list)) を宣言
   newnode->data = n を設定
   newnode->next = (*head) を設定
   (*head) = newnode を設定
Step 6 -> 関数 int intostack(struct linked_list* head) を作成する
   head != NULL の間ループする
   head->data を出力する
   stack[++top] = head->data を設定
   head = head->next を設定
   End
End
Step 7 -> main() へ移動する
   push(&head, 10) を呼び出す
   push(&head, 20) を呼び出す
   push(&head, 30) を呼び出す
   push(&head, 40) を呼び出す
   intostack(head) を呼び出す
   printfromstack(stack) を呼び出す
STOP

サンプルコード

#include <stdio.h>
#include <stdlib.h>
struct linked_list {
   int data;
   struct linked_list *next;
};
int stack[30], top = -1;
struct linked_list* head = NULL;
int printfromstack(int stack[]) {
   printf("\nStack:\n");
   while(top>=0) {
      printf("%d ", stack[top--]);
   }
}
int push(struct linked_list** head, int n) {
   struct linked_list* newnode = (struct linked_list*)malloc(sizeof(struct linked_list));
   newnode->data = n;
   newnode->next = (*head);
   (*head) = newnode;
}
int intostack(struct linked_list* head) {
   printf("Linked list:\n");
   while(head!=NULL) {
      printf("%d ", head->data);
      stack[++top] = head->data;
      head = head->next;
   }
}
int main(int argc, char const *argv[]) {
   push(&head, 10);
   push(&head, 20);
   push(&head, 30);
   push(&head, 40);
   intostack(head);
   printfromstack(stack);
   return 0;
}

コードのポイント

• push() 関数は、新しいノードをリストの先頭に挿入することで、連結リストを構築します。
• intostack() 関数は、連結リストを先頭から順に走査しながら、各ノードの値をスタックに格納します。
• printfromstack() 関数は、スタックの性質（LIFO：後入れ先出し）を利用し、最後に格納した要素から順に取り出して出力することで、逆順表示を実現しています。

実行結果

上記のプログラムを実行すると、以下の出力が得られます。

Linked list:
40 30 20 10
Stack:
10 20 30 40

このように、スタックの「後入れ先出し」という特性を利用することで、連結リストを簡単に逆順に出力できることがわかります。