[자료구조] 간단한 Queue 구현

 

 

 

 

 

자료구조

Queue는 선형 자료구조(FIFO-First in First Out)이며 한쪽에서는 입력이 한쪽에서는 출력이 이루어지는 자료구조이다.

Stack과는 반대 개념의 자료구조이며 프린터의 출력 처리나 윈도 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다. Key 입력 등

Queue 자료구조

 

소스코드

#pragma once
#include<iostream>
/*--

Queue method
	push()
	pop()
	empty()
	front()
	size()
Custom method;
	DisplayAll();
	clear();
	capacity()
--*/


typedef bool BOOL;
template<class T>
class pQueue;

template<class T>
class Node {
private:
	Node* next_;
	T value_;
public:
	friend pQueue<T>;
	Node(const T& lhs) :value_(lhs), next_(nullptr) {}
};

template<class T>
class pQueue {
private:
	Node<T>* head_;
	Node<T>* tail_;
	size_t size_;
public:
	pQueue() {
		head_ = new Node<T>{ 0 };
		tail_ = new Node<T>{ 0 };
		head_->next_ = nullptr;
		tail_->next_ = nullptr;
		size_ = 0;
	}
	void Push(const T& lhs) {
		Node<T>* node = new Node<T>{ lhs };
		if (Empty())
			head_ = node;
		tail_->next_ = node;
		tail_ = node;
		++size_;
	}
	void Push(const T&& lhs) {
		Node<T>* node = new Node<T>{ lhs };
		if (Empty())
			head_ = node;
		tail_->next_ = node;
		tail_ = node;
		++size_;
	}
	T Pop() {
		//Not Safety Pop
		Node<T>* node = nullptr;
		T value = head_->value_;
		head_ = head_->next_;
		if (node != nullptr)
			delete node;
		--size_;
		return value;
	}
	BOOL Empty()const {
		return (0xFFFFFFFF & size_) == 0 ? true : false;
	}
	T Front()const {
		return head_->value_;
	}
	size_t Size()const { return size_; }

	void DisplayAll()const {
		Node<T>* curr = nullptr;
		curr = head_;
		std::cout << "Display ALL: ";
		while (curr != nullptr) {
			std::cout << curr->value_ << ", ";
			curr = curr->next_;
		}
		std::cout << std::endl;
	}
	void Clear() {
		Node<T>* curr = nullptr;
		curr = head_;
		while (curr != nullptr) {
			Node<T>* deleteNode = nullptr;
			deleteNode = curr;
			curr = curr->next_;
			if (deleteNode != nullptr) {
				delete deleteNode;
				--size_;
			}
		}
	}
	size_t Capacity()const {
		return sizeof(this) * size_;
	}
};

 

 

후기

 

노드 구성도

두 번째로 구현해본 자료구조 Queue이다. Stack과 다르게 포인터가 두 개로 구성되어 있으며 책이나 인터넷을 안 보고 혼자 생각하면서 구현하다 보니 생각보다 시간이 걸렸는데 다음 자료구조부터가 걱정이다. 

이번에도 Template을 사용해서 어떤 자료 형태에서도 돌아갈 수 있게 만들었으며 R-value에 대응할 수 있게 생성자 또한 추가하였다. 그리고 기존 queue에 없는 Method를 3개 추가하였다. 

Method 이름	용도
DisplayAll()	Node의 모든 value 출력
Clear()	모든 Node 삭제
Capacity()	현재 Queue의 메모리 크기 출력

 

 

출처 및 레퍼런스

Wiki: https://ko.wikipedia.org/wiki/큐_(자료_구조)