연결 리스트(Linked List)가 주어졌을 때, 스택(Stack) 자료구조를 활용하여 리스트의 마지막 요소부터 첫 번째 요소까지 역순으로 출력하는 프로그램을 만들어 보겠습니다.
입력 : 10 -> 5 -> 3 -> 1 -> 7 -> 9 출력 : 9 -> 7 -> 1 -> 3 -> 5 -> 10
핵심 아이디어는 간단합니다. 연결 리스트를 순회하면서 모든 데이터를 스택에 차례대로 저장(push)한 뒤, 스택의 최상단(top)부터 요소를 하나씩 꺼내면서(pop) 출력하면 자연스럽게 역순 결과를 얻을 수 있습니다.
알고리즘
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 -> printfromstack(int stack[]) 함수 생성 While top>=0 동안 반복 stack[--top] 값 출력 End Step 5 -> 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 -> intostack(struct linked_list* head) 함수 생성 While 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;
}실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
Linked list: 40 30 20 10 Stack: 10 20 30 40
동작 원리 정리
이 코드의 흐름을 단계별로 살펴보면 다음과 같습니다.
1. push 함수 : 새 노드를 리스트의 맨 앞에 삽입합니다. 따라서 10, 20, 30, 40 순서로 삽입하면 실제 연결 리스트에는 40 → 30 → 20 → 10 순서로 저장됩니다.
2. intostack 함수 : 연결 리스트를 처음부터 끝까지 순회하면서 각 노드의 값을 화면에 출력하고, 동시에 스택 배열에 순서대로 저장합니다.
3. printfromstack 함수 : 스택은 LIFO(Last In, First Out, 후입선출) 구조이므로, top 인덱스부터 감소시키며 값을 꺼내면 가장 나중에 들어간 데이터부터 출력됩니다. 그 결과 연결 리스트의 역순 출력이 완성됩니다.
이처럼 스택의 후입선출 특성을 활용하면 연결 리스트를 별도의 재귀 호출 없이도 손쉽게 역순으로 출력할 수 있습니다.