[Data Structure] 리스트로 큐 구현 연습

Queue 구현

#include <iostream>

struct Node {
	int data;
	Node* next;

	Node(int val) :data(val), next(nullptr) {}
};

class Que {
private:
	Node* front;
	Node* rear;

public:
	Que() : front(nullptr), rear(nullptr) {}
	~Que() {
		Node* curr = front;
		while (curr != nullptr) {
			//dequeue();
			Node* tmp = curr;
			curr = curr->next;
			delete tmp;
		}
	}
	bool isEmpty() const {
		return front == nullptr;
	}

	void enqueue(int val) {
		Node* node = new Node(val);
		if (isEmpty()) {
			front = rear = node;
		}
		else {
			rear->next = node;
			rear = node;
		}
	}

	int dequeue() {
		if (isEmpty()) {
			return -1;
		}
		Node* tmp = front;
		int val = front->data;
		front = front->next;

		if (front == nullptr) {
			rear = nullptr; 
			// rear은 할당되지 않은 주소를 참조 중 이였음.. 
			// 댕글링 포인터 문제가 발생할 수 있기에 객체가 삭제될때는 메모리 참조를 초기화 할 필요가 있다.
		}
		delete tmp;
		return val;
	}

	int peek() const {
		if (isEmpty()) {
			return -1;
		}
		return front->data;
	}
};

int main() {
	Que q;
	q.enqueue(10);
	q.enqueue(20);
	q.enqueue(30);

	std::cout << "Front element: " << q.peek() << std::endl;  // 출력: 10

	std::cout << "Dequeue: " << q.dequeue() << std::endl;     // 출력: 10
	std::cout << "Dequeue: " << q.dequeue() << std::endl;     // 출력: 20

	std::cout << "Front element after dequeue: " << q.peek() << std::endl; // 출력: 30

	return 0;
}

댕글링 포인터

리스트로 구현한 자료구조의 경우 isFull() 함수를 구현하지 않는다. 왜냐면 계속해서 동적메모리에 할당하면 되니깐!

enqueue()에서 Node* node = new Node(...); 로 계속해서 동적 할당되어 힙메모리를 차지한다. 그렇다면 반대로 dequeue 작업에서는 메모리를 해제해주어야 하고 그렇게 구현한다.

다만 주의할점으로 메모리만 제거한다고 끝이 아니라 해당 객체에 연결된 참조 포인터의 주소도 초기화 할 필요가 있다.

만약, 큐에 노드가 하나 남은 상태에서 dequeue를 실행하는 상황을 보자.

front -> rear -> node 남은 한 노드를 변수들이 가리키고 있는상태..

이 상태에서 일반적인 dequeue를 한다면, 현재 front는 front->next를 가리키게 된다. front->next는 nullptr을 가리키기에 nullptr로 자연스럽게 초기화가 된다.

이후 node를 delete를 하는 과정을 거친다. 하지만 여기서 , rear은 사라진 node를 가리키기에 nullptr로 초기화 해주어야 한다.

만약 초기화 하지 않은 큐의 rear는 삭제된 메모리 주소를 참조하게 되고 잠재적으로 이미 해제된 메모리를 참조할 위험이 생기게 된다.

이러한 포인터를 댕글링 포인터라고 한다.

int dequeue {
	...
		if (front == nullptr) {
			rear = nullptr; 
			// rear은 할당되지 않은 주소를 참조 중 이였음.. 
			// 댕글링 포인터 문제가 발생할 수 있기에 객체가 삭제될때는 메모리 참조를 초기화 할 필요가 있다.
		}