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;
}
