[C++][자료구조] 연결 리스트로 구현한 큐 이해하기 (한줄씩 설명, 포인터)

line by line 으로 설명해보기

 

Node 클래스

class Node {
	int data;	// <데이터 필드> 일반 변수
	Node* link;	// <링크 필드> 포인터 변수 link
public:
	Node(int val) { data = val; link = NULL; }
	Node* getLink() { return link; }
	
	void setLink(Node* next) {
		link = next;
	}
	void display() {
		cout << data << endl;
	}
};

 

 

<클래스의 변수 선언>

int data;

노드의 데이터 필드 부분이다. 포인터 아님. 일반적인 변수.

 

Node* link;

노드의 링크 필드 부분이다. link는 포인터 변수임. 다음 노드의 주소를 link에 저장한다.

Node*는 노드의 주소를 뜻한다. 

 

<생성자와 함수 선언>

Node(int val) { data = val; link = NULL; }

생성자이다. 파라미터로 변수 값을 받음.

노드의 데이터필드 부분에 val값이 저장된다. 다음 노드의 주소를 저장하는 포인터 변수 link에는 공백문자열이 저장된다. (생성될 때는 다음 노드가 없으니까)

 

Node* getLink() { return link; }

Node*형 값을 반환하는 getLink() 함수. 포인터 변수인 link에 저장된 다음 노드의 주소를 반환한다.

 

void setLink(Node* next) {

    link = next;

}

Node*형을 파라미터로 갖는 setLink() 함수. 즉, next는 다음 노드의 주소를 뜻함. 

따라서 다음 노드의 주소를 저장하는 포인터 변수인 link에 next값이 저장된다.

 

void display() {

    cout << data << endl;

}

현재 노드의 데이터 필드(data)에 저장된 값을 출력한다.

 

 

 

 

여기까지 Node 클래스 설명이다

---

LinkedQueue 클래스

연결 리스트로 구현한 큐 클래스이다.

이 큐에서는 front가 항상 비어있는 상태가 아니다. 처음으로 enqueue를 하게 된다면 front와 rear이 같은 데이터를 가리킨다. 두 번째로 enqueue를 하면 front는 첫 번째 데이터를 가리키고 rear은 두 번째 데이터를 가리킨다.

 

class LinkedQueue {
	Node* front;
	Node* rear;
public:
	LinkedQueue() {
		front = NULL; rear = NULL;
	}
	~LinkedQueue() {
		while (!isEmpty())
			delete dequeue();
	}

	bool isEmpty() {
		return front == NULL;
	}

	// 삽입 연산: 연결된 큐의 맨 뒤에 노드 삽입 (rear에 삽입)
	void enqueue(Node* p) {
		if (isEmpty())
			front = rear = p;
		else {
			rear->setLink(p);
			rear = p;
		}
	}
    
	// 삭제 연산
	Node* dequeue() {
		if (isEmpty())
			return NULL;

		Node* temp = front;
		front = front->getLink();

		if (front == NULL)
			rear = NULL;

		return temp;
	}

	Node* peek() { return front; }

	void display() {
		cout << "[큐 내용]: " << endl;
		for (Node* p = front; p != NULL; p = p->getLink())
			p->display();
		cout << endl;
	}
};

 

<클래스의 변수 선언>

Node* front;

노드의 주소를 갖는 포인터 변수 front. 큐의 처음

Node* rear;

마찬가지로 노드의 주소를 갖는 포인터 변수 rear. 큐의 끝

 

<클래스의 생성자 선언>

LinkedQueue() {

    front = NULL; rear = NULL;

}

생성자. 큐의 front와 rear에 공백 문자열을 저장.

 

~LinkedQueue() {

    while (!isEmpty())

        delete dequeue();

}

삭제 생성자. 큐가 공백이 아니라면 while문을 반복한다. delete는 포인터 변수 (동적 메모리 할)를 제거하는 연산자이다.

dequeue는 Node*형을 반환한다. 포인터 변수이므로 delete를 사용하여 삭제한다.

 

<클래스의 함수들 선언>

