현재 나는 C로하는 자료구조와 Java로 하는 운영체제를 동시에 수강하고 있는데, JAVA로 CPU Scheduling을 할때 Queing 연산을 한다고 우리는 말한다.
위에서 말한 큐를 포스팅 해보겠다
다시한번 말하지만 내가 참고한 책은 다음과 같다
[C언어로 쉽게 풀어쓴 자료구조; 천인국,공용해,하상호 저]
이전에 스택은 LIFO구조로써 Last In First Out으로 마지막에 들어간것이 먼저 나가는 구조였다 하지만 큐는 First In First Out(FIFO)구조이다.
큐는 한마디로 터널에 먼저 들어온 차 순서대로 먼저 나가는 구조를 생각해보면 된다.
큐와 관련된 ADT를 살펴보겠다
create(max_size) ::=
최대 크기가 max_size인 공백큐를 생성한다.
init(q) ::=
큐를 초기화한다.
is_empty(q) ::=
if(size==0) return TRUE;
else return FALSE;
if_full(q) ::=
if(size==max_size) return TRUE;
else return FALSE;
enqueue(q,e) ::=
if(is_full(q)) queue_full 오류;
else q의 끝에 e를 추가한다.
dequeue(q) ::=
if(is_empty(q)) queue_empty 오류;
else q의 맨 앞에 있는 e를 제거해서 반환한다.
peek(q) ::=
if(is_empty(q)) queue_empty 오류
else q의 맨 앞에 있는 e를 읽어서 반환한다.위에서 보듯이 스택과 크게 달라진점이 없다 스택의 push가 큐에 와서는 enqueue로 바뀐 것이고 스택의 pop이 큐에 와서는 dequeue(q)로 바뀐 것이다.
큐의 응용
직접적인 응용
- 위에서 말한 CPU스케줄링에 사용된다
- 비슷한 느낌으로 프린터와 컴퓨터 사이의 버퍼링에서 여러대의 컴퓨터에서 동시에 프린트를 할떄 먼저 도착한 순서대로 처리를 해준다.
- 시뮬레이션을 할때 대기열에서도 큐가 사용되고
- 통신에서의 packet의 모델링에서도 이용된다
간접적인 응용
- 스택과 마찬가지로 프로그래머의 도구
- 많은 알고리즘에서 사용됨
스택에서는 Top과 bottom을 이용해서 데이터를 쌓아갔다
큐에서는 front와 rear를 이용하는데 차이점은 스택은 마지막에 들어온것이 먼저 나가기때문에 bottom이 고정돼있어도 된다 하지만 큐에서는 front와 rear둘다 움직인다.
선형큐
- 배열을 선형으로 사용해서 큐를 구현했다.
(a) 초기상태에서는 front와 rear둘다 -1을 가리킨다
(b) enqueue로 3이 들어오면 rear를 한칸 뒤로 옮기고 3을 집어 넣는다
(c) enqueue로 7이 들어오면 rear를 한칸 뒤로 옮기고 7을 집어넣는다
(d) enqueue로 5가 들어오면 rear를 한칸 뒤로 옮기고 5를 집어넣는다(rear는 5가 있는 칸을 가리킨다)
(e) 는 그림에 문제가 있는데 현재 [2]에 5가 들어있고 rear도 [2]를 가리켜야 한다.
이때, dequeue()가 실행되면 먼저들어온 3이 제거되어 반환되고 front가 한칸 뒤로 옮겨진다.
(f) dequeue()가 실행되면 먼저들어온 7이 제거되어 반환되고 front가 한칸 뒤로 옮겨진다.
위의 메모리 구조를 보면 언젠가는 메모리가 부족할 것으로 보인다 따라서 나온 것이 원형큐이다.
선형큐를 구현한 코드를 확인해보자
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct { // 큐 타입
int front; //front를 나타냄
int rear; //rear를 나타냄
element data[MAX_QUEUE_SIZE]; //사용할 메모리라고 생각
} QueueType;
// 오류 함수
void error(char *message)
{
fprintf(stderr, "%s\n", message);
exit(1); //프로그램 종료
}
void init_queue(QueueType *q)
{
q->rear = -1;
q->front = -1;
}
void queue_print(QueueType *q)
{
for (int i = 0; i<MAX_QUEUE_SIZE; i++) {
if (i <= q->front || i> q->rear)
printf(" | ");
else
printf("%d | ", q->data[i]);
}
printf("\n");
}
int is_full(QueueType *q)
{
if (q->rear == MAX_QUEUE_SIZE - 1)
return 1;
else
return 0;
}
int is_empty(QueueType *q)
{
if (q->front == q->rear)
return 1;
else
return 0;
}
void enqueue(QueueType *q, int item)
{
if (is_full(q)) {
error("큐가 포화상태입니다.");
return;
}
q->data[++(q->rear)] = item; //q의 rear를 한칸 뒤로 옮기고 그위치의 데이터에 item 을 넣을 것
}
int dequeue(QueueType *q)
{
if (is_empty(q)) {
error("큐가 공백상태입니다.");
return -1;
}
int item = q->data[++(q->front)];
//q의 front를 한칸 뒤로 옮기고 그위치의 데이터를 꺼내서 item에 넣음
//이때 사실 값만을 꺼내서 엄밀하게 말하면 제거해서 반환한 것은 아니다
return item;
}
int main(void)
{
int item = 0;
QueueType q; //현재 front rear 메모리가 있음
init_queue(&q); // rear와 front를 둘다 -1로 초기화
enqueue(&q, 10); queue_print(&q); //구조체 포인터 데이터 10을 enqueing함
enqueue(&q, 20); queue_print(&q);
enqueue(&q, 30); queue_print(&q);
item = dequeue(&q); queue_print(&q); //dequeing
item = dequeue(&q); queue_print(&q);
item = dequeue(&q); queue_print(&q);
return 0;
}다시한번 말하지만 선형큐는 계속 뒤로 밀리는 구조여서 앞에 빈 메모리를 활용하지 못한다.
반면에 원형큐는 (rear+1)%Maxarraysize로 이 문제를 해결했다. 수학에 조예가 깊은 사람들은 mod연산과 비슷하다고 생각하면 좋다.
원형큐도 선형큐와 마찬가지로 관리를할 front와 rear두개가 필요한데 원형큐는 선형큐와 다르게 일정메모리에서 벗어나지 않는다. 이때 front와 rear는 처음에 0을 가리키고 있다(선형큐는 초기에 front와 rear초기값 -1)
선형큐와 마찬가지로 삽입을 하면 rear가 이동하고 삽입되고 지워지면 먼저 들어온 것이 삭제되고 front가 이동한다
위의 그림을 이해하기 위해서는 다음을 알아야 한다.
우리는 item이 다찬 상태로 front와 rear가 같은 위치를 가리키고 있으면 오류상태라고 하고 오류상태 직전에 더 삽입할 수 없는 상태를 포화상태라고 할 것이다.
우리가 바로 위 포화상태에서 하나를 삭제한다고 해보자 그러면 우리는 하나를 넣을 수 있을것이다. 당연하게도 우리는 직관적으로 0에 넣는 상황을 상상할 수 있다. 하지만 7+1=8이기 때문에 이를 전체 MaxSize와의 나머지 연산(%)를 취해서 0을 가리키게 해주면 된다.
위와 같은 방법으로 우리는 선형큐에서 dequeue가 일어났을때 앞에 빈공간을 삭제하는 원형큐를 배워봤다.
이제 원형큐를 한번 구현해보자.
#include <stdio.h>
#include <stdlib.h>
// ===== 원형큐 코드 시작 ======
#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct { // 큐 타입
element data[MAX_QUEUE_SIZE];
int front, rear;
} QueueType;
// 오류 함수
void error(char *message)
{
fprintf(stderr, "%s\n", message);
exit(1);
}
// 공백 상태 검출 함수
void init_queue(QueueType *q)
{
q->front = q->rear = 0;
}
// 공백 상태 검출 함수
int is_empty(QueueType *q)
{
return (q->front == q->rear);
}
// 포화 상태 검출 함수
int is_full(QueueType *q)
{
return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}
// 원형큐 출력 함수
void queue_print(QueueType *q)
{
printf("QUEUE(front=%d rear=%d) = ", q->front, q->rear);
if (!is_empty(q)) {
int i = q->front;
do {
i = (i + 1) % (MAX_QUEUE_SIZE);
printf("%d | ", q->data[i]);
if (i == q->rear)
break;
} while (i != q->front);
}
printf("\n");
}
// 삽입 함수
void enqueue(QueueType *q, element item)
{
if (is_full(q))
error("큐가 포화상태입니다");
q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
q->data[q->rear] = item;
}
// 삭제 함수
element dequeue(QueueType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다");
q->front = (q->front + 1) % MAX_QUEUE_SIZE;
return q->data[q->front];
//위의 선형큐와 마찬가지로 실제로 값을 삭제한 것은 아니다.
}
// 삭제 함수
element peek(QueueType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다");
return q->data[(q->front + 1) % MAX_QUEUE_SIZE];
}
// ===== 원형큐 코드 끝 ======
int main(void)
{
QueueType queue;
int element;
init_queue(&queue);
printf("--데이터 추가 단계--\n");
while (!is_full(&queue))
{
printf("정수를 입력하시오: ");
scanf("%d", &element);
enqueue(&queue, element);
queue_print(&queue);
}
printf("큐는 포화상태입니다.\n\n");
printf("--데이터 삭제 단계--\n");
while (!is_empty(&queue))
{
element = dequeue(&queue);
printf("꺼내진 정수: %d \n", element);
queue_print(&queue);
}
printf("큐는 공백상태입니다.\n");
return 0;
}덱(deque)
덱(deque)은 double-ended queue의 줄임말로 기존의 front에서만 삽입과 삭제가 가능했던 거에서 front와 rear 모두에서 삽입과 삭제가 가능한 큐이다. 다시말해 우리는 원형큐에서 삽입을 하기 위해서는 rear를 하나 뒤로 이동시키고 삽입을 하고 삭제를 하기 위해서는 삭제를 한후 front를 한칸 앞으로 당겼다. 덱은 여기에 추가로 rear에서 삭제를 하기 위해 rear에서 삭제를 하고 rear를 한칸 되돌리고 front에서 삽입을 하기 위해서 뒤로 당긴후 삽입을 하는 시계 반대방향의 방향성도 더해준 것이다
덱과 관련된 ADT를 확인해 보겠다.
create() ::=
덱을 생성한다.
init(dq) ::=
덱을 초기화 한다.
is_empty(dq) ::=
덱이 공백상태인지를 검사한다.
if_full(dq) ::=
덱이 포화상태인지를 검사한다.
add_front(dq,e) ::=
덱의 앞에 요소를 추가한다.
add_rear(dq,e) ::=
덱의 뒤에 요소를 추가한다.
delete_front(dq) ::=
덱의 앞에 있는 요소를 반환한 다음 삭제한다.
delete_rear(dq) ::=
덱의 뒤에 있는 요소를 반환한 다음 삭제한다.
get_front(dq) ::= 덱의 앞에서 삭제하지 않고 앞에 있는 요소를 반환한다.
get_rear(dq) ::= 덱의 뒤에서 삭제하지 않고 뒤에 있는 요소를 반환한다. 코드를 확인해보면 시계 반대방향의 방향성이라는 말이 와닿을 것이다.
사실 처음에는 rear가 front뒤에 있고 앞에있고에 따른 상대적인 위치가 헷갈렸다 rear가 front보다 뒤에 있어도 되는가?-> 이문제는 '원' 이기에 해결이 되는 것이다.
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct { // 큐 타입
element data[MAX_QUEUE_SIZE];
int front, rear;
} DequeType;
// 오류 함수
void error(char *message)
{
fprintf(stderr, "%s\n", message);
exit(1);
}
// 초기화
void init_deque(DequeType *q)
{
q->front = q->rear = 0;
}
// 공백 상태 검출 함수
// 공백 상태는 [0] 이 아닌 다른 부분에서 공백상태가 검출될 수 있다.
int is_empty(DequeType *q)
{
return (q->front == q->rear);
}
// 포화 상태 검출 함수
int is_full(DequeType *q)
{
return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}
// 원형큐 출력 함수
void deque_print(DequeType *q)
{
printf("DEQUE(front=%d rear=%d) = ", q->front, q->rear);
if (!is_empty(q)) {
int i = q->front;
do {
i = (i + 1) % (MAX_QUEUE_SIZE);
printf("%d | ", q->data[i]);
if (i == q->rear)
break;
} while (i != q->front);
}
printf("\n");
}
// 삽입 함수
void add_rear(DequeType *q, element item)
{
if (is_full(q))
error("큐가 포화상태입니다");
q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
q->data[q->rear] = item;
}
void add_front(DequeType *q, element val)
{
if (is_full(q))
error("큐가 포화상태입니다");
q->data[q->front] = val;
q->front = (q->front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
//음수의 나머지를 구하는 문제가 생기기 때문에 빼는 과정에서 MAX_QUEUE_SIZE만큼 더해주고 나머지를 구해준다.
}
// 삭제 함수
element delete_front(DequeType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다");
q->front = (q->front + 1) % MAX_QUEUE_SIZE;
return q->data[q->front];
}
element get_front(DequeType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다");
return q->data[(q->front + 1) % MAX_QUEUE_SIZE];
}
// 삭제 함수
element delete_rear(DequeType *q)
{
int prev = q->rear; // 데이터를 가져올 previous_index를 미리 저장해둔다
if (is_empty(q))
error("큐가 공백상태입니다");
q->rear = (q->rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
// add_front와 마찬가지로
// rear가 1칸씩 감소하다보면 음수가 나오는 문제가 있기 때문에 MAX_QUEUE_SIZE를 더해줌으로써 이를 해결한다.
return q->data[prev]; // 저장해놓은 previous_index를 사용해 데이터를 반환한다.
}
element get_rear(DequeType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다");
return q->data[q->rear];
}
int main(void)
{
DequeType queue;
init_deque(&queue);
for (int i = 0; i < 3; i++) {
add_front(&queue, i);
deque_print(&queue);
}
for (int i = 0; i < 3; i++) {
delete_rear(&queue);
deque_print(&queue);
}
return 0;
}