imported>Unknown at 05:23, 7 February 2021

2021-02-07T05:23:05Z

New page

__TOC__

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

== 배열로 구현한 Queue ==
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개를 못 쓰게 되겠네요.
* 이를 보완하기 위해 원형 큐라는게 있더랍니다. 또는 링크드 리스트로 큐를 만들어서 제한없이 쓰는 방법도 있겠죠.
* 요것도 만들어봐야겠죠?^^

== Linked List로 만든 큐 ==
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;
}

DataStructure/Queue - Revision history

imported>Unknown at 05:23, 7 February 2021