자료구조란 무엇인가?
자료구조(Data Structure)는 데이터를 체계적으로 정리하고 관리하는 방식을 의미합니다. 자료구조는 크게 선형 자료구조와 비선형 자료구조 두 가지로 분류할 수 있습니다.
선형 자료구조 (Linear Data Structure)
데이터가 일렬(순차적) 형태로 배치되는 구조입니다.
예시: 배열(Array), 구조체(Structure), 스택(Stack), 큐(Queue), 연결 리스트(Linked List)
비선형 자료구조 (Non-linear Data Structure)
데이터가 계층적 형태로 배치되는 구조입니다.
예시: 트리(Tree), 그래프(Graph), 집합(Set), 테이블(Table)
C 언어에서의 스택(Stack)
스택은 한쪽 끝(top)에서만 데이터의 삽입과 삭제가 이루어지는 선형 자료구조입니다. 마지막에 들어간 데이터가 가장 먼저 나오는 LIFO(Last In, First Out) 방식으로 동작하며, 접시를 쌓아 올린 모습에 비유할 수 있습니다.
스택의 주요 연산
- Push(삽입) – 스택의 꼭대기(top)에 새로운 요소를 추가합니다.
- Pop(삭제) – 스택의 꼭대기에 있는 요소를 제거하고 반환합니다.
예를 들어, 값 10, 20, 30, 40, 50을 순서대로 push한 뒤 pop을 수행하면 다음과 같이 동작합니다.
Deleted element = 50 Item = a [top] top --
이후 pop을 네 번 더 호출하면 40, 30, 20, 10 순서로 삭제됩니다.
Deleted element = 40 Deleted element = 30 Deleted element = 20 Deleted element = 10
모든 요소가 삭제된 상태에서 pop을 다시 호출하면 스택 언더플로(stack underflow)가 발생합니다.
스택의 두 가지 예외 상태
- 스택 오버플로(Stack Overflow) – 이미 가득 찬 스택에 요소를 삽입하려고 할 때 발생합니다.
- 스택 언더플로(Stack Underflow) – 비어 있는 스택에서 요소를 삭제하려고 할 때 발생합니다.
Push(), Pop(), Display() 알고리즘
각 연산의 핵심 알고리즘은 다음과 같습니다.
1. Push() 알고리즘
먼저 스택 오버플로 여부를 확인합니다.
if (top == n-1)
printf("stack over flow");
오버플로가 아니라면 top을 증가시킨 후 해당 위치에 요소를 저장합니다.
top++; a[top] = item;
2. Pop() 알고리즘
먼저 스택 언더플로 여부를 확인합니다.
if (top == -1)
printf("stack under flow");
언더플로가 아니라면 최상단 요소를 꺼낸 후 top을 감소시킵니다.
item = a[top]; top--;
3. Display() 알고리즘
스택이 비어 있는지 먼저 확인합니다.
if (top == -1)
printf("stack is empty");
비어 있지 않다면 bottom부터 top까지 모든 요소를 출력합니다.
for (i = 0; i <= top; i++)
printf("%d ", a[i]);
예제 프로그램: 배열로 구현하는 스택
다음은 배열을 이용해 스택을 구현한 C 프로그램입니다. 원본 코드의 오류(push/pop 호출 반복, 조건문 실수 등)를 수정하여 어떤 컴파일러에서도 동작하도록 정리했습니다.
#include <stdio.h>
#include <stdlib.h>
int top = -1, n, a[100];
void push(void);
void pop(void);
void display(void);
int main(void) {
int ch;
printf("enter the size of the stack: ");
scanf("%d", &n);
printf("\nstack implementation\n");
printf("1. Push\n");
printf("2. Pop\n");
printf("3. Exit\n");
do {
printf("\nEnter your choice: ");
scanf("%d", &ch);
switch (ch) {
case 1:
push();
display();
break;
case 2:
pop();
display();
break;
case 3:
exit(0);
default:
printf("invalid choice\n");
}
} while (ch >= 1 && ch <= 3);
return 0;
}
void push(void) {
int item;
if (top == n - 1) {
printf("stack over flow\n");
} else {
printf("enter an element for insertion: ");
scanf("%d", &item);
top++;
a[top] = item;
}
}
void pop(void) {
int item;
if (top == -1) {
printf("stack under flow\n");
} else {
item = a[top];
top--;
printf("deleted element = %d\n", item);
}
}
void display(void) {
int i;
if (top == -1) {
printf("stack is empty\n");
} else {
printf("contents of the stack: ");
for (i = 0; i <= top; i++)
printf("%d \t", a[i]);
printf("\n");
}
}
실행 결과
위 프로그램을 실행하면 다음과 같은 결과를 확인할 수 있습니다.
enter the size of the stack: 5 ← 사용자 입력 stack implementation 1. Push 2. Pop 3. Exit Enter your choice: 1 ← 사용자 입력 enter an element for insertion: 10 contents of the stack: 10 Enter your choice: 1 enter an element for insertion: 20 contents of the stack: 10 20 Enter your choice: 2 deleted element = 20 contents of the stack: 10 Enter your choice: 2 deleted element = 10 stack is empty Enter your choice: 2 stack under flow Enter your choice: 1 enter an element for insertion: 30 contents of the stack: 30
실행 결과에서 볼 수 있듯이, 가장 나중에 삽입된 값(20)이 가장 먼저 삭제되는 것을 통해 스택의 LIFO 특성을 명확히 확인할 수 있습니다. 또한 빈 스택에서 pop을 시도하면 언더플로 메시지가 출력되며, 예외 처리가 올바르게 동작하는 것도 알 수 있습니다.