1.큐의 이해와 ADT
먼저 들어간 것이 먼저 나온다.
즉, First in - FIrst out의 구조
줄서기를 예시로 생각하면 편할 것이다.
ADT
1.초기화 2.큐가 비었는지 여부 검사 3.데이터 저장 4.데이터 삭제
5.저장순서가 가장 앞선 데이터를 반환하되 삭제하지X
큐는 배열기반으로도 연결리스트 기반으로도 구현할 수 있는데,
배열기반의 큐가 좀더 논의할 것이 많다.
2. 큐의 연결리스트 기반 구현
백준10845번 큐 를 연결리스트를 기반으로 큐를 구현하여 풀어보았다.
https://www.acmicpc.net/problem/10845
내 코드
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
int data;
struct node* next;
} Node;
typedef struct queue
{
Node* front;
Node* back;
int size;
} Queue;
void QueueInit(Queue* pqueue)
{
pqueue->front = (Node*)malloc(sizeof(Node));
pqueue->front->next = NULL;
pqueue->back = NULL;
pqueue->size = 0;
}
void push(Queue* pqueue, int data)
{
Node* temp = (Node*)malloc(sizeof(Node));
temp->data = data;
temp->next = NULL;
if (pqueue->front->next == NULL)
{
pqueue->front->next = temp;
pqueue->back = temp;
}
else
{
pqueue->back->next = temp;
pqueue->back = temp;
}
(pqueue->size)++;
}
int pop(Queue* pqueue)
{
if (pqueue->front->next == NULL) return -1;
else
{
int deldata = pqueue->front->next->data;
Node* delNode = pqueue->front->next;
pqueue->front->next = delNode->next;
(pqueue->size)--;
free(delNode);
return deldata;
}
}
int main()
{
int i, N;
int temp;
scanf("%d", &N);
char array[10] = { 0 };
Queue queue;
Queue* pqueue = &queue;
QueueInit(pqueue);
for (i = 0; i < N; i++)
{
scanf("%s", array);
if (strcmp(array, "push") == 0)
{
scanf("%d", &temp);
push(pqueue, temp);
}
else if (strcmp(array, "pop") == 0)
{
temp = pop(pqueue);
printf("%d\n", temp);
}
else if (strcmp(array, "size") == 0)
{
temp = pqueue->size;
printf("%d\n", temp);
}
else if (strcmp(array, "empty") == 0)
{
if (pqueue->front->next == NULL) printf("1\n");
else printf("0\n");
}
else if (strcmp(array, "front") == 0)
{
if (pqueue->front->next == NULL) printf("-1\n");
else printf("%d\n", pqueue->front->next->data);
}
else
{
if (pqueue->front->next == NULL) printf("-1\n");
else printf("%d\n", pqueue->back->data);
}
}
return 0;
}
//큐가 비었다는 것은 pqueue->front->next == NULL 로 판단하는 것이 핵심이다.
3. 큐의 배열 기반 구현
큐의 배열 기반 구현은 좀더 설명할 것이 많다고 하여 강의를 듣고 직접 구현해보기로 하였다.
(1)보편적인 구현 논리
처음에는 F = 0, R = -1 //F는 입구, R은 출구
새로운 성분을 넣을 때마다 R을 +1하면서 array[R]에 값을 저장//이 떄 R이 꼬리
성분을 꺼낼 때마다 F를 +1하면서 array[F]를 출력한다.//F는 출력되어야할 데이터 즉, 머리
(2)이러한 구현 논리의 문제점
이미 출력한 데이터가 저장되어 있는 배열의 앞부분을 더 이상 활용할 수 없다.
이 때 데이터를 더 추가하기 위해서는 R을 인덱스가 0인 위치로 이동시켜야 한다.
이러한 방식으로 문제를 해결한 것이 바로 '원형 큐'이다.
//R이 F를 따라잡지 않으려면? R이 F를 따라잡으려면 배출되지 않고 저장되는 데이터의 개수가 배열의 칸수보다 많아야 한다. 즉, 처음 배열의 개수를 배출되지 않고 저장되는 최대 데이터의 개수보다 많게 설정하면 된다.
(3)원형 큐의 단순한 연산의 문제점
F와 R의 관계로 현재 데이터의 개수를 판단할 수 있다.
그런데
완전히 채워졌을 때 F와 R의 관계를 보면 R + 1 = F이다.
그런데 완전히 비워졌을 때를 보면 데이터가 하나 남았을 때 F = R이므로 데이터가 모두 비워지면 F가 1 더 커지므로 R + 1 = F가 된다.
즉, 완전히 비워졌을 때와 완전히 채워졌을 때의 R과 F의 관계가 완전히 같다.
<내가 생각하는 해결책>
R과 F를 원래대로 돌리는게 아니라 modular연산을 통해 가리켜야하는 배열의 number를 이야기하는게 맞다.
그러면 가득 찼을 때와 텅 비었을 때의 구분 역시 가능하고 R,F를 통해 데이터의 개수 역시 알 수 있다.
-> 내가 생각한 해결책의 문제점 :
(1) R,F가 INT_MAX를 넘어갈 수 없다.
(2) 모듈러 연산을 하면 시간이 많이 걸린다.
(4)문제를 해결한 원형 큐
R과 F가 같은 칸일 때 데이터의 개수가 0개, 데이터가 채워지다가 F - 1 = R일 때 FULL이도록 하면 empty와 full이 구분된다.
이 때, F는 빈칸, 즉, 데이터의 출력은 array[F+1]을 출력하는 걸로 한다.
(5)내가 구현한 코드
강의에서 제공한 헤더파일
#ifndef __C_QUEUE_H__
#define __C_QUEUE_H__
#define TRUE 1
#define FALSE 0
#define QUE_LEN 4 // 정상적으로 원형으로 큐를 구현했는지 확인하기 위해 일부러 QUE_LEN을 작게 잡았다. 이 때, 저장할 수 있는 데이터의 수는 최대 3개
typedef int Data;
typedef struct _cQueue
{
int front;
int rear;
Data queArr[QUE_LEN];
} CQueue;
typedef CQueue Queue;
void QueueInit(Queue * pq);
int QIsEmpty(Queue * pq);
void Enqueue(Queue * pq, Data data);
Data Dequeue(Queue * pq);
Data QPeek(Queue * pq);
#endif내가 만든 소스 코드
#include <stdio.h>
#include "CircularQueue.h"
void QueueInit(Queue* pq)
{
pq->front = 0;
pq->rear = 0;
}
int QIsEmpty(Queue* pq)
{
if (pq->front == pq->rear) return 1;
else return 0;
}
void Enqueue(Queue* pq, Data data)
{
if (pq->front == (pq->rear + 1) % QUE_LEN)
{
printf("큐가 배불러요");
}
else
{
pq->rear = (pq->rear + 1) % QUE_LEN;//이 부분에서 오류가 났었다.
pq->queArr[pq->rear] = data;//front눈 언제나 맨처음 데이터 앞칸을 rear는 맨마지막 데이터를 가리켜야한다.
}
}
Data Dequeue(Queue* pq)
{
if (QIsEmpty(pq))
{
printf("큐가 굶어죽어요");
return -1;
}
else
{
pq->front = (pq->front + 1) % QUE_LEN;
return pq->queArr[pq->front];
}
}
Data QPeek(Queue* pq)
{
if (QIsEmpty(pq))
{
printf("큐가 굶어죽어요");
return -1;
}
else
{
return pq->queArr[pq->front + 1];
}
}실행한 메인 함수
#include <stdio.h>
#include "CircularQueue.h"
int main(void)
{
// Queue의 생성 및 초기화 ///////
Queue q;
QueueInit(&q);
// 데이터 넣기 ///////
Enqueue(&q, 1); Enqueue(&q, 2);
Enqueue(&q, 3);
// 데이터 꺼내기 ///////
while(!QIsEmpty(&q))
printf("%d ", Dequeue(&q));
Enqueue(&q, 4); Enqueue(&q, 5);
while (!QIsEmpty(&q))
printf("%d ", Dequeue(&q));
return 0;
}(6) 강의의 소스 코드
#include <stdio.h>
#include <stdlib.h>
#include "CircularQueue.h"
void QueueInit(Queue * pq)
{
pq->front = 0;
pq->rear = 0;
}
int QIsEmpty(Queue * pq)
{
if(pq->front == pq->rear)
return TRUE;
else
return FALSE;
}
int NextPosIdx(int pos)
{
if(pos == QUE_LEN - 1) return 0;
else return pos + 1;
}//나와 가장 큰 차이가 있는 코드이다. 나는 모듈러 연산을 계속하는 반면 이 코드는 단순하게 pos가 QUE_LEN - 1 이면 0을 return하여 배열의 첫번째 칸으로 돌아가게 하고 아니면 pos + 1을 return 한다.
void Enqueue(Queue * pq, Data data)
{
if(NextPosIdx(pq->rear) == pq->front)//나와 흡사라나 NextPosIdx라는걸 활용한게 차이점 아 Idx가 인덱스였구나
{
printf("Queue Memory Error!");
exit(-1);// -1을 return하고 종료. return -1;과 같으나 오류가 있을 때 주로 사용. 나도 애용해야겠다.
}
pq->rear = NextPosIdx(pq->rear);//modular보다 가독성이 좋아졌다. 연산 속도도 더 좋겠지
pq->queArr[pq->rear] = data;//rear가 다음칸에 가고 그 다음칸에 data 저장.
}
Data Dequeue(Queue * pq)
{
if(QIsEmpty(pq))
{
printf("Queue Memory Error!");
exit(-1);
}
pq->front = NextPosIdx(pq->front);
return pq->queArr[pq->front];//오 이것도 나랑 같을 줄은 생각 못 했는데 ㅋㅋ
나는 pq->front를 return 뒤에 바꿀 수는 없으니 이렇게 하자는 생각이었다.
}
Data QPeek(Queue * pq)
{
if(QIsEmpty(pq))
{
printf("Queue Memory Error!");
exit(-1);
}
return pq->queArr[NextPosIdx(pq->front)];
}modular 연산 대신 NextPosIndx라는 함수를 만들어 활용한 것을 제외하고는 나와 완전히 같다.
