객체지향 개념을 이용한 원형큐(circular queue)구현

소개글

객체지향 개념을 이용한 원형큐 구현입니다

목차

1.문제제기
2.문제분석
3.소스

본문내용

1. 문제제기 :
자료구조의 일종인 큐(Queue)의 개념을 이해하고, C++객체지향 언어로 구현해본다. 이때 배열을 사용하여 구현을 해야 하는데, 배열의 특성상 그 크기가 미리 지정되어 있으므로 데이터의 저장순서를 주의해야한다. 그러므로 front와 rear 변수를 적절히 조작하여 원형큐를 구현한다.

2. 문제분석 & 문제해결 :
자료구조에서 스택과는 반대되는 개념인 Queue를 구현하는 과제이다. Queue는 FIFO(First In First Out)방식으로, 자료가 입력된 순서대로 출력되는 것이다. 이 프로그램은 Queue라는 이름의 클래스를 포함하며 이 클래스는 IsEmpty(), IsFull(), Push(), Pop(), DisplayQueue()등의 함수로 이루어져 있다. 또한 rear, front의 변수를 가지고 있으며 큐의 내용을 저장할 data라는 정수형 배열을 가지고 있다.
큐는 데이터가 들어간 순서대로 나와야한다. 그런데 일차원배열에 데이터를 저장하고 제일 앞에 있는 원소를 제거할 경우 뒤에 있는 내용 전체를 복사하여 배열의 시작부분에 다시 할당시켜야하는 어려움이 있다. 이렇게 할 경우 데이터의 관리가 어려울 뿐만 아니라 메모리 사용이 커진다는 단점이 있다. 따라서 원형큐(Circular Queue)를 구현해야한다.
원형큐를 조작하기위해서 필요한 변수가 front와 rear이다. front는 Queue의 현재 가장 앞에 있는 원소를 가리키며, rear는 Queue의 현재 가장 뒤에 있는 빈 공간을 의미한다. 이 두 변수의 조작을 통해서, 실제 data배열 안에 있는 원소들은 일차선형으로 저장되어있지만 마치 데이터가 원형으로 저장되어있는 것과 같은 효과를 낼 수 있다.
Push함수는 사용자로부터 정수를 입력받아서 data[rear]의 위치에 저장한다. rear는 현재 데이터의 가장 마지막부분을 의미하므로 즉 데이터를 계속해서 뒷부분에 붙여 저장하는 기능을 하는 것이다. 할당이 끝나면 rear++를 통해 rear값이 다시 데이터의 가장 마지막 빈공간을 의미하도록 한다.

참고 자료

없음