큐 Queue

Category:

1. 큐란 무엇인가?

2. 메소드와 필드에는 무엇이 있는가?

3. 구현(implementation)문제에 의한, 2가지 구현 방법

- Circular design

- length 추가

4. 실제 구현

5. 추가문제

---

1.큐란 무엇인가?

 

스택의 LIFO(후입선출 ,선입후출, Last-in-Last-out)와 달리 큐는 FIFO(선입선출, First-in-first-out)이다.

 

젠가박스를 생각해보자,

 

한쪽만 뚫려있는 젠가박스에 젠가를 넣고 빼는것을 상상해보면, 후입선출, 즉 스택이다.

 

양쪽이 뚫려있는 젠가박스에 젠가를 넣고 반대쪽으로 빼는것을 생각해보면, 선입선출, 즉 큐다.

 

롤 클라이언트 대기열도 위와같은 스택의 자료구조형을 가진다.

---

2. 메소드와 필드에는 무엇이 있는가?

 

필드:

 

rear , front, maxQue 그리고 가장 중요한, ItemType * items가 있을것이다.

 

(실은 큐에선 rear와 front가 가장 중요하다.)

 

메소드:

 

EnqueueDequeue (큐에서 없애기도 하지만, 해당 큐를 뽑아내는일도 겸한다.)IsFullIsEmpty

 

---

3. 구현 문제에 의한 2가지 방법

 

-Circular design의 경우

 

#1. Ciruclar에서 IsFull과 IsEmpty는 rear과 front의 상대적인 위치로 파악할 수 없다.

따라서, cell 한개를 포기하여, 이를 해결한다.

 

스택에서는 top의 위치로 이를 파악할 수 있었다. 

 

Circular design의 경우 front와 rear의 위치로 IsFull한지 IsEmpty한지 알 수가없다.

 

하지만 front가 다가와 rear에 부딪힐 경우, empty

 

rear가 다가와 front에 부딪힐 경우 full 이란것을 예상해 볼 수 있다.

 

하지만 두 경우 모두 rear == front 가 true이므로 둘을 "구분할 수 없다" 라는 문제가 발생한다.

 

따라서, 하나의 cell을 포기한다면 이를 해결하여 rear+1 == front 즉, rear가 뒤에서 front에 부딪히려 한다는 상황을 full하다고 예상해 볼 수 있다.

 

마찬가지로 다른 알고리즘으론

 

front+1 == rear라고 하는것도 생각해 볼 수 있겠다,

---

이거 안됀다,

 

rear+1 == front의 경우에는 maxQue-1 즉, cell 1개를 포기 (값을 enqueue하지못함, 실제로 memory는 할당되어 있으나) 하고, dequeue는 자유롭다, 단 하나도 포기하지 않는다.

 

그러나,

 

front+1 == rear의 경우에는 enqueue를 하나도 포기하지 않지만, dequeue를 하나 포기해야한다.

(절대 안되지, 값을 하나 덜 넣고말지, 못빼는 값이 존재하면 어떡해)

---

 

이의 반대경우는 궂이 하나의 셀을 포기할 필요가 없으므로, 그대로 rear == front가 isEmpty하다고 생각하면 될 것이다.

 

 

#2. Circular design은 modular 연산자로 구현한다.

 

이 생각을 못할 수 있었다. 예를들어 rear가 계속 ++하다가, 끝에 다다르면 circular design이니 순환을 하도록 해야되는데, 이를 어떻게 구현할까 생각해보았었다.

 

원래는 if(rear == lastPos) rear is not ++, but =1 이라고 구현 할 생각이였으나, 이는 modular operator로 구현할 수 있었다.

 

따라서 다음과 같이 해결한다.

 

rear = (rear+1) % maxQue;

 

여기서 maxQue는 당연히 user가 원하는 size보다 1 큰 값일것이다. (하나의 cell을 포기해야하니.)

(maxQue = max+1)

 

