[자료 구조] 원형 버퍼 CircularBuffer

배열 기반 원형 버퍼

원형 버퍼

• 덱(deque)과 리스트(list)처럼 맨 앞과 맨 뒤의 데이터에 대한 접근이 가능하다.
• 이를 위해 Head와 Tail에 대한 인덱스가 존재한다.
• 새로 삽입되는 데이터는 TailIdx에 삽입되며 가장 먼저 꺼내지는 데이터는 HeadIdx가 지칭한다.
• 메모리의 연속성 이점을 사용하기 위해 배열로 많이 구현하여 사용할 수 있다.

#pragma once
#include <iostream>
#include <cassert>

template<typename T>
class CircularBuffer
{
private:
	static constexpr int MAX_QUEUE_LENGTH = 8;

private:
	T m_arrBuffer[MAX_QUEUE_LENGTH];
	int m_iTailIdx;
	int m_iHeadIdx;

public:
	CircularBuffer();
	~CircularBuffer();

public:
	void Push(const T& data)
	{
		m_arrBuffer[m_iTailIdx] = data;
		m_iTailIdx = (m_iTailIdx + 1) % MAX_QUEUE_LENGTH;
	}

	T Pop()
	{
		T data = m_arrBuffer[m_iHeadIdx];
		m_iHeadIdx = (m_iHeadIdx + 1) % MAX_QUEUE_LENGTH;
		return data;
	}

	T& Front()
	{
		return m_arrBuffer[m_iHeadIdx];
	}

	T& Back()
	{
		return m_arrBuffer[m_iTailIdx];
	}

	void Print()
	{
		for (int i = 0; i < MAX_QUEUE_LENGTH; ++i)
		{
			std::cout << m_arrBuffer[i];
			if (i == m_iHeadIdx)
			{
				std::cout << "[Head]";
			}
			if (i == m_iTailIdx)
			{
				std::cout << "[Tail]";
			}
			std::cout << " , ";
		}
		std::cout << std::endl;
	}
};

template<typename T>
inline CircularBuffer<T>::CircularBuffer()
	:
	m_arrBuffer{},
	m_iTailIdx(0),
	m_iHeadIdx(0)
{
}

template<typename T>
inline CircularBuffer<T>::~CircularBuffer()
{
}

고려사항

• TailIdx가 HeadIdx를 넘어설 때, 꺼내질 HeadIdx가 가장 최근에 삽입된 데이터가 아닐 수도 있다. (FIFO가 되지 않음)
• 배열 기반은 항상 고정된 크기의 메모리를 차지한다. (적당한 크기를 잡아야한다.)