[Data Structure] C++로 나만의 큐 구현하기

코테 준비하다가 BFS 문제를 만났는데.. 알고리즘 공부를 너무 안 해서 BFS 구현이 헷갈린다. 그래도 검색 없이 자력으로 BFS 정도는 구현할 수 있어야지, 생각하다가 문득 그 전에 BFS에서 사용하는 큐를 구현할 줄은 아나? 싶어서 냅다 큐를 구현해보았다.

40분 정도 소요된 것 같고, 포인터 사용이 너무 오랜만이라 헤매다가 겨우 갈피를 찾았다. 하지만 확실한 것은 입학하고 1학년 때 객체지향프로그래밍 수업에서 구현하던 것보다 "포인터"라는 이론에 대한 개념이 어느 정도 잡혀있는 것을 느꼈다는 것. 검색 없이 이면지 하나로 그림 조금만 그려가면서 무리 없이 구현할 수 있었다.

#pragma once

template <typename T>
class Node {
public:
	T data;
	Node* next;
	Node* prev;

	Node() {
		data = NULL;
		next = NULL;
		prev = NULL;
	}
	Node(T _data) {
		data = _data;
		next = NULL;
		prev = NULL;
	}
};

#pragma once
#include "Node.h"

template <typename T>
class Queue {
	Node<T>* head;
	Node<T>* tail;

	int queue_size;

public:
	Queue() {
		head = new Node<T>();
		tail = new Node<T>();

		queue_size = 0;
	}

	int size() {
		return queue_size;
	}

	bool empty() {
		return queue_size == 0;
	}

	void push(T data) {
		Node<T>* newNode = new Node<T>(data);

		if (empty()) {
			head->next = newNode;
			tail->prev = newNode;
		}
		else if (queue_size > 0) {
			tail->prev->next = newNode;
			newNode->prev = tail->prev;
			tail->prev = newNode;
			newNode->next = tail;
		}
		queue_size++;
	}

	T pop() {
		if (empty()) {
			return NULL;
		}
		Node<T>* returnNode = new Node<T>();
		returnNode = head->next;
		head->next = head->next->next;
		head->next->prev = head;

		T return_value = returnNode->data;
		delete(returnNode);

		queue_size--;
		return return_value;
	}

	T front() {
		return head->next->data;
	}

	T back() {
		return tail->prev->data;
	}
};

처음 큐를 배울 때도 그랬지만 이번에도 역시 초기화와 포인터가 애를 먹였다. 노드를 만들었는데 필드 값 변경이 잘 안 되길래 디버깅을 해봤더니 NULL로 초기화해주는 것을 까먹은 것. 무슨 변수를 만들던 아무런 값을 넣지 않고 방치하는 습관을 고칠 필요가 있다.

클래스 생성자 만들기, 생성자에서 필드 항상 초기화해주기. 유니티 C# 스크립트는 이를 알아서 다 해주다 보니 이 습관을 버리고 살았는데, 상당히 나쁜 습관임을 새삼 깨달았다.