TIL 2025 04 16 CS50 / 스택, 큐, 딕셔너리 자료구조 정리

목차

1. 큐 (Queue)
2. 스택 (Stack)
3. 딕셔너리 (Dictionary)
4. 각 자료구조의 활용 및 비교

---

 

1. 큐 (Queue)

 

큐는 선입선출(FIFO: First-In First-Out) 방식으로 동작하는 선형 자료구조.

가장 먼저 들어온 데이터가 가장 먼저 나감.

 

1-1. 특징

• 입장과 퇴장이 반대 방향에서 일어남
• 줄 서기, 프린터 작업 대기열 등에 활용
• 배열 또는 연결 리스트 기반으로 구현 가능

 

1-2. 예시

#include <stdio.h>
#define SIZE 100

int queue[SIZE];
int front = 0, rear = 0;

void enqueue(int value) {
    if (rear < SIZE) {
        queue[rear++] = value;
    }
}

int dequeue() {
    if (front < rear) {
        return queue[front++];
    }
    return -1; // 큐가 비었을 때
}

int main() {
    enqueue(10);
    enqueue(20);
    printf("%d\n", dequeue()); // 10 출력
    return 0;
}

 

코드 흐름

• enqueue 함수로 큐에 값을 삽입하며, rear 인덱스를 한 칸 이동
• dequeue 함수로 front 인덱스에 위치한 값을 반환하고 front를 증가
• 따라서 삽입과 삭제가 각각 rear, front 기준으로 진행되며, 순서를 유지

---

 

2. 스택 (Stack)

 

스택은 후입선출(LIFO: Last-In First-Out) 방식으로 동작.

가장 마지막에 넣은 데이터가 가장 먼저 나감.

 

2-1. 특징

• 입장과 퇴장이 같은 방향에서 일어남
• 함수 호출, 괄호 검사, 되돌리기 기능 등에 활용
• 배열 또는 연결 리스트 기반으로 구현 가능

 

2-2. 예시

#include <stdio.h>
#define SIZE 100

int stack[SIZE];
int top = -1;

void push(int value) {
    if (top < SIZE - 1) {
        stack[++top] = value;
    }
}

int pop() {
    if (top >= 0) {
        return stack[top--];
    }
    return -1; // 스택이 비었을 때
}

int main() {
    push(10);
    push(20);
    printf("%d\n", pop()); // 20 출력
    return 0;
}

코드 흐름

• push 함수는 top을 증가시킨 뒤 해당 위치에 값을 저장.
• pop 함수는 현재 top 위치의 값을 반환하고 top을 감소시킴.
• 스택은 삽입(push)과 삭제(pop)이 같은 위치(top)에서 수행되어 후입선출 구조를 가짐.

---

 

3. 딕셔너리 (Dictionary)

 

딕셔너리는 키(key)와 값(value) 쌍으로 구성된 구조.

내부적으로는 해시 테이블을 기반으로 작동.

 

3-1. 특징

• 키를 통해 값을 빠르게 검색 가능 (평균 O(1))
• 키는 고유해야 하며, 값은 중복 가능
• 실제 사용 예: JSON, 사용자 정보 저장, 인덱싱 등

 

3-2. 간단한 해시 테이블 구조 예시 

#include <stdio.h>
#include <string.h>
#define SIZE 100

char* keys[SIZE];
char* values[SIZE];

int hash(char* key) {
    int hash = 0;
    while (*key) hash += *key++;
    return hash % SIZE;
}

void insert(char* key, char* value) {
    int idx = hash(key);
    keys[idx] = key;
    values[idx] = value;
}

char* get(char* key) {
    int idx = hash(key);
    if (keys[idx] && strcmp(keys[idx], key) == 0) {
        return values[idx];
    }
    return NULL;
}

int main() {
    insert("2024001", "Kim");
    insert("2024002", "Lee");
    printf("%s\n", get("2024001")); // Kim 출력
    return 0;
}

코드 흐름 설명

• hash 함수는 문자열 키의 각 문자 값을 더하여 인덱스를 생성.
• insert는 해당 해시 인덱스에 키와 값을 저장.
• get은 해시 인덱스에서 키를 비교한 뒤 일치할 경우 값을 반환.
• 이 구현은 충돌 처리 방식을 생략한 단순한 구조이므로, 실제 환경에선 체이닝 또는 오픈 어드레싱 등을 함께 사용해야 함.

 

---

 

4. 각 자료구조의 활용 및 비교

 

• 각 구조는 상황에 맞게 선택적으로 사용해야 하며, 문제 해결의 관점에서 자료구조의 선택이 효율성에 큰 영향을 줌.
• 적으로 사용해야 하며, 문제 해결의 관점에서 자료구조의 선택이 효율성에 큰 영향을 줌.