자료구조 기초 — 스택, 큐, 연결 리스트

지금까지는 int data[100]; 과 같은 배열을 주로 사용했습니다. 배열은 인덱스(data[3])를 통해 빛의 속도로 접근(O(1))할 수 있다는 강력한 장점이 있습니다.

하지만, 만약 배열의 한가운데에 있는 데이터를 지우거나(삭제), 중간에 새 데이터를 끼워 넣으려면(삽입) 그 뒤에 있는 모든 데이터를 한 칸씩 밀거나 당겨야 하는 막대한 연산(O(n))이 발생합니다.
이러한 목적에 따라 데이터를 효율적으로 담는 그릇을 바꾸는 것이 바로 자료구조의 핵심입니다.

스택은 프링글스 통이나 접시 무더기와 같습니다. 마지막에 넣은 것(Last In)이 가장 먼저 나옵니다(First Out).

• Push : 데이터를 꼭대기에 쌓기
• Pop : 제일 꼭대기에 있는 데이터 꺼내기
• Top : 현재 가장 꼭대기 위치를 가리키는 인덱스

int stack[100];
int top = -1; // 데이터가 하나도 없을 때의 기본값

void push(int value) {
    stack[++top] = value; // top을 1 올리고 그 자리에 저장
}

int pop() {
    return stack[top--];  // 현재 top의 값을 꺼내고 top을 1 내림
}

큐는 은행 창구 대기열이나 맛집 웨이팅과 같습니다. 먼저 들어온 데이터(First In)가 먼저 나갑니다(First Out).

• Enqueue : 줄 맨 뒤에 추가하기
• Dequeue : 줄 맨 앞에 있는 데이터 처리 후 빼기
• Front : 맨 앞 (출구), Rear : 맨 뒤 (입구)

배열의 가장 큰 단점(크기 고정, 중간 삽입/삭제의 어려움)을 포인터로 해결한 자료구조입니다. 데이터를 메모리의 흩어진 공간에 동적 할당(malloc)하고, 각 데이터가 "다음 데이터의 주소"를 들고 있게 만들어 기차처럼 연결합니다.

struct Node {
    int data;              // 실제 저장할 값
    struct Node *next;     // 자기 자신과 똑같이 생긴 '다음 노드'의 주소!
};

// 새로운 노드를 생성(malloc)하고 값을 넣은 뒤 연결하는 방식