큐

5장 큐

- 정리의 기반은 학교 강의 노트와 [c언어로 쉽게 풀어쓴 자료구조]를 참고하였습니다.

저의 정리가 옳지 않다면 피드백 부탁드립니다.

---

큐

• 정의 : 먼저 들어온 데이터가 먼저 나가는 구조(선입 선출 : FIFO(First-In First-Out))
• ex) 매표소에서 표를 사기 위해 늘어선 줄
• 특징 : 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조로, 스택과 다른 점은 삽입과 삭제가 다른 쪽에서 일어난다는 점이다.
• 삽입 연산 : enqueue(rear변수 활용)
• 삭제 연산 : dequeue(front변수 활용)
• 큐의 종류 : 선형 큐, 원형 큐

선형 큐 주의 사항

• 스택 top의 초기값 = -1
• 스택이 full일 경우 = MAX_STACK_SIZE-1

선형 큐 문제점

이해하기엔 쉬우나, front와 rear의 값이 계속 증가만 하기 때문에 언젠가는 큐를 사용하는 배열의 끝에 도달하게 되고 배열의 앞부분이 비어 있더라도 사용하지를 못한다. 그래서 주기적으로 모든 요소들을 왼쪽으로 이동시켜야 한다.
-> 시간이 상당히 많이 걸리고, 복잡해짐.
-> 해결 방안 : 큐를 원형으로 생각하여 front와 rear의 값이 배열의 끝인 (MAX_QUEUE_SIZE-1)에 도달하면 다음에 증가되는 값은 0이 되도록 하는 것

원형 큐 주의 사항

• 초기값 : front, rear = 0 (front는 첫번째 요소의 하나 앞을 가리킨다)
• 공백 상태 : front = rear
• 포화 상태 : front = rear + 1
• front = (front + 1) % 큐 사이즈
• rear = (front + 1) % 큐 사이즈

덱

• 정의 : double-ended queue의 줄임말로, 큐의 front와 rear에서 모두 삽입과 삭제가 가능한 큐

원형 큐

#include <stdio.h>
#include <stdlib.h>

#define MAX_QUEUE_SIZE 10
typedef int element;
typedef struct {
  element data[MAX_QUEUE_SIZE];
  int front, rear;
} QueueType;

// 큐 시작
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 enqueue(QueueType *q)
{
  if (is_full(q))
    printf("error : 포화 상태");
  q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
  q->data[q->rear] = item;
}


//삭제
element dequeue(QueueType *q)
{
  if (is_empty(q))
    printf("error : 공백 상태");
  q->front = (q->front + 1) % MAX_QUEUE_SIZE;
  return q->data[q->front];
}