큐 (Queue) - c++ : 큐 리스트, 서클큐(CircleQueue) 구현

 

▶️ 큐 (Queue)

 

• 선입선출 방식의 자료구조 입니다.
  • 먼저 들어간 요소가 먼저 방출되는 방식입니다.

 

• 선형적인 자료구조 입니다.
  • 자료의 저장과 출력이 한줄로 표현될 수 있습니다.

 

• 큐의 종류(파생된 큐들)에는 우선순위큐, 서클큐(Circle Queue) 등이 있습니다.

 

• 큐에 동적 배열을 사용하는것은 효율이 좋지 않습니다.

 

 

 

▶️ 리스트를 사용한 큐 구현 예시 

Queue.h

큐 노드와 큐를 구현한 코드입니다.

// Queue.h
#pragma once
#include <assert.h>

template <typename T>
class CQueueNode
{
	template <typename T>
	friend class CQueue;
    
public :
	CQueueNode(){}
	~CQueueNode(){}
    
private :
	T data;
	CQueueNode<T> * mNext = nullptr;
}

template <typename T>
class CQueue
{
public :
	CQueue(){}
	~CQueue(){}
    
private :
	// 들어온지 제일 오래된 노드를 가르킬 포인터
	CQueueNode<T> * mBegin 	= nullptr;
	// 들어온지 제일 얼마안된 노드를 가르킬 포인터
	CQueueNode<T> * mLast 	= nullptr;
	int mSize = 0;
    
public :
	bool empty() const { return mSize == 0 ; }
    
	void push( const T & data )
    {
		CQueueNode<T> * node = new CQueueNode<T>;
		node->mData = data;
        
		if( !mBegin )
			mBegin = node;
		else 
			mLast->mNext = node;
            
		mLast = node;
		mSize++;
	}
    
	T pop()
	{
		assert( mSize != 0 );
        
		CQueueNode<T> * node = mBegin->mNext;
		T data = mBegin->mData;
        
		delete mBegin;
        
		mBegin = node;
		mSize--;
        
		if( mSize == 0 )
			mLast = nullptr;
            
		return data;
	}
    
	void clear()
	{
		while( mBegin )
		{
			CQueueNode<T> * node = mBegin->mNext;
			delete mBegin;
			mBegin = node;
		}
		mSize = 0;
		mLast = nullptr;
		mBegin = nullptr;
	}
};

main.cpp

#include <iostream>
#include "Queue.h"

int main()
{
	CQueue<int> queue;

	queue.push( 0 );
	queue.push( 3 );
	queue.push( 5 );

	while ( !queue.empty() )
	{
		std::cout << "pop : " << queue.pop() << std::endl;
	}
	return 0;
}

 

 

▶️ 배열을 이용한 서클큐(Circle Queue)

• 위의 리스트를 이용한 큐는 push와 pop을 반복할때 계속 주소가 바뀌었다면

서클큐는 한정된 공간을 미리 할당하는 방식입니다.

• 서클큐에서의 push는 마지막(tail)에 추가된 인덱스의 다음부터 요소를 추가하지만

배열의 끝까지 추가할 경우, 배열의 첫 인덱스로 이동하여 추가를 합니다.

• 서클큐에서의 pop 또한 push와 동일하게 제일 오래된 인덱스의 요소(head)부터 제거하다가

배열의 끝 요소까제 제거할 경우, 배열의 첫 인덱스로 이동하여 요소를 제거합니다.   

 

 node1을 push한 상태입니다. head는 node1을 가르키고 tail은 node1의 다음을 가르킵니다

 

 

Node2를 push후, pop을 한번 실행한 상태입니다

Node2를 push하며 tail은 다음 추가할 인덱스를 가지고 있고

pop을 실행하여 Node1이 제거되고 head는 그 다음 인덱스인 node2의 인덱스를 가지고 있습니다.

 

 

Node 3, Node4, Node5순으로 push한 상태입니다.

node5를 추가한 후 배열의 최대 크기만큼의 인덱스를 가르키던 tail은

배열의 첫 node를 가르킵니다.

 

 

위 예시처럼 

tail과 head가 배열의 마지막 인덱스를 가지고 있을 때 

push와 pop를 실행한다면 push와 pop을 실행 후, 배열의 첫 인덱스값을 가지게 됩니다.

 

 

 

 

 

▶️ 배열을 이용한 써클큐(CircleQueue) 의 구현 

• mTail : 제일 최근에 추가된 요소의 인덱스를 가르킴
• mHead : 제일 마지막에 추가된 요소의 인덱스를 가르킴

queue.h

template <typename T, int Count = 100>
class CCircleQueue
{
public :
	CCircleQueue() {}
	~CCircleQueue() {}

private :
	T mArray[Count] = {};
	int mSize = 0;
    // 제일 최근에 추가된 요소의 인덱스+1 (배열이 가득 찰 경우 배열 첫인덱스)을 저장하는 인덱스값
	int mTail = 0;
    // 제일 마지막에 추가된 요소의 인덱스+1 (배열이 가득 찰 경우 배열 첫인덱스)을 저장하는 인덱스값
	int mHead = 0;

public : 
	bool empty() const { return mSize == 0; }

	bool full() const { return mSize == Count; }

	void clear()
	{
		mSize = 0;
		mTail = 0;
		mHead = 0;
	}

	void push( const T& data )
	{
		assert( !full() );

		mArray[mTail] = data;
		mTail = ( mTail + 1 ) % Count;

		++mSize;
	}

	T pop()
	{
		assert( !empty() );
		
		T data = mArray[mHead];
		mHead = ( mHead + 1 ) % Count;

		--mSize;

		return data;
	}
};

main.cpp

#include <iostream>
#include "Queue.h"

int main()
{
	CCircleQueue <int, 10> circleQueue;

	circleQueue.push( 0 );
	circleQueue.push( 3 );
	circleQueue.push( 5 );
	circleQueue.push( 7 );

	std::cout << "pop : " << circleQueue.pop() << std::endl;

	circleQueue.push( 9 );

	while ( !circleQueue.empty() )
	{
		std::cout << "pop : " << circleQueue.pop() << std::endl;
	}

	return 0;
}