-length design의 경우

 

위와 같지만, 문제는 큐에서 가장 많이 실행하는 operation이 enqueue와 dequeue인데, 각 opeartion 마다, length를 ++하고, -- 하기에는 부담이 크다.

 

4. 실제 구현

#1. Circular design

ADT

template <class ItemType>
class QueueType // Circular Design
{
private:
	int rear, front;
	int maxQue; // maxQue는 User가 원하는것보다 1 많아야한다. 따라서 100같은 일반적인 수가 아닌,
                  //101과 같은 수일것이다.
	ItemType* items; // 동적할당으로 memory를 확보함
public:
	//Constructor
	QueueType(); // 기본 생성자, maxQue만큼 memory를 확보한다.
	QueueType(int max); // 사용자가 원하는 만큼 memory를 확보한다. maxQue = max + 1;
	
	//Destructor
	~QueueType();

	//Observer
	bool isFull() const;
	bool isEmpty() const;

	//Transformer
	void enqueue(ItemType item);
	void dequeue(ItemType& item);
};

Implementation

#include "QueueType.h"
//Constructor
template <class ItemType>
QueueType<ItemType>::QueueType()
{
	maxQue = 101; // 사용 가능한 memory는 100개
	front = maxQue - 1;
	rear = maxQue - 1;
	items = new ItemType[maxQue];
}
template <class ItemType>
QueueType<ItemType>::QueueType(int max)
{
	maxQue = max + 1;
	front = maxQue - 1;
	rear = maxQue - 1;
	items = new ItemType[maxQue];
}

//Destructor
template <class ItemType>
QueueType<ItemType>::~QueueType()
{
	delete[] items;
}

//Observer
template<class ItemType>
bool QueueType<ItemType>::isFull() const
{
	if ((rear + 1)%maxQue == front) // modular를 사용할 생각을 못했었다.
		// 우측 끝에서 rear가 있다면 circular이므로 당연히 wrap around 해야한다.
	{
		return true;
	}
	else
	{
		return false;
	}
}
template<class ItemType>
bool QueueType<ItemType>::isEmpty() const
{
	return (rear == front); // 위의isFull operator도 이와같이 작성하는것이 좋을 것 같다.
}

//Transformer
template<class ItemType>
void QueueType<ItemType>::enqueue(ItemType item) // 교재에는 없지만 여기 반드시 throw로 조건을 걸어야한다.
// 왜냐하면, 여기서 throw로 조건을 걸지않으면 Full한 상황에도 enqueue하게 되며, 갑자기 empty가 되버리는 불상사가 발생한다.
{
	if (isFull())
	{
		throw "Queue is full to enqueue";
	}
	else
	{
		rear = (rear + 1) % maxQue;
		items[rear] = item;
	}
}

template<class ItemType>
void QueueType<ItemType>::dequeue(ItemType& item)
{
	if (isEmpty())
	{
		throw "Queue is empty to dequeue";
	}
	else
	{
		front = (front + 1) % maxQue;
		item = items[front];
	}
}

#2. length design // 상속을 통해

 

ADT

template <class ItemType>
class CountedQueueType : public QueueType<ItemType>
{
private:
	int length;
	//나머지 rear과 front는 super class의 method를 이용해 접근.
public:
	CountedQueueType(int max);
	void enqueue(ItemType item);
	void dequeue(ItemType& item);
	int lengthIs() const;
};

Implementation

template<class ItemType>
CountedQueueType<ItemType>::CountedQueueType(int max):QueueType(max)
{
	length = 0;
}
template<class ItemType>
void CountedQueueType<ItemType>::enqueue(ItemType item)
{
	QueueType<ItemType>::enqueue(item);
	length++;
}
template<class ItemType>
void CountedQueueType<ItemType>::dequeue(ItemType& item)
{
	QueueType<ItemType>::dequeue(item);
	length--;
}

awkward한 표현은 "오늘"에 넣어두었다.