bool isEmpty() {

    return front == NULL;

}

큐가 비었는지를 반환하는 함수. 큐의 front에 공백문자열(NULL)이 저장되어있다면 True 반환.

front는 Node*형의 포인터 변수이다. 큐에 하나라도 삽입된다면(노드의 주소가 rear에 삽입됨) front는 다음 노드의 주소를 저장하고 있어야 하므로 front는 공백문자열이 없어진다.

따라서 front가 NULL이면 다음 노드가 없다는 뜻이다.

 

void enqueue(Node* p) {

    if (isEmpty())

        front = rear = p;

    else {

        rear->setLink(p);

        rear = p;

    }

}

주석에 달아놨듯 큐의 삽입연산이다. rear에 삽입한다.

큐가 비어있는 상태였다면 front와 rear에 같은 주소(p)가 저장된다. (front는 다음 노드의 주소를 저장해야 하고, rear에는 현재(삽입한) 노드의 주소가 저장된다)

큐가 비어있는 상태가 아니었다면 rear(*Node형 포인터 변수)->setLink(p)를 통해 현재 rear의 link에 다음 노드의 주소인 p를 저장한다. 

rear는 마지막 노드를 가리키고 있어야 하므로 rear는 p가 된다. (뒤로 이동)

 

Node* dequeue() {

    if (isEmpty())

        return NULL;

 

    Node* temp = front;

    front = front->getLink();

 

    if (front = NULL)

        rear = NULL;

 

    return temp;

}

큐의 삭제 연산이다. 삭제하면서 Node*형을 반환한다. 

만약 큐가 비어있다면 공백 문자열(NULL)을 반환(return)한다. --> 함수 끝

아니라면 계속 진행

 

Node* 형의 포인터 변수 temp를 임시로 선언하고 front의 값을 저장한다.

front에는 getLink()함수를 통해 다음 노드의 주소를 반환받아 저장한다.

 

위 코드를 실행 후에 front가 비어있다면(공백문자열) rear에 공백문자열(NULL)을 저장한다.

즉, 큐가 비어있는 상태가 된다.

 

삭제한 노드를 반환해야 하므로 임시적으로 저장했던 temp를 반환한다.

 

Node* peek() { return front; }

큐는 선입선출이다. 먼저 들어온 데이터인 front를 반환한다. 

 

void display() {

    cout << "[큐 내용]: " << endl;

    for (Node* p = front; p != NULL; p = p->getLink())

        p->display();

    cout << endl;

}

큐를 모두 출력하는 함수. for문만 보자

포인터 함수 p를 선언, front값을 저장한다. p가 NULL이 아니라면 반복한다. 1회 반복 후에는 getLink()함수를 통해 p에 다음 노드의 주소를 저장한다.

끝까지 반복하면 p에 NULL이 저장된다. 왜냐하면 마지막 노드는 링크 필드에 NULL이 저장되기 때문이다.

front부터 rear까지 순서대로 노드의 데이터필드에 저장된 값을 출력한다.

 

---

큐 사용하기 (main함수)

 

void main() {
	LinkedQueue que;
	for (int i = 1; i < 10; i++)
		que.enqueue(new Node(i)); // 동적 메모리 할당
	que.display();

	delete que.dequeue();
	delete que.dequeue();
	delete que.dequeue();
	que.display();
}

 

LinkedQueue 클래스의 que 객체 선언.

new 연산자는 동적 메모리 할당을 뜻한다. new Node(i)는 Node 객체를 생성한다. 데이터필드에 i를 저장한다.

enqueue()함수로 큐에 저장한다. Node객체의 멤버 변수인 link에 다음 노드의 주소를 저장하는 과정도 enqueue에서 이루어진다.

 

delete 연산자는 동적 메모리 할당 제거를 뜻한다. que.dequeue()를 하면 먼저 들어온 값을 삭제하고 반환한다. 반환된 Node객체를 delete 연산자를 통해 할당되었던 동적 메모리를 제거한다. 

 

 

 

 

실행한 결과는 아래와 같다.