큐? 선형, 원형 큐~

먼저 들어온 사람이 먼저 나간다.

제품이 레일을 따라 검사받고 나가는 것처럼..

                             ㅁ1ㅁ2ㅁ3ㅁ4ㅁ5ㅁ6ㅁ7 <-제품이 가는방향..

----------------------------------------

<- 나가는곳                           들어오는곳->

1234..순서대로 들어왔다가 들어온 순서대로 나가는것도 1234순으로 나간다..

버스정류장에 사람이 온대로 버스에 탄다는 개념..?

 

큐는 스택과 반대의 개념이다..

(스택은 먼저들어온놈이 나중에 나간다..위에서 물건이 쌓인다는 개념..)

 

큐는 한쪽 끝ㅇ느 front로 정해서 삭제만..다른쪽은 rear로 정해서 삽입만..

1차원 배열로 선형큐를 만들면 문제가 발생한다.

#include    
#include 
#include 
#define MAX 10

using namespace std;


class CQueue
{
private:
	int arr[MAX];
	int front;
	int rear;

public:
	CQueue() : front(0),rear(0)
	{}

	void enQueue(int data);
	void deQueue();
	void Print();
};

void CQueue::enQueue(int data)
{
	if(rear>MAX-1)
	{
		cout << "데이터가 꽉 찼습니다 " << endl;
	}
	else
	{
		cout << "데이터 삽입" << endl;
		arr[rear++]=data;

	}
}

void CQueue::deQueue()
{
	if(front==rear)
	{
		cout << "모든데이터를 삭제하였습니다." << endl;
	}
	else
	{
		cout << "데이터 삭제" << endl;
		arr[front++]=NULL;
	}
}

void CQueue::Print()
{
	for(int i=0;i
0)
		{
			cout << arr[i] << " " ;
		}

	}
}

int main()
{     
	CQueue st1;
	for(int i=0;i<10;i++)
	{
		st1.enQueue(i+10);
		st1.Print();
		cout << endl;
	}
	st1.enQueue(11);
	st1.enQueue(11);

	for(int i=1;i<11;i++)
	{
		st1.deQueue();
		st1.Print();
	}
	st1.enQueue(11);
	getch();
	return 0;
}

자리가 있는데도 데이터가 꽉 찬것으로 인지하고 있다..

그럼 이것을 어떻게..? 

 

원형 큐라는 개념을 이용

다람쥐 챗바퀴처럼..계속 돈다는거야...

위에는 10개의 공간이 있는데..1234567891012345678910

이런식으로..

그럼 %연산자를 이용해서..

#include    
#include 
#include 
#define MAX 10

using namespace std;


class CQueue
{
private:
	int arr[MAX];
	int front;
	int rear;

public:
	CQueue() : front(0),rear(0)
	{}

	void enQueue(int data);
	void deQueue();
	void Print();
};

void CQueue::enQueue(int data)
{
	if((rear+1)%MAX==front)
	{
		cout << "데이터가 꽉 찼습니다 " << endl;
	}
	else
	{
		cout << "데이터 삽입" << endl;
		arr[rear=(rear+1)%MAX]=data;

	}
}

void CQueue::deQueue()
{
	if(front==rear)
	{
		cout << "모든데이터를 삭제하였습니다." << endl;
	}
	else
	{
		cout << "데이터 삭제" << endl;
		arr[front=(front+1)%MAX]=NULL;
	}
}

void CQueue::Print()
{
	for(int i=0;i0)
		{
			cout << arr[i] << " " ;
		}

	}
}

int main()
{     
	CQueue st1;
	for(int i=0;i<10;i++)
	{
		st1.enQueue(i+10);
		st1.Print();
		cout << endl;
	}
	st1.enQueue(11);
	st1.enQueue(11);

	for(int i=1;i<11;i++)
	{
		st1.deQueue();
		st1.Print();
	}
	for(int i=0;i<3;i++)
	{
		st1.enQueue(i+10);
		st1.Print();
		cout << endl;
	}
	getch();
	return 0;

}

 

 

이런식으로 수정을 해봤다..

꼬리에 꼬리를 문다는 식으로..데이터의 꽉찬지 확인은

(rear+1)%MAX==front랑 같은지..즉 0인지 확인하는것.. 

 

지금 위에것은 0~MAX-1의 구간을 계속 순환해..그리고

arr[0]의 빈공간은 빈상태와 풀상태를 쉽게 확인해서 더미로 나둔다(한개의 공간은..출발이 rear=1 front=0이란거지..)

왜냐면 위에것을 기준으로  rear값이 데이터가 삽입될때마다 증가하다가..계속 순환하니까 나중엔 결국(10개 데이터니까)

9개 데이터를 넣었을때

(rear+1)%MAX==front로 미리 +1을 검사하여..front랑 같으니까 데이터가 풀이라는것을 알수 있는거지..

만약 더미가 없다면?? 둘다 0이라면..이게 풀인지..처음상태인 빈공간인지..중복된다는거지..

 

 

뭐..................그렇다는거....