나의 IT일지
큐 본문
자료구조에는 여러 형식으로 데이터를 저장한다. 그리고 데이터를 저장하는 방식에 따라 선형형식, 비선형형식으로 나뉜다.
- 선형 구조 : 데이터를 1:1 관계로 하나씩 나열시킨 구조로, list, stack, queue가 해당 구조에 해당한다.
- 비선형 구조 : 데이터를 1:n 관계로 나열 시킨 구조로, Heap, Tree가 해당 구조에 해당한다.
그중에 데이터를 입력한 순서대로 저장한 뒤, 저장한 순서대로 데이터를 사용하기 위한 자료형태가 있는데, 이 자료형태를 큐(Queue)라고 한다. 큐는 데이터를 대기열처럼 저장하는 들어오는 순서대로 저장하는 자료구조로, 가장 먼저 삽입된 데이터를 가장 먼저 삭제되는 선입선출 형식을 사용한다.
큐에서는 데이터를 삽입하는 것을 "enqueue", 데이터를 제거하는 것을 "dequeue", 삭제되는 데이터의 위치를 "front", 삽입되는 데이터의 위치를 "rear"라고 한다.
배열 큐
배열 큐는 배열을 이용해 큐를 나타내는 자료구조로, 저장공간이 정해져 있는 큐이다.
typedef struct ArrayQueueNodeType {
element data;
}ArrayQueueNode;typedef struct ArrayQueueType {
struct ArrayQueueNodeType queue[4];
int front, rear;
}ArrayQueue;위의 코드는 큐의 노드와 큐의 정보인 사용할 배열과 front, rear를 구현해 놓은 것이다. 이때, node(노드)란 데이터를 저장하는 공간으로, 구조체를 통해 노드에 어떤 형태의 데이터를 저장할지 결정한다.
배열 큐 알고리즘
큐은 데이터가 제일 먼저 삽입한 데이터는 제일 먼저 삭제되어야 하기에, 데이터를 삽입, 삭제 , 출력하는 기능을 알고리즘을 통해 소스코드로 구현해야 한다. 이때 front은 삭제되는 데이터가 위치하는 배열의 인덱스 값을 지정하며, rear는 삽입되는 데이터가 위치하는 배열의 인덱스값을 지정한다. 그리고 배열을 생성할 때, front와 rear는 "-1"로 구현해야 하며 이를 해당 배열이 공백상태라고 한다.
ArrayQueue* createQueue(void) {
ArrayQueue* Q = (ArrayQueue*)malloc(sizeof(ArrayQueue));
Q->front = -1;
Q->rear = -1;
return Q;
}
- 데이터 삽입 함수(enqueue())
- 기능
- 배열에 자리가 있는 경우 : 배열에 데이터를 삽입, rear를 +1
- 배열에 자리가 없는 경우(rear == 배열크기-1) : 배열에 자리가 없다고 출력
- 기능
- 함수의 자료형 : void
- 매개변수 : 저장할 데이터, 데이터를 저장할 배열을 가진 큐의 정보 변수
| 알고리즘 |
| 1.배열이 공백인 경우(rear == 배열크기-1) "공백상태"를 출력 2. 배열에 자리가 있을 경우 2-1. rear의 위치 변경 2-2. rear의 위치에 데이터 삽입 |
void enQueue(ArrayQueue* Q, element data) {
if (Q->rear == Array_Size) {
printf("포화상태\n");
return 1;
}
else {
Q->queue[++Q->rear].data = data;
}
}
- 데이터 삭제 함수(dequeue())
- 기능
- 배열이 공백이 아닌 경우 : 데이터를 삭제, front를 +1
- 배열에 공백인 경우(front == rear) : 배열에 저장되어 있는 데이터가 없다고 출력
- 함수의 자료형 : int
- 매개변수 : 데이터를 삭제할 배열을 가진 큐의 정보 변수
- 기능
| 알고리즘 |
| 1.배열이 공백인 경우(front == rear) "공백상태"를 출력 2. 배열에 자리가 있을 경우 2-1. front의 위치 변경 2-2. front의 위치에 데이터 삭제 |
int deQueue(ArrayQueue* Q) {
if (Q->front == Q->rear) {
printf("공백 상태\n");
return 1;
}
else {
int data;
Q->front++;
data = Q->queue[Q->front].data;
return data;
}
}
- 데이터 출력 함수(printStack())
- 기능 : front부터 rear의 위치까지의 데이터 내용을 출력
| 알고리즘 | 인덱스 값이 front인 배열 요소 부터 rear까지 출력 |
void printQueue(ArrayQueue* Q) {
printf("\nQueue : ");
for (int i = Q->front + 1; i <= Q->rear; i++) {
printf("%c\t", Q->queue[i]);
}
}
데이터 삽입, 데이터 삭제, 데이터 출력하는 함수를 구현했으며, 해당 함수들을 통해 배열 큐를 생성하면 다음과 같다.
include<stdio.h>
#include<malloc.h>
#define Array_Size 4
typedef char element;
typedef struct ArrayQueueNodeType {
element data;
}ArrayQueueNode;
typedef struct ArrayQueueType {
struct ArrayQueueNodeType queue[Array_Size];
int front, rear;
}ArrayQueue;
//큐 생성
ArrayQueue* createQueue(void) {
ArrayQueue* Q = (ArrayQueue*)malloc(sizeof(ArrayQueue));
Q->front = -1;
Q->rear = -1;
return Q;
}
//큐 공백검사
int isQueueEmpty(ArrayQueue* Q) {
if (Q->front == Q->rear) {
printf("\n공백 상태");
return 1;
}
else {
return 0;
}
}
//큐 포화 검사
int isQueueFull(ArrayQueue* Q) {
if (Q->rear == Array_Size-1) {
printf("\n포화상태");
return 1;
}
else {
return 0;
}
}
//큐 데이터 삽입
void enQueue(ArrayQueue* Q, element data) {
if (isQueueFull(Q)) {
return 1;
}
else {
Q->queue[++Q->rear].data = data;
}
}
//큐 데이터 삭제
element deQueue(ArrayQueue* Q) {
if (isQueueEmpty(Q)) {
return 1;
}
else {
int data;
Q->front++;
data = Q->queue[Q->front].data;
return data;
}
}
//큐 데이터 출력
void printQueue(ArrayQueue* Q) {
printf("\nQueue : ");
for (int i = Q->front+1; i <= Q->rear; i++) {
printf("%c\t", Q->queue[i]);
}
}
int main() {
ArrayQueue* Q = createQueue();
element data;
enQueue(Q, 'A');
printQueue(Q);
enQueue(Q, 'B');
printQueue(Q);
enQueue(Q, 'C');
printQueue(Q);
data = deQueue(Q);
printQueue(Q);
printf("deQueue : %c", data);
enQueue(Q, 'D');
printQueue(Q);
enQueue(Q, 'E');
printQueue(Q);
}
이때 배열 큐는 데이터를 저장했던 공간은 다시 사용할 수 없다. 그래서 데이터 1개 삭제했어도, 데이터를 1개 덜 저장할 수 있는 것을 확인할 수 있다.
연결 큐
배열 큐는 저장공간이 한정되어 있을 뿐만 아니라, 데이터를 저장한 공간을 다시 사용할 수 없다. 그래서 노드의 주소를 통해 연결해서 저장공간 상관없이 사용하는 연결 큐를 사용하게 된다.
typedef struct LinkedQueueNodeType {
element data;
struct LinkedQueueNodeType* link;
}LinkedQueueNode;typedef struct LinkedQueueType {
LinkedQueueNode* front, * rear;
}LinkedQueue;위의 코드는 큐의 노드와 큐의 정보인 사용할 배열과 front, rear를 구현해 놓은 것이다. 이때, node(노드)란 데이터를 저장하는 공간으로, 구조체를 통해 노드에 어떤 형태의 데이터를 저장할지 결정한다.
연결 큐 알고리즘
큐은 데이터가 제일 먼저 삽입한 데이터는 제일 먼저 삭제되어야 하기에, 데이터를 삽입, 삭제 , 출력하는 기능을 알고리즘을 통해 소스코드로 구현해야 한다. 이때 front은 삭제되는 노드가 위치하는 주소의 값을 지정하며, rear는 삽입되는 노드가 위치하는 주소의 값을 지정한다. 이때 front와 rear는 배열을 생성할 때, "NULL"로 구현해야 한다. 그리고 이는 해당 배열이 공백상태이기 때문이다.
LinkedQueue* createLinkedQueue() {
LinkedQueue* Q = (LinkedQueue*)malloc(sizeof(LinkedQueue));
Q->front = NULL;
Q->rear = NULL;
return Q;
}
- 데이터 삽입 함수(enqueue())
- 기능
- 노드가 있는 경우 : rear에 저장된 값을 노드의 주소로 저장한 후, 노드의 주소를 rear에 저장
- 노드가 없는 경우 : 노드의 주소에 NULL값을 저장한 후, 노드의 주소를 rear,front에 저장
- 기능
- 함수의 자료형 : void
- 매개변수 : 저장할 데이터, 저장할 연결형 큐
| 알고리즘 |
| 1.노드가 없는 경우(front == NULL): 1-1. 새로운 노드의 포인터 변수에 NULL값을 저장 1-2. 노드의 주소를 rear,front에 저장 2. 노드가 있을 경우 2-1. 새로운 노드의 포인터 변수에 NULL값을 저장 2-2. 노드의 주소를 rear에 저장 |
void enQueue(LinkedQueue* Q,element data) {
LinkedQueueNode* QNode = (LinkedQueueNode*)malloc(sizeof(LinkedQueueNode));
QNode->data = data;
QNode->link = NULL;
if (Q->front == NULL){
Q->front = QNode;
Q->rear = QNode;
}
else {
Q->rear->link = QNode;
Q->rear = QNode;
}
}
- 데이터 삭제 함수(dequeue())
- 기능
- 노드가 있는 경우 : front에 저장된 값을 노드의 주소로 저장한 후, 노드의 주소를 front에 저장
- 노드가 없는 경우 : 공백상태 출력
- 함수의 자료형 : 노드의 데이터의 자료형
- 매개변수 : 삭제할 연결형 큐
- 기능
| 알고리즘 |
| 1.배열이 공백인 경우(front == NULL) : "공백상태"를 출력 2. 배열에 자리가 있을 경우 1-1. 삭제할 노드의 포인터 변수의 값을 front에 저장 1-2. 만약 front == NULL일 경우 rear도 NULL로 변경 |
element deQueue(LinkedQueue* Q) {
LinkedQueueNode* temp = NULL;
if (Q->front == NULL) {
printf("공백상태");
return 0;
}
else {
temp = Q->front;
element item = temp->data;
Q->front = Q->front->link;
if (Q->front == NULL) {
Q->rear == NULL;
}
free(temp);
return item;
}
}
- 데이터 출력 함수(printStack())
- 기능 : front부터 rear의 위치까지의 데이터 내용을 출력
| 알고리즘 | 노드에 저장되어 있는 데이터를 front부터 rear까지 출력 |
void printQueue(LinkedQueue* Q) {
LinkedQueueNode* temp = Q->front;
printf("\nLInked Queue:");
while (temp) {
printf("%5c", temp->data);
temp = temp->link;
}
}데이터 삽입, 데이터 삭제, 데이터 출력하는 함수를 구현했으며, 해당 함수들을 통해 연결 큐를 생성하면 다음과 같다.
#include<stdio.h>
#include<stdlib.h>
typedef char element;
typedef struct LinkedQueueNodeType {
element data;
struct LinkedQueueNodeType* link;
}LinkedQueueNode;
typedef struct LinkedQueueType {
LinkedQueueNode* front, * rear;
}LinkedQueue;
//공백 큐를 생성
LinkedQueue* createLinkedQueue() {
LinkedQueue* Q = (LinkedQueue*)malloc(sizeof(LinkedQueue));
Q->front = NULL;
Q->rear = NULL;
return Q;
}
//큐가 공백상태인지 확인
int isQueueEmpty(LinkedQueue* Q) {
if (Q->front == NULL) {
return 1;
}
else {
return 0;
}
}
//큐에 데이터를 입력
void enQueue(LinkedQueue* Q,element data) {
LinkedQueueNode* QNode = (LinkedQueueNode*)malloc(sizeof(LinkedQueueNode));
QNode->data = data;
QNode->link = NULL;
if (isQueueEmpty(Q)){
Q->front = QNode;
Q->rear = QNode;
}
else {
Q->rear->link = QNode;
Q->rear = QNode;
}
}
//큐 데이터 삭제
element deQueue(LinkedQueue* Q) {
LinkedQueueNode* temp = NULL;
if (isQueueEmpty(Q)) {
printf("공백상태");
return 0;
}
else {
temp = Q->front;
element item = temp->data;
Q->front = Q->front->link;
if (Q->front == NULL) {
Q->rear == NULL;
}
free(temp);
return item;
}
}
//큐 데이터 출력
void printQueue(LinkedQueue* Q) {
LinkedQueueNode* temp = Q->front;
printf("\nLInked Queue:");
while (temp) {
printf("%5c", temp->data);
temp = temp->link;
}
}
int main() {
LinkedQueue* Q = createLinkedQueue();
element data;
enQueue(Q,'A');
printQueue(Q);
enQueue(Q, 'B');
printQueue(Q);
enQueue(Q, 'C');
printQueue(Q);
data = deQueue(Q);
printQueue(Q);
printf("\t\tdeQueue : %c", data);
}
원형 큐
배열 큐는 사용한 공간은 두번 다시 사용하지 못해서 효율이 좋지 않다. 이 점을 보안하기 위해서 사용하는 자료구조가 있는데, 이 자료구조를 원형 Queue라고 한다. 원형 Queue란 Queue의 처음과 끝을 연결해 놓은 자료구조로, 어떤 요소가 첫번째 요소이고 어떤 요소가 마지막 요소인지 식별하기 위해 front와 rear를 사용한다.
typedef struct circleQueueNodeType {
element data;
}circleQueueNode;typedef struct circleQueueType {
circleQueueNode queue[4];
int front, rear;
} circleQueue;위의 코드는 큐의 노드와 큐의 정보인 사용할 배열과 front, rear를 구현해 놓은 것이다. 이때, node(노드)란 데이터를 저장하는 공간으로, 구조체를 통해 노드에 어떤 형태의 데이터를 저장할지 결정한다.
원형 큐의 알고리즘
원형 큐도 배열 큐처럼 데이터가 제일 먼저 삽입한 데이터는 제일 먼저 삭제되어야 하기에, 데이터를 삽입, 삭제 , 출력하는 기능을 알고리즘을 통해 소스코드로 구현해야 한다. 이때 front은 삭제되는 데이터가 위치하는 배열의 인덱스 값을 지정하며, rear는 삽입되는 데이터가 위치하는 배열의 인덱스값을 지정한다. 추가적으로 원형 큐는 배열 큐와 달리 사용한 인덱스를 다시 사용할 수 있기에, front와 rear를 설정해야 한다.
circleQueue* createCQueue() {
circleQueue* cQ;
cQ = (circleQueue*)malloc(sizeof(circleQueue));
cQ->front = 0;
cQ->rear = 0;
return cQ;
}
- 데이터 삽입 함수
- 기능
- 원형 큐가 포화상태일 경우(front == (rear+1)%최대 노드개수) : "포화상태"출력
- 원형 큐가 포화 상태가 아닐 경우 : rear에 다음 인덱스 위치를 부여하고, rear 위치에 데이터 삽입
- 함수의 자료형 : void
- 매개변수 : 저장할 데이터, 저장공간이 될 원형 큐
- 기능
| 알고리즘 |
| 1.배열이 포화인 경우(front == (rear+1)%최대 노드개수) "포화상태"를 출력 2. 배열에 자리가 있을 경우 2-1. rear를 다음 인덱스 위치로 변경 2-2. rear의 위치에 데이터 삽입 |
void enCQueue(circleQueue* cQ, element item) {
if (((cQ->rear + 1) % cQ_SIZE) == cQ->front)){
printf("포화상태");
return;
}
else {
cQ->rear = (cQ->rear + 1) % cQ_SIZE;
cQ->queue[cQ->rear].data = item;
}
}
- 데이터 삭제 함수
- 기능
- 원형 큐가 공백이 아닌 경우 : front 위치의 데이터를 삭제, front에 다음 인덱스 위치를 저장
- 배열에 공백인 경우(front == rear) : 배열에 저장되어 있는 데이터가 없다고 출력
- 함수의 자료형 : 데이터의 자료형
- 매개변수 : 저장공간인 원형 큐
- 기능
| 알고리즘 |
| 1.배열이 공백인 경우(front == rear) "공백상태"를 출력 2. 배열에 자리가 있을 경우 2-1. front의 위치를 다음 인덱스의 위치로 변경 2-2. front의 위치에 있는 데이터 삭제 |
element deCQueue(circleQueue* cQ) {
element data;
if (cQ->front == cQ->rear){
printf("공백상태");
return;
}
else {
cQ->front = (cQ->front + 1) % cQ_SIZE;
data = cQ->queue[cQ->front].data;
cQ->queue[cQ->front].data = NULL;
return data;
}
}- 데이터 출력 함수
- 기능 : front에 위치한 데이터를 시작으로 rear에 위치한 데이터 까지 출력
- 필드 내 사용 변수
- first ← front의 인덱스 위치
- last ← rear의 인덱스 위치
| 알고리즘 | first에 저장된 값이 last에 저장된 값과 같아질 때까지 노드에 저장된 데이터 값 출력 |
void printCQ(circleQueue* cQ) {
int first, last;
first = (cQ->front+1) % cQ_SIZE;
last = (cQ->rear+1) % cQ_SIZE;
printf(" Circular Queue : ");
while (first != last) {
printf("%3c", cQ->queue[first]);
first = (first + 1) % cQ_SIZE;
}
}데이터 삽입, 데이터 삭제, 데이터 출력하는 함수를 구현했으며, 해당 함수들을 통해 원형 큐를 생성하면 다음과 같다
#include <stdio.h>
#include <stdlib.h>
#define cQ_SIZE 4
typedef char element;
typedef struct circleQueueNodeType {
element data;
}circleQueueNode;
typedef struct circleQueueType {
circleQueueNode queue[cQ_SIZE];
int front, rear;
} circleQueue;
circleQueue* createCQueue() {
circleQueue* cQ;
cQ = (circleQueue*)malloc(sizeof(circleQueue));
cQ->front = 0;
cQ->rear = 0;
return cQ;
}
int isCQueueEmpty(circleQueue* cQ) {
if (cQ->front == cQ->rear) {
printf(" Circular Queue is empty! ");
return 1;
}
else return 0;
}
int isCQueueFull(circleQueue* cQ) {
if (((cQ->rear + 1) % cQ_SIZE) == cQ->front) {
printf(" Circular Queue is full! ");
return 1;
}
else return 0;
}
void enCQueue(circleQueue* cQ, element item) {
if (isCQueueFull(cQ)) return;
else {
cQ->rear = (cQ->rear + 1) % cQ_SIZE;
cQ->queue[cQ->rear].data = item;
}
}
element deCQueue(circleQueue* cQ) {
element data;
if (isCQueueEmpty(cQ)) return;
else {
cQ->front = (cQ->front + 1) % cQ_SIZE;
data = cQ->queue[cQ->front].data;
cQ->queue[cQ->front].data = NULL;
return data;
}
}
void printCQ(circleQueue* cQ) {
int i, first, last;
first = (cQ->front+1) % cQ_SIZE;
last = (cQ->rear+1) % cQ_SIZE;
printf(" Circular Queue : ");
i = first;
while (i!= last) {
printf("%3c", cQ->queue[i]);
i = (i + 1) % cQ_SIZE;
}
}
int main(void) {
circleQueue* cQ = createCQueue();
element data;
printf("\n 삽입 A>>"); enCQueue(cQ, 'A'); printCQ(cQ);
printf("\n 삽입 B>>"); enCQueue(cQ, 'B'); printCQ(cQ);
printf("\n 삽입 C>>"); enCQueue(cQ, 'C'); printCQ(cQ);
printf("\n 삭제 >>"); data = deCQueue(cQ); printCQ(cQ);
printf("\t삭제 데이터: %c", data);
printf("\n 삭제 >>"); data = deCQueue(cQ); printCQ(cQ);
printf("\t삭제 데이터: %c", data);
printf("\n 삭제 >>"); data = deCQueue(cQ); printCQ(cQ);
printf("\t\t삭제 데이터: %c", data);
printf("\n 삽입 D>>"); enCQueue(cQ, 'D'); printCQ(cQ);
printf("\n 삽입 E>>"); enCQueue(cQ, 'E'); printCQ(cQ);
return 0;
}
'알고리즘과 자료구조' Related Articles
more
Comments