C 언어에서 연결 리스트 기반 스택이란?
스택(Stack)은 LIFO(Last In First Out, 후입선출) 방식으로 동작하는 대표적인 자료구조입니다. 배열을 이용해 스택을 구현하면 크기가 고정되기 때문에 스택 오버플로우(Stack Overflow)나 스택 언더플로우(Stack Underflow)가 발생하기 쉽습니다. 반면 연결 리스트(Linked List)를 활용하면 메모리를 동적으로 할당하므로 이러한 문제를 효과적으로 피할 수 있습니다.
C 언어에서 스택에 수행할 수 있는 기본 연산은 다음 두 가지입니다.
- Push: 스택의 맨 위(top)에 새로운 데이터를 삽입
- Pop: 스택의 맨 위 데이터를 삭제하고 반환
Push 연산의 기본 구현
Push는 새 노드를 생성해 리스트의 시작 부분에 연결하는 방식으로 구현합니다. 기본 구현 코드는 다음과 같습니다.
&item = 10; newnode = (node*) malloc(sizeof(node)); newnode->data = item; newnode->link = NULL; newnode->link = start; start = newnode;
동작 순서를 살펴보면 다음과 같습니다.
malloc()으로 새 노드의 메모리를 동적으로 할당합니다.- 새 노드의 데이터 필드에 값을 저장합니다.
- 새 노드의 링크가 기존 시작 노드(
start)를 가리키도록 합니다. start포인터를 새 노드로 갱신하여 새 노드가 스택의 top이 되도록 합니다.
Pop 연산의 기본 구현
Pop은 스택이 비어 있는지 먼저 확인한 뒤, 최상위 노드를 제거하고 메모리를 해제하는 방식으로 구현합니다. 기본 문법은 다음과 같습니다.
문법(Syntax)
if (start == NULL)
printf("Deletion is not possible. List is empty");
else {
temp = start;
start = start->link;
free(temp);
}- 스택이 비어 있으면(
start == NULL) 삭제가 불가능하다는 메시지를 출력합니다. - 그렇지 않으면 임시 포인터
temp에 현재 top을 저장하고,start를 다음 노드로 이동시킨 후free()로 메모리를 해제합니다.
연결 리스트로 만든 스택 전체 프로그램
다음은 연결 리스트를 이용해 스택을 구현한 완전한 C 프로그램입니다. Push, Pop, Top 확인, 빈 스택 검사, 출력, 요소 개수 확인, 스택 삭제 등의 기능을 메뉴 형태로 제공합니다.
#include <stdio.h>
#include <stdlib.h>
struct node {
int info;
struct node *ptr;
} *top, *top1, *temp;
int topelement();
void push(int data);
void pop();
void empty();
void display();
void destroy();
void stack_count();
void create();
int count = 0;
void main() {
int no, ch, e;
printf("\n 1 - Push");
printf("\n 2 - Pop");
printf("\n 3 - Top");
printf("\n 4 - Empty");
printf("\n 5 - Exit");
printf("\n 6 - Display");
printf("\n 7 - Stack Count");
printf("\n 8 - Destroy stack");
create();
while (1) {
printf("\n Enter choice : ");
scanf("%d", &ch);
switch (ch) {
case 1:
printf("Enter element : ");
scanf("%d", &no);
push(no);
break;
case 2:
pop();
break;
case 3:
if (top == NULL)
printf("stack is empty");
else {
e = topelement();
printf("\n Top element : %d", e);
}
break;
case 4:
empty();
break;
case 5:
exit(0);
case 6:
display();
break;
case 7:
stack_count();
break;
case 8:
destroy();
break;
default:
printf(" wrong choice: Try again ");
break;
}
}
}
// 빈 스택 생성
void create() {
top = NULL;
}
// 스택 내 요소 개수 출력
void stack_count() {
printf("\n no: of elements in stack : %d", count);
}
// 데이터 삽입(Push)
void push(int data) {
if (top == NULL) {
top = (struct node *)malloc(1 * sizeof(struct node));
top->ptr = NULL;
top->info = data;
} else {
temp = (struct node *)malloc(1 * sizeof(struct node));
temp->ptr = top;
temp->info = data;
top = temp;
}
count++;
}
// 스택 전체 출력
void display() {
top1 = top;
if (top1 == NULL) {
printf("empty stack");
return;
}
while (top1 != NULL) {
printf("%d ", top1->info);
top1 = top1->ptr;
}
}
// 데이터 삭제(Pop)
void pop() {
top1 = top;
if (top1 == NULL) {
printf("\n error");
return;
} else {
top1 = top1->ptr;
printf("\n Popped value : %d", top->info);
free(top);
top = top1;
count--;
}
}
// 최상위(top) 요소 반환
int topelement() {
return (top->info);
}
// 스택이 비었는지 확인
void empty() {
if (top == NULL)
printf("\n empty stack");
else
printf("\n stack not empty with %d values", count);
}
// 스택 전체 삭제(Destroy)
void destroy() {
top1 = top;
while (top1 != NULL) {
top1 = top->ptr;
free(top);
top = top1;
}
top = NULL;
printf("\n all are destroyed");
count = 0;
}실행 결과(Output)
위 프로그램을 실행하면 다음과 같은 결과를 확인할 수 있습니다.
1 - Push 2 - Pop 3 - Top 4 - Empty 5 - Exit 6 - Display 7 - Stack Count 8 - Destroy stack Enter choice: 1 Enter element: 23 Enter choice: 1 Enter element: 45 Enter choice: 1 Enter element: 56 Enter choice: 2 Popped value: 56 Enter choice: 6 45 23 Enter choice: 8 all are destroyed Enter choice: 6 empty stack Enter choice: 5
정리
연결 리스트 기반 스택은 필요할 때마다 노드를 동적으로 할당하므로 배열 기반 스택과 달리 용량 제한 없이 유연하게 운영할 수 있습니다. Push는 새 노드를 top 앞에 연결하고, Pop은 top 노드를 해제하며 한 칸 아래 노드를 새 top으로 지정하는 것이 핵심입니다. 다만 모든 동적 할당에는 free()를 통한 메모리 해제가 반드시 동반되어야 메모리 누수를 예방할 수 있습니다.