배열 큐(Array Queue)란?
배열을 이용해 구현한 큐를 의미한다. 1차원 배열을 이용하기 때문에 자료들끼리 물리적으로도 연결되어 있고 배열 생성하기 전에 배열의 크기를 미리 정해주어야 한다. 배열로 만든 큐는 자료의 추가/제거를 반복하다 보면 빈 공간이 있음에도 이를 인식하지 못하는 경우가 생겨 메모리가 비효율적으로 쓰이는 문제점이 있다. 이는 다음에 구현해볼 배열을 이용한 원형 큐, 연결 리스트를 이용한 큐로 이를 해결할 수 있다.
각 함수 중간에 AQ가 있는데 ArrayQueue을 의미한다.
배열 큐의 구현
소스 파일 구성은 다음과 같다.
|
파일 이름 |
내용 |
|
arrayqueue.h |
구조체 및 함수 선언 |
|
arrayqueue.cpp |
함수 구현 |
|
arrayqueuemain.cpp |
main 함수 실행 |
1.arrayqueue.h
#define TRUE 1
#define FALSE 0
using namespace std;
typedef struct arrayQueueNode{
int data;
};
typedef struct arrayQueue {
int maxSize;
int currentSize;
int front;
int rear;
arrayQueueNode *pElement;
};
arrayQueue* createAQ(int _max); // 큐 생성
int enqueueAQ(arrayQueue* pQueue,arrayQueueNode element); // 큐 enqueue
arrayQueueNode* dequeueAQ(arrayQueue* pQueue); // 큐 dequeue
arrayQueueNode* peekAQ(arrayQueue* pQueue); // 큐 peek
void deleteAQ(arrayQueue* pQueue); // 큐 삭제
int isFullAQ(arrayQueue* pQueue); // 큐의 자료가 가득 찼는지 확인
int isEmptyAQ(arrayQueue* pQueue); // 빈 큐인지 확인
void displayAQ(arrayQueue* pQueue); // 큐의 자료들 출력- ArrayQueueNode는 큐에 저장되는 각각의 자료들을 의미하며 실제 값인 data를 포함한다. 이렇게 따로 노드 구조체를 만드는 이유는 범용성을 위해서 이다.
- ArrayQueue는 실제 큐를 의미하며 큐의 최대 자료 저장 개수(maxSize), 현재 큐에 저장된 자료 개수(currentSize)실제로 자료를 저장 중인 배열(pElement)을 포함한다. 정수형 변수 front와 rear는 각각 큐의 제일 앞, 뒤의 노드(프런트와 리어 노드)의 위치 인덱스에 접근하기 위한 변수이다. 여기서 주의해야 할 점은 변수 front는 프런트 노드 위치의 한 칸 앞 위치를 가리킨다. 만약 현재 프런트 노드의 위치 인덱스가 1 이면 front의 값은 0이 된다.
전체적인 형태는 다음과 같다.
추가적으로 #define을 이용해 TURE은 1,FALSE는 0 값으로 정의해주었다.
함수들은 함수 구현 부분에서 자세히 설명하겠다.
2.arrayqueue.cpp
- createAS()
arrayQueue* createAQ(int _max) {
arrayQueue* pReturn = NULL;
if (_max > 0) {
pReturn = new arrayQueue;
if (pReturn != NULL) {
memset(pReturn, 0, sizeof(arrayQueue));
pReturn->maxSize = _max;
pReturn->front = -1;
pReturn->rear = -1;
}
else {
cout << "메모리 할당 오류, pReturn" << endl;
return NULL;
}
}
else {
cout << "큐의 크기는 0보다 커야합니다." << endl;
return NULL;
}
pReturn->pElement = new arrayQueueNode[_max];
if (pReturn->pElement != NULL) {
memset(pReturn->pElement, 0, sizeof(arrayQueueNode)*_max);
}
else {
cout << "메모리 할당 오류, pElement" << endl;
delete pReturn;
return NULL;
}
return pReturn;
}먼저 최대 저장 가능 원소 개수가 0보다 큰지 확인 후 0보다 크다면 ArrayQueue에 대한 메모리를 할당 후 maxSize를 _max값으로 초기화하고 front, rear 모두 -1로 값을 준다. 변수 front에도 -1 값을 주는 이유는 앞서 말했듯이 front는 프런트 노드의 한 칸 이전 위치를 가리키기 때문이다. pElement에 대해서도 메모리 할당 후 memset()을 이용해서 _max만큼 메모리를 할당한다.
- enqueue()
먼저 인규 연산을 하기 위해서는 큐가 가득 차 있는 상태인지 아닌지를 알아야 한다. 이때 isFullAQ() 함수를 이용해 큐가 가득 차있는 상태인지 아닌지를 알아내 인큐 연산이 가능한지 판단할 것이다. 큐가 가득 찬 상태가 아니라면 새로운 노드를 추가하는데 이때 추가하는 곳의 위치 인덱스는 rear+1이 된다. 추가 후에는 currentSize,rear을 각각 1씩 더해준다. 이때 반환형은 TRUE/FALSE이다.
pQueue->pElement [pQueue->rear+1] = element; // 큐 끝에 새로운 노드 추가
pQueue->currentSize++ ,pQueue->rear++; // currentSize, rear 값 조정
그림으로 나타내면 다음과 같다.
코드 구현은 다음과 같다.
int enqueueAQ(arrayQueue* pQueue, arrayQueueNode element) {
int ret = FALSE;
if (pQueue != NULL) {
if (isFullAQ(pQueue) == FALSE) {
pQueue->pElement[pQueue->rear+1] = element;
pQueue->currentSize++;
pQueue->rear++;
ret = TRUE;
}
else {
cout << "큐가 이미 가득 찼습니다." << endl;
}
}
return ret;
}- dequeue()
먼저 디큐 연산을 하기 위해서는 큐가 공백 상태인지 아닌지를 알아야 한다. 이때 isEmptyAQ() 함수를 이용해 큐가 공백 상태인지 아닌지를 알아내 디큐 연산이 가능한지 판단할 것이다. 큐가 공백 상태가 아니라면 큐에 맨 앞에 있는 노드를 반환하는데 이때 위치 인덱스는 front +1 이 된다. 포인터 전달 후에는 currentSize는 1을 빼주고 front는 1을 더해준다.노드를 반환할 때는 새로운 노드를 생성 후 반환하는 노드의 포인터를 전달한다. 이때 반환한 노드의 메모리는 main함수에서 제거하려고 한다.
pReturn->data = pQueue->pElement [pQueue->front + 1]. data; // 새로 생성한 노드에 맨 앞에 있는 노드의 포인터 전달
pQueue->front++ ,pQueue->currentSize--; // fornt , currentSize 값 조정
그림으로 나타내면 다음과 같다.
코드 구현은 다음과 같다.
arrayQueueNode* dequeueAQ(arrayQueue* pQueue){
arrayQueueNode* pReturn = NULL;
if (pQueue != NULL) {
if (isEmptyAQ(pQueue) == FALSE) {
pReturn = new arrayQueueNode;
if (pReturn != NULL) {
pReturn->data = pQueue->pElement[pQueue->front + 1].data;
pQueue->front++;
pQueue->currentSize--;
}
else {
cout << "메모리 할당 오류,pReturn" << endl;
}
}
else {
cout << "공백 큐 입니다." << endl;
}
}
return pReturn;
}- peek()
피크 연산은 디큐 연산과 비슷하지만 반환하는 노드를 제거하지 않는다는 점에서 차이가 생긴다. 노드를 제거하지 않기 때문에 front의 위치를 조정할 필요도 currneSize의 값에 변화를 줄 필요도 없다.
그림으로 나타내면 다음과 같다.
arrayQueueNode* peekAQ(arrayQueue* pQueue) {
arrayQueueNode* pReturn = NULL;
if (pQueue != NULL) {
if (isEmptyAQ(pQueue) == FALSE) {
pReturn = new arrayQueueNode;
if (pReturn != NULL) {
pReturn->data = pQueue->pElement[pQueue->front + 1].data;
}
else {
cout << "메모리 할당 오류,pReturn" << endl;
}
}
else {
cout << "공백 큐 입니다." << endl;
}
}
return pReturn;
}나머지 함수 구현 코드는 다음과 같다.
void deleteAQ(arrayQueue* pQueue) {
if (pQueue != NULL) {
if (pQueue->pElement != NULL) {
delete[] pQueue->pElement;
}
delete pQueue;
}
}
int isFullAQ(arrayQueue* pQueue) {
int ret = FALSE;
if (pQueue != NULL) {
if (pQueue->currentSize == pQueue->maxSize
|| pQueue->rear==pQueue->maxSize-1) {
ret = TRUE;
}
}
return ret;
}
int isEmptyAQ(arrayQueue* pQueue) {
int ret = FALSE;
if (pQueue != NULL) {
if (pQueue->currentSize == 0) {
ret = TRUE;
}
}
return ret;
}
void displayAQ(arrayQueue* pQueue) {
if (pQueue != NULL) {
cout << "큐 크기: " << pQueue->maxSize << endl;
cout << "현재 자료 개수: " << pQueue->currentSize << endl;
for (int i = pQueue->front + 1; i < pQueue->rear + 1; i++) {
cout << "[" << i << "] - [" << pQueue->pElement[i].data << "]" << endl;
}
}
}여기서 주의해야할 점은 isFullAQ에서 큐가 가득 찼는지 판단할 때 현재 저장된 자료 개수뿐만 아니라 리어 노드의 위치가 어디 인지도 생각해야 한다는 점이다. 리어 노드의 위치가 이미 큐의 맨 끝에 있다면 더 이상 노드를 추가하지 못하기 때문이다. 여기서는 리어 노드의 위치 인덱스를 가리키는 변수 rear의 값이 maxSize-1 값과 같으면 큐는 가득 찬 것이다.
3.arraysqueuemain.cpp
메인 함수 실행 코드는 다음과 같다.
#include "arrayqueue.h"
int main()
{
arrayQueue *pQueue = NULL;
arrayQueueNode* pNode = NULL;
arrayQueueNode Node;
pQueue = createAQ(4);
if (pQueue != NULL) {
Node.data = 1;
enqueueAQ(pQueue,Node );
Node.data = 2;
enqueueAQ(pQueue, Node);
Node.data = 3;
enqueueAQ(pQueue, Node);
Node.data = 4;
enqueueAQ(pQueue, Node);
displayAQ(pQueue);
pNode = dequeueAQ(pQueue);
if (pNode != NULL) {
cout << "dequeue: " << pNode->data << endl;
delete pNode;
}
displayAQ(pQueue);
pNode = peekAQ(pQueue);
if (pNode != NULL) {
cout << "dequeue: " << pNode->data << endl;
delete pNode;
}
displayAQ(pQueue);
Node.data = 5;
enqueueAQ(pQueue, Node);
}
return 0;
}
이때 주의할 점은 디큐 연산 실행 후 반환되는 노드의 메모리를 제거해 줘야 하는 점이다. 위 코드에서는
delete pNode를 통해 메모리 제거를 해주었다.
실행결과는 다음과 같다.
마지막에 새로운 노드 '5'를 추가했으나 배열 큐느 큐에 빈 공간이 있지만(위치 인덱스 0) 인식하지 못하기 때문에 인큐 연산을 실패한 모습이다.
배열로 구현한 원형 큐
앞서 구현한 배열 큐는 디큐연산을 실행하고 만들어진 빈 공간을 인식하지 못해 실제로 큐에 들어있는 자료 개수가 최대 저장 개수보다 적은데도 불구하고 인큐 연산을 실행하지 못하고 메모리 활용에 있어서 매우 비효율적이게 된다.
이러한 비효율성을 해결하기위해서는 리스트 구현과 비슷하게 디큐 연산을 하고 생긴 빈 공간을 채우기 위해 남아있는 자료들을 왼쪽으로 한 칸씩 이동하는 방법이 있지만 이러한 방법은 남아있는 자료가 n개 있으면 n번 이동해야하기 때문에 시간 복잡도는 O(n)이다. 따라서 크기가 큰 배열이라면 연산을 하는데 드는 시간이 상당히 오래 걸리게 된다.
이를 해결하기 위한 좀 더 효율적인 방법은 기존의 일자 형태였던 큐를 오른쪽 끝과 왼쪽 끝을 연결시켜 원형으로 만드는 것이다. 기존 배열 큐에서는 리어 노드가 큐에 끝에 있으면 오른쪽에 빈 공간이 없기 때문에 큐의 왼쪽 부분에 빈 공간이 많아도 인큐 연산을 실행하지 못했으나 원형 큐에서 오른쪽 끝과 왼쪽 끝을 연걸 함으로써 리어 노드의 오른쪽에도 공간을 만들어 인큐 연산을 실행할 수 있게 된다.
원형 큐의 구현
소스 파일 구성은 다음과 같다.
|
파일 이름 |
내용 |
|
arraycircularqueue.h |
구조체 및 함수 선언 |
|
arraycircularqueue.cpp |
함수 구현 |
|
arraycircularqueuemain.cpp |
main 함수 실행 |
※이때 앞서 구현한 배열 큐의 코드를 그대로 활용한다.
1.arraycircularqueue.h
#define TRUE 1
#define FALSE 0
using namespace std;
typedef struct arrayQueueNode{
int data;
};
typedef struct arrayQueue {
int maxSize;
int currentSize;
int front;
int rear;
arrayQueueNode *pElement;
};
arrayQueue* createAQ(int _max); // 큐 생성
int enqueueAQ(arrayQueue* pQueue,arrayQueueNode element); // 큐 enqueue
arrayQueueNode* dequeueAQ(arrayQueue* pQueue); // 큐 dequeue
arrayQueueNode* peekAQ(arrayQueue* pQueue); // 큐 peek
void deleteAQ(arrayQueue* pQueue); // 큐 삭제
int isFullAQ(arrayQueue* pQueue); // 큐의 자료가 가득 찼는지 확인
int isEmptyAQ(arrayQueue* pQueue); // 빈 큐인지 확인
void displayAQ(arrayQueue* pQueue); // 큐의 자료들 출력앞서 배열 큐에서 구현한 코드와 동일하다.
2.arrayQueue.cpp
- createAQ()
arrayQueue* createAQ(int _max) {
arrayQueue* pReturn = NULL;
if (_max > 0) {
pReturn = new arrayQueue;
if (pReturn != NULL) {
memset(pReturn, 0, sizeof(arrayQueue));
pReturn->maxSize = _max;
pReturn->front = -1;
pReturn->rear = -1;
}
else {
cout << "메모리 할당 오류, pReturn" << endl;
return NULL;
}
}
else {
cout << "큐의 크기는 0보다 커야합니다." << endl;
return NULL;
}
pReturn->pElement = new arrayQueueNode[_max];
if (pReturn->pElement != NULL) {
memset(pReturn->pElement, 0, sizeof(arrayQueueNode)*_max);
}
else {
cout << "메모리 할당 오류, pElement" << endl;
delete pReturn;
return NULL;
}
return pReturn;
}배열 큐의 코드와 동일하다.
- enqueue()
앞서 구현한 배열 큐의 인큐 연산과 다른점이 생긴다. 배열 큐에서는 rear의 값이 무조건 순차적으로 증가하지만 원형 큐에서는 배열의 맨 끝에서 맨 앞으로도 갈 수 있어야 하기 때문에 rear의 값을 조정하는 코드를 변경해주었다.
pQueue->rear = (pQueue->rear + 1) % (pQueue->maxSize);
int enqueueAQ(arrayQueue* pQueue, arrayQueueNode element) {
int ret = FALSE;
if (pQueue != NULL) {
if (isFullAQ(pQueue) == FALSE) {
pQueue->rear = (pQueue->rear + 1) % (pQueue->maxSize);
pQueue->pElement[pQueue->rear] = element;
pQueue->currentSize++;
ret = TRUE;
}
else {
cout << "큐가 이미 가득 찼습니다." << endl;
}
}
return ret;
}- dequeue()
앞서 구현한 배열 큐와 다른점은 인큐 연산 때와 마찬가지로 front값이 큐의 맨 끝에서 맨 앞으로도 갈 수 있어야 한다는 점이다. 따라서 front의 값을 조정하는 코드를 변경해주었다.
arrayQueueNode* dequeueAQ(arrayQueue* pQueue) {
arrayQueueNode* pReturn = NULL;
if (pQueue != NULL) {
if (isEmptyAQ(pQueue) == FALSE) {
pReturn = new arrayQueueNode;
if (pReturn != NULL) {
pQueue->front = (pQueue->front + 1) % (pQueue->maxSize);
pReturn->data = pQueue->pElement[pQueue->front].data;
pQueue->currentSize--;
}
else {
cout << "메모리 할당 오류,pReturn" << endl;
}
}
else {
cout << "공백 큐 입니다." << endl;
}
}
return pReturn;
}- peek()
피크 연산은 front 값을 변경 시켜줄 필요가 없기 때문에 배열 큐에서의 피크 연산과 구현 코드가 동일하다.
arrayQueueNode* peekAQ(arrayQueue* pQueue) {
arrayQueueNode* pReturn = NULL;
if (pQueue != NULL) {
if (isEmptyAQ(pQueue) == FALSE) {
pReturn = new arrayQueueNode;
if (pReturn != NULL) {
pReturn->data = pQueue->pElement[pQueue->front + 1].data;
}
else {
cout << "메모리 할당 오류,pReturn" << endl;
}
}
else {
cout << "공백 큐 입니다." << endl;
}
}
return pReturn;
}나머지 함수 구현 코드는 다음과 같다.
void deleteAQ(arrayQueue* pQueue) {
if (pQueue != NULL) {
if (pQueue->pElement != NULL) {
delete[] pQueue->pElement;
}
delete pQueue;
}
}
int isFullAQ(arrayQueue* pQueue) {
int ret = FALSE;
if (pQueue != NULL) {
if (pQueue->currentSize == pQueue->maxSize) {
ret = TRUE;
}
}
return ret;
}
int isEmptyAQ(arrayQueue* pQueue) {
int ret = FALSE;
if (pQueue != NULL) {
if (pQueue->currentSize == 0) {
ret = TRUE;
}
}
return ret;
}
void displayAQ(arrayQueue* pQueue) {
if (pQueue != NULL) {
cout << "큐 크기: " << pQueue->maxSize << endl;
cout << "현재 자료 개수: " << pQueue->currentSize << endl;
int index = 0;
for (int i = 1; i < pQueue->currentSize+1; i++) {
index = (pQueue->front + i) % (pQueue->maxSize);
cout << "[" << index << "] - [" << pQueue->pElement[index].data << "]" << endl;
}
}
}여기서 변경된 점은 isFullAQ()에서 현재 저장된 자료 개수와 최대 저장 자료 개수만 비교해주면 된다는 점이다.
3.arraysqueuemain.cpp
main함수의 코드는 배열 큐에서의 main함수 코드와 동일하다.
실행결과는 다음과 같다.
앞서 배열 큐의 실행 결과와 다르게 위치 인덱스 0에 '5' 노드가 성공적으로 들어가 있는 모습이다.
'컴퓨터 공학 > 자료구조' 카테고리의 다른 글
| C로 만드는 자료구조- 큐를 이용한 평균 대기 시간 구하기 (0) | 2020.09.18 |
|---|---|
| C로 만드는 자료구조- 연결 리스트로 구현한 큐 (0) | 2020.09.11 |
| C로 만드는 자료구조- Queue란? (0) | 2020.09.06 |
| C로 만드는 자료구조-배열로 구현한 스택 (0) | 2020.08.29 |
| C로 만드는 자료구조- 연결 리스트로 구현한 스택 (0) | 2020.08.29 |
최근댓글