[알고개념] 8. 자료구조

1. Stack

스택은 FILO(First In Last Out) 구조로, 새로운 데이터가 기존의 데이터 위에 차곡차곡 쌓이는 자료구조이다.

• push X: 정수 X를 스택에 넣는 연산
• pop: 스택에서 가장 위에 있는 정수를 빼는 연산
• size: 스택에 들어있는 정수의 개수
• empty: 스택이 비어있는지 여부
• top: 스택의 가장 위에 있는 정수

 

2. Queue

큐는 FIFO(First In First Out) 구조로, 줄세우기와 같은 자료구조이다. 

• push X: 정수 X를 큐에 넣는 연산
• pop: 큐에서 가장 앞에 있는 정수를 빼는 연산
• size: 큐에 들어있는 정수의 개수
• empty: 큐가 비어있는지 여부
• front: 큐의 가장 앞에 있는 정수
• back: 큐의 가장 뒤에 있는 정수

 

 3. Array, Linked List

배열은 같은 Type의 데이터를 연속된 주소에 저장한다. 삽입과 삭제가 느리지만, 데이터에 접근하는 것이 빠르다. 연결 리스트는 노드들로 구성되어 있는데, 연속된 주소에 저장되지 않는다. 노드는 Data와 Link로 구성되어 본인 다음에 어떤 노드가 올지에 대한 정보가 저장되어 있다. 삽입과 삭제가 빠르지만, 데이터에 접근하는 것이 느리다.

typedef struct NODE {
    int data;
    struct NODE *link;
} NODE;

NODE* insert_NODE(NODE *plist, NODE* prev, int data) {
    NODE* pnew = NULL;
    if (!(pnew = (NODE*) malloc(sizeof(NODE)))) {
        printf("메모리 동적할당 오류\n");
        exit(1);
    }

    pnew->data = data;
    if (prev == NULL) { // 연결리스트 맨 앞에 삽입
        pnew->link = plist;
        plist = pnew;
    } else { // 연결 리스트 중간에 삽입
        pnew->link = prev->link;
        prev->link = pnew;
    }
    return plist;
}

NODE* delete_NODE(NODE *plist, NODE* prev, NODE *curr) {
    if (prev == NULL) plist = curr->link;
    else prev->link = curr->link;
    free(curr);
    return plist;
}

void print_list(NODE* plist) {
    NODE *p = plist;
    printf("(");

    while (p) {
        printf("%d", p->data);
        p = p->link;
    }
    printf(")\n");
}

 

4. Priority Queue

우선순위 큐는 말그대로 우선순위가 부여된 순서대로 정렬되서 들어가는 큐이다. 사용자 지정 함수를 이용하여 compare 함수를 넣어주면 우리가 원하는 우선순위를 부여해줄 수 있다.

struct Student {
    int id;
    int math, eng;
    Student(int num, int m, int e) : id(num), math(m), eng(e) {}
};
 
// 학번을 기준으로 학번(id) 값이 큰 것이 Top 을 유지 하도록 한다.
struct cmp {
    bool operator()(Student a, Student b) {
        return a.id < b.id;
    }
};

int main() {
	priority_queue<Student, vector<Student>, cmp> pq;
}