[DS] 연결리스트(Linked list)를 이용한 큐(Queue) 구현

↓↓↓        연결 리스트(Linked list)와 큐(queue) 먼저 공부하기      ↓↓↓

 

https://yyyeji.tistory.com/364

[DS] 큐(Queue)란?

 

https://yyyeji.tistory.com/365

[DS] 연결 리스트(Linked List)란?

 

 

 

연결 리스트(linked list)를 이용한 큐(queue)을 구현하기 위한 ADT 정의

---

class node {
public:
    string name;
    double score;
    node *link;
    void set_data(string s, double d);
};

 

데이터와 포인터를 포함한 node 클래스를 만들어줍니다.

포인터는 node 클래스를 가르키기 때문에 node type으로 정의합니다.

 

 

class linked_queue {
    node *front, *rear;
public:
    linked_queue();
    void insert_q(node t);
    node delete_q();
    bool queue_empty();
};

linked_queue - 연결 리스트(linked list)를 생성한 초기 상태

insert_q - queue rear에 원소 하나 추가

delete_q - queue front에서 원소 하나 제거

queue_empty - 현재 queue가 empty인지에 대한 상태 확인

 

 

 

함수 구현

---

void node::set_data(string s, double d) {
    name = s;
    score = d;
}

node class의 data를 셋팅(setting)해주는 메소드(method)입니다.

 

 

linked_queue::linked_queue() {
    front = NULL;
    rear = NULL;
}

linked queue class의 생성자(constructor)에서는 fron와 rear을 NULL로 초기화시켜 줍니다.

 

 

void linked_queue::insert_q(node t) {
    node *p;
    p = new node;
    (*p) = t;

    p->link = NULL;
    if(rear != NULL) rear->link = p;
    else front = p;

    rear = p;
}

원소 추가는 rear에서 이뤄집니다. 

 

원소가 추가될 때 new node의 link는 마지막 node이기 때문에 NULL로 만들어줍니다.

만약 rear가 NULL이 아니면 rear의 link를 new node에 연결해주고, rear가 NULL이라면 front에도 new node를 넣어줍니다.

 

rear = p;

어떤 상황이든 rear는 new node입니다.

 

 

node linked_queue::delete_q() {
    node tmp;
    node *t;

    t = front;
    tmp = *front;

    front = front->link;
    delete t;
    if(front == NULL) rear = NULL;

    return tmp;
}

원소 삭제는 front에서 이뤄집니다.

 

front = front->link;

그렇기 때문에 원소가 삭제되기 전에 front의 link를 삭제될 node의 다음 node로 연결시켜줘야 됩니다.

 

if(front == NULL) rear = NULL;

front가 NULL이면 연결 리스트(linked list)가 비었다는 의미이기 때문에 rear도 NULL로 만들어 줍니다.

 

 

 

bool linked_queue::queue_empty() {
    if(front == NULL) return true;
    else return false;
}

queue_empty는 연결 리스트(linked list)로 구현된 큐(queue)이 empty 상태인지 확인하는 함수입니다.

현재 front가 NULL이면 true를 return 해줍니다.

 

 

 

main 함수 구현

---

int main() {
    linked_queue lq;
    node tmp;

    tmp.set_data("A", 100);
    lq.insert_q(tmp);
    tmp.set_data("B", 90);
    lq.insert_q(tmp);
    tmp.set_data("C", 80);
    lq.insert_q(tmp);
    tmp.set_data("D", 70);
    lq.insert_q(tmp);
    
    tmp = lq.delete_q();
    cout << tmp.name << " : " << tmp.score <<"\n";
    tmp = lq.delete_q();
    cout << tmp.name << " : " << tmp.score <<"\n";
}

원소가 들어간 순서대로 제거되기 때문에 결과가 제대로 출력된 것을 확인할 수 있습니다.

 

 

 

◡̈