1. Queue ¶

Queue는 나중에 넣은 것은 나중에 나오고 먼저 넣은 것은 먼저 나오는 자료 구조입니다.
위 아래 뻥 뚫린.. 위로 물부으면 밑으로 나오겠죠? (먼저 들어간건 먼저 나온다!)
자판기를 생각하면 되겟죠? 먼저 선 사람이 먼저 나가니..(새-_-치기 제외)
Front는 큐의 맨 앞을 가르키는 변수, Rear는 큐의 맨 끝 원소를 가르키는 변수

1.1. 배열로 구현한 Queue ¶

~cpp 
class Queue
{
	enum {Size=100};
private:
	int m_nFront;
	int m_nRear;
	int m_nData[Size];
	bool IsEmpty();
	bool IsFull();
public:
	Queue() {m_nFront=m_nRear=-1;}
	bool Add(int ndata);
	bool Erase();
	void Show();
	~Queue() {}
};

bool Queue::IsEmpty()
{

true;
	return false;
}

bool Queue::IsFull()
{
	if(m_nRear==Size-1 && m_nFront!=m_nRear)
		return true;
	return false;
}

bool Queue::Add(int ndata)
{
	if(!IsFull())
	{
		m_nData[++m_nRear]=ndata;
		return true;
	}
	else
	{
		cout<<"꽉찼다";
		return false;
	}
}
	
bool Queue::Erase()
{
	if(!IsEmpty())
	{
		m_nFront++;
		return true;
	}
	else
	{
		cout<<"비었다";
		return false;
	}
}

void Queue::Show()
{
	int count=m_nFront;
	while(1)
	{
		cout<<m_nData[++count];
		if(count==m_nRear)
			break;
	}
}

그런데.. 이 큐는 문제점이 있습니다.
원소를 한 90개 넣고 그 원소를 90개 다지우면? Front와 Rear가 각각 89를 가리키게 되겠지요? 그럼 남는 공간은 10-_-개밖에 안됩니다.
이렇게 되면 첨에 100개의 배열을 할당해준것중에 90개를 못 쓰게 되겠네요.
이를 보완하기 위해 원형 큐라는게 있더랍니다. 또는 링크드 리스트로 큐를 만들어서 제한없이 쓰는 방법도 있겠죠.
요것도 만들어봐야겠죠?^^

1.2. Linked List로 만든 큐 ¶

~cpp 
class Queue
{
private:
	struct Node
	{
		int nData;
		Node* pPrev;
	};
	Node* m_pFront;
	Node* m_pRear;
	bool IsEmpty();
public:
	Queue();
	~Queue();
	void Add(int x);
	void Remove();
};

Queue::Queue()
{
	m_pFront=new Node;
	m_pFront->pPrev=NULL;
	m_pRear=m_pFront;
}

void Queue::Add(int x)
{
	Node* temp=new Node;
	temp->nData=x;
	temp->pPrev=m_pRear;
	m_pRear=temp;
}

void Queue::Remove()
{
	if(!IsEmpty())
	{
		Node* temp=m_pRear->pPrev;
		delete m_pRear;
		m_pRear=temp;
	}
	else
		cout<<"...";
}

bool Queue::IsEmpty()
{
	if(m_pRear==m_pFront)
		return true;
	else
		return false;
}

Queue::~Queue()
{
	while(!IsEmpty())
	{
		Remove();
	}
	delete m_pFront;
}

Contents

1. Queue ¶

1.1. 배열로 구현한 Queue ¶

1.2. Linked List로 만든 큐 ¶