큐(Queue)

  스택 

스택과는 달리 하나의 입구와 하나의 출구를 가진 자료구조로 선입선출(First In Fist Out) 구조를 가진다.

 

- 삽입 연산(EnQueue)

큐에 데이터를 삽입하고 삽입된 데이터를 마지막으로 표시한다.

 

* 원본 데이터

인덱스	0 : FIRST	1	2	3 : REAR	4
데이터	10	20	30	40

인덱스	0 : FIRST	1	2	3	4 : REAR
데이터	10	20	30	40	50

 

- 인출 연산(DeQueue)

첫 데이터를 인출하고 해당 데이터 다음에 존재하는 데이터를 최상단으로 표시한다.

인덱스	0	1 : FIRST	2	3	4 : REAR
데이터	10	20	30	40	50

┗→ 10

 

  큐 구현 준비 

큐는 선형 리스트와 연결 리스트에서 모두 구현할 수 있는 기본적인 자료구조 중 하나이다.

 

구현에 필요한 메서드 및 속성은 다음과 같다.

• 생성자
  • Queue() 비어있고 기본 초기 용량을 가지는 인스턴스 생성
  • Queue(Queue&) 다른 Queue 데이터로 인스턴스 생성
  • Queue(int) 비어있고 지정한 초기 용량을 가지는 인스턴스 생성
• 속성 
  
  • Count Queue에 포함된 데이터의 개수
• 메서드 
  • Enqueue(data) Queue의 끝 부분에 데이터를 저장
  • Peek() Queue의 시작 부분의 데이터를 제거하지 않고 반환
  • Dequeue() Queue의 시작 부분의 데이터를 제거하고 반환
  • Clear() 저장되어 있는 모든 데이터 삭제
  • Contains(data) 데이터가 저장되어 있는지 여부 확인

 

큐 구현

ArrayList와 SinglyLinkedList를 이용하여 Queue를 구현한다.

 

Queue.h

#pragma once
// ArrayList를 사용하는 경우
#include "../ArrayList/ArrayList.h"

// SinglyLinkedList를 사용하는 경우
#include "../LinkedList/SinglyLinkedList.h"

class Queue
{
public:
#pragma region 생성자
	Queue(int capacity = 10);
	Queue(const Queue& other);
#pragma endregion

#pragma region 속성
	const size_t Count() { return m_items.Count(); }
#pragma endregion

#pragma region 메서드
	void Enqueue(int value);

	int Peek();
	int Dequeue();
	void Clear();

	bool Contains(int value);

	void PrintInfo();
#pragma endregion

private:
#pragma region 변수
	ArrayList m_items;
#pragma endregion
};

 

생성자 구현

기본 생성자와 Stack을 인자로 받는 복사 생성자를 구현한다.

 

Queue.cpp

/// <summary>
/// 비어있고 초기 용량을 가지는 Queue를 생성한다.
/// </summary>
/// <param name="capacity">생성할 공간의 크기(기본: 10)</param>
Queue::Queue(int capacity)
	: m_items(capacity)
{
}

/// <summary>
/// 다른 Queue와 동일한 값을 가지는 Queue를 생성한다.
/// </summary>
/// <param name="other">기준이 될 Queue</param>
Queue::Queue(const Queue& other)
	: m_items(other.m_items)
{
}

 

데이터 삽입 메서드 구현

데이터 삽입 연산에 필요한 메서드들을 구현한다.

 

Queue.cpp

/// <summary>
/// Queue의 끝 부분에 값을 추가한다.
/// </summary>
/// <param name="value">추가할 값</param>
void Queue::Enqueue(int value)
{
	m_items.Add(value);
}

 

데이터 인출 메서드 구현

데이터 인출 연산에 필요한 메서드들을 구현한다.

 

Queue.cpp

/// <summary>
/// Queue의 시작 부분을 제거하지 않고 반환한다.
/// </summary>
/// <returns>시작 부분에 있는 값</returns>
int Queue::Peek()
{
	if (m_items.Count() <= 0)
	{
		throw std::out_of_range("empty");
	}

	return m_items.Item(0);
}

/// <summary>
/// Queue의 시작 부분의 값을 제거한 뒤 반환한다.
/// </summary>
/// <returns>시작 부분에 있던 값</returns>
int Queue::Dequeue()
{
	if (m_items.Count() <= 0)
	{
		throw std::out_of_range("empty");
	}

	int data{ m_items.Item(0) };
	m_items.RemoveAt(0);

	return data;
}

/// <summary>
/// Queue의 모든 값을 제거한다.
/// </summary>
void Queue::Clear()
{
	m_items.Clear();
}

 

기능 메서드 구현

자료구조를 효율적으로 사용하기 위한 기능 메서드를 구현한다.

 

Queue.cpp

/// <summary>
/// Queue에 지정한 값이 존재하는지 확인한다.
/// </summary>
/// <param name="value">Queue에서 찾을 값</param>
/// <returns>값의 존재 여부</returns>
bool Queue::Contains(int value)
{
	return m_items.Contains(value);
}

 

참고문헌

Microsoft MSDN.Queue 클래스 (System.Collections)