180301 튜터링 - 큐(Queue)

< 180301 >

- Queue 정의 : 먼저 들어온 데이터가 먼저 꺼내지는 자료구조

- 예시 : 버스에서 줄서기(앞에 선 사람이 먼저 탐), 

            스타크래프트 게이트웨이(질럿, 드라군, 다크 순으로 찍으면 질럿, 드라군, 다크 순으로 나온다.)

- (선형)큐 구현하기.

#include <stdio.h>
#include <stdlib.h>
 
#define MAX 100
 
typedef struct queue {
    int data[MAX];
    int front;
    int rear;
} Queue;
 
void init(Queue * q) {
    q->front = 0;
    q->rear = 0;
}
 
int isEmpty(Queue * q) {
    return (q->front == q->rear);
}
 
void enqueue(Queue * q, int data) {
    q->data[(q->rear)++] = data;
}
 
int peek(Queue * q) {
    if (isEmpty(q)) {
        printf("(peek)큐가 비어있습니다. : ");
        return -11111;
    }
    return q->data[q->front];
}
 
void dequeue(Queue * q) {
    if (!isEmpty(q)) {
        (q->front)++;
    }
}
 
int main()
{
    Queue q;
    init(&q);
 
    enqueue(&q, 1);
    enqueue(&q, 9);
    enqueue(&q, 9);
    enqueue(&q, 8);
 
    printf("%d\n", peek(&q));
    dequeue(&q);
 
    printf("%d\n", peek(&q));
    dequeue(&q);
 
    printf("%d\n", peek(&q));
    dequeue(&q);
 
    printf("%d\n", peek(&q));
    dequeue(&q);
 
    printf("%d\n", peek(&q));
}
 

>> 이런식으로 구현할 수 있다.

>> 하지만 이렇게 될 경우, 배열의 앞 공간에 낭비가 발생한다.

- 원형 큐 (coded by ㄱㄱㄷ ㅋㄱ ㄱㅇㄹ)

#include <stdio.h>
#include <stdlib.h>
 
#define MAX 100
 
typedef struct queue {
   int data[MAX];
   int front;
   int rear;
} Queue;
 
void init(Queue * q) {
   q->front = 0;
   q->rear = 0;
}
 
int isEmpty(Queue * q) {
   return (q->front == q->rear);
}
 
int isFull(Queue * q) {
   return (q->rear+1)%MAX == q->front;
}
 
void enqueue(Queue * q, int data) {
   if (isFull(q)) printf("큐가 포화상태입니다. 더이상 삽입할 수 없습니다.\n");
   else {
      q->rear = (q->rear + 1) % MAX;
      q->data[q->rear] = data;
   }
}
 
int peek(Queue * q) {
   if (isEmpty(q)) {
      printf("(peek)큐가 비어있습니다. : ");
      return -11111;
   }
   return q->data[(q->front+1) % MAX];
}
 
void dequeue(Queue * q) {
   if (isEmpty(q)) printf("(deqeue)큐가 비어있습니다.\n");
   else {
      q->front = (q->front + 1) % MAX;
   }
}
 
int main()
{
   Queue q;
   init(&q);
 
   enqueue(&q, 1);
   enqueue(&q, 9);
   enqueue(&q, 9);
   enqueue(&q, 8);
 
   printf("%d\n", peek(&q));
   dequeue(&q);
 
   printf("%d\n", peek(&q));
   dequeue(&q);
 
   printf("%d\n", peek(&q));
   dequeue(&q);
 
   printf("%d\n", peek(&q));
   dequeue(&q);
   
   printf("%d\n", peek(&q));
 

}

>> 사용한 공간의 낭비를 막을 수 있다.

>> 빈 상태와 포화상태를 구분하기 위해 한 칸을 비워둔다. 

>> 21-23 :  포화상태에 대한 코드이다. 모듈러 연산을 통해 마지막 인덱스 다음 인덱스를 0으로 만들 수 있다.

### 연결리스트를 이용한 큐를 만들어보자. 

>> head 포인터를 front 로, tail 포인터를 rear 로 두고 만들면 된다.

### 덱

>> 앞으로도 넣고 뒤로더 넣을 수 있으며, 앞에서도 꺼내고 뒤에서도 꺼낼 수 있다.