자료구조 계속~, 함수 오버로딩
스택, 큐 vs 리스트, 배열
이 섹션은 “스택과 큐”라는 추상 자료구조와, 그것을 실제 메모리 위에 구현하는 방법(배열 vs 연결 리스트)을 비교해 줍니다. 초심자가 이해하기 쉽게 핵심만 정리합니다.
추상 vs 구현
- 스택(Stack), 큐(Queue)는 동작 규칙(추상): 스택은 LIFO, 큐는 FIFO.
- 배열(Array)와 연결 리스트(Linked List)는 그 추상 규칙을 실현하는 구체적 자료구조(메모리 배치와 관리 방법).
즉, 스택/큐는 “어떻게 동작해야 하는가”를 정의하고, 배열/리스트는 “메모리에서 실제로 어떻게 배치하고 관리할 것인가”를 결정합니다.
메모리 관점(연속 vs 비연속)
- 배열: 연속된 메모리 블록을 사용합니다. 인접한 요소들이 메모리에서 붙어 있으므로 캐시 친화적이고 인덱스 접근이 빠릅니다.
- 연결 리스트: 노드가 힙에 흩어져 있고 포인터로 연결됩니다. 삽입/삭제는 포인터 조작만으로 빠르지만, 캐시 성능이 떨어지고 포인터 오버헤드가 있습니다.
간단한 구현 예제 (C 스타일, 핵심만)
배열 기반 스택 (고정 크기):
#define MAX 100
int stack[MAX];
int top = -1;
void push(int v){ if(top < MAX-1) stack[++top] = v; }
int pop(void){ if(top>=0) return stack[top--]; return -1; }
리스트 기반 스택 (헤드에서 push/pop):
struct Node { int v; struct Node* next; };
struct Node* head = NULL;
void push(int v){ struct Node* n = malloc(sizeof *n); n->v=v; n->next=head; head=n; }
int pop(void){ if(!head) return -1; int r=head->v; struct Node* t=head; head=head->next; free(t); return r; }
배열(원형 버퍼) 기반 큐:
#define QMAX 128
int q[QMAX]; int r=0,w=0; // r: 읽기, w: 쓰기
int empty(){ return r==w; }
int full(){ return ((w+1)%QMAX)==r; }
void enqueue(int v){ if(!full()){ q[w]=v; w=(w+1)%QMAX; } }
int dequeue(){ if(!empty()){ int x=q[r]; r=(r+1)%QMAX; return x; } return -1; }
리스트 기반 큐 (헤드/테일 유지):
struct QNode { int v; struct QNode* next; };
struct QNode *qhead=NULL, *qtail=NULL;
void enqueue(int v){ struct QNode* n=malloc(sizeof *n); n->v=v; n->next=NULL; if(qtail) qtail->next=n; else qhead=n; qtail=n; }
int dequeue(void){ if(!qhead) return -1; int r=qhead->v; struct QNode* t=qhead; qhead=qhead->next; if(!qhead) qtail=NULL; free(t); return r; }
장단점 요약
- 배열 기반
- 장점: 단순하고 메모리 연속으로 캐시 친화적, 인덱스 접근 빠름.
- 단점: 고정 크기일 경우 공간 한계, 동적 확장 시 재할당 비용.
- 리스트 기반
- 장점: 삽입/삭제가 노드 연결만 바꾸면 되므로 유연.
- 단점: 포인터 오버헤드, 캐시 불리, malloc/free 비용과 단편화.
언제 무엇을 쓸까
- 자료 크기와 변경 빈도를 예측할 수 있고 성능(캐시)을 중시하면 배열(또는 동적 배열/vector)을 사용하세요.
- 삽입/삭제가 빈번하고 크기가 유동적이면 리스트가 편리하지만, 실제 성능을 반드시 측정하세요(할당 비용이 큰 영향을 미침).
간단 정리: 스택/큐는 규칙(추상)이고, 배열/리스트는 그 규칙을 메모리 위에 구현하는 두 가지 대표적인 방법입니다. 구현 선택은 메모리 레이아웃(연속/비연속), 성능, 메모리 제약을 고려해 결정하세요.
다양한 타입들을 자료구조에 넣는 방법
C 예시
struct snode {
struct snode* next; /* MQ1. ���� SNode�� �ȹٲ㵵 ��? */
struct snode* prev;
struct data_polymolph* data;
};
enum type
{
Human,
Animal,
};
struct data_polymolph {
enum type type;
void* data;
};
struct Human
{
int id;
};
struct Animal
{
int id;
};
int main()
{
{
struct Human a;
struct data_polymolph data;
data.type = Human;
data.data = (void*)&a;
}
{
struct Animal a;
struct data_polymolph data;
data.type = Animal;
data.data = (void*)&a;
}
struct data_polymolph data;
struct Human* human = NULL;
struct Animal* animal = NULL;
switch (data.type)
{
case Human:
human = (struct Human*)data.data;
break;
case Animal:
animal = (struct Animal*)data.data;
break;
default:
break;
}
return 0;
}
자료구조에 다양한 타입을 넣을일은 일반적으로 없으나, C에서 추가 문법적인 지원은 없음.
이에 대해 Cpp의 다형성에서 좀 더 자세하게 다룸.
함수 오버로딩 (C++ 문법)
요지: C++에서는 같은 이름의 함수를 여러 개 정의할 수 있습니다. 다만 매개변수(타입, 개수, 순서)가 달라야 합니다. 이를 “함수 오버로딩”이라고 부릅니다. C에서는 같은 이름을 여러 번 정의할 수 없지만, C++은 허용합니다.
간단한 예:
void func(int a);
void func(void* b);
int main() {
func(1); // 정수 버전 호출
func(nullptr); // void* 버전 호출
}
왜 가능한가? (심볼과 이름 장식)
- 컴파일러는 링크 시 함수를 구분하기 위해 함수 이름에 매개변수 타입 정보를 붙여서 내부 심볼을 만듭니다. 이를 이름 장식(name mangling) 또는 심볼 맹글링이라고 합니다. 예:
func_int처럼 보이는 형태로 바뀝니다(실제 형식은 컴파일러마다 다름). - 덕분에 동일한 원시 이름(func)을 가진 여러 함수를 서로 다른 심볼로 구분해 링킹할 수 있습니다.
오버로드 선택 규칙(요약)
- 호출 시 컴파일러는 가능한 후보들 중에서 가장 적합한 함수를 선택합니다. 기본 원칙은 “정확히 일치하는 타입 > 표준 변환(정수 승격, 부동소수점 변환 등) > 사용자 정의 변환” 순서입니다.
- 암시적 변환이 여러 후보에 적용되어 어느 쪽이 더 좋은지 결정되지 않으면 “모호(ambiguous)”로 컴파일 오류가 납니다.
예외와 주의사항
- 반환 타입만 다른 함수는 오버로딩할 수 없습니다. 예:
int f(); double f();는 에러입니다. 호출문만으로 어떤 것을 호출해야 할지 알 수 없기 때문입니다. - 기본 인자(default argument)는 오버로딩과 섞이면 혼동을 만들 수 있으니 주의하세요.
- 멤버 함수는
const/&(ref-qualifier) 같은 CV/참조 한정자에 따라 오버로딩할 수 있습니다:
struct S {
void m(); // 비-const 버전
void m() const; // const 객체에서 호출되는 버전
};
extern “C”와 오버로딩
extern "C"는 C 호환 심볼을 생성하도록 지시하여 이름 장식을 하지 않습니다. 따라서extern "C"로 선언된 함수들은 오버로딩할 수 없습니다(심볼 충돌).
함수 템플릿과 오버로딩
- 함수 템플릿도 다른 함수들과 함께 오버로드될 수 있습니다. 구체화된(특수화된) 버전과 일반 버전 간의 우선순위 규칙을 이해해야 합니다.
디버깅/검사: 실제 심볼 보기
- 컴파일된 바이너리에서 심볼을 보면 어떤 이름으로 변환됐는지 확인할 수 있습니다. 예: 리눅스에서
nm이나objdump -t를 쓰고c++filt로 복원(demangle)하면 원래의 함수 시그니처를 볼 수 있습니다. Windows에서도 디스어셈블러나 심볼 도구에서 비슷한 정보를 확인할 수 있습니다.
간단한 실전 예제
#include <iostream>
void print(int x) { std::cout << "int: " << x << '\n'; }
void print(const char* s) { std::cout << "cstr: " << s << '\n'; }
int main() {
print(3); // print(int)
print("hi"); // print(const char*)
// print(nullptr); // nullptr는 const char* 또는 void* 등에 매치되니 주의
}
요약
- C++의 함수 오버로딩은 같은 이름으로 여러 행동을 정의할 수 있게 해 주어 API를 더 읽기 쉽게 만듭니다.
- 컴파일러는 매개변수 타입 정보를 사용해 어떤 함수를 호출할지 결정합니다(이 과정에서 이름 장식과 오버로드 해소가 작동).
- 반환 타입만으로는 오버로딩할 수 없고, 모호성이나 암시적 변환에 주의해야 합니다.
- 자세한 심볼에 대해서 내용은 name magling 참고.