[Data Structure] Queue(큐)

2023-01-12 4 분 소요

큐는 first-in first-out(FIFO)의 특징을 가진 선형 리스트이다. 알고리즘적으로는 대기열, 인터넷 전송 패킷 처리 등의 시뮬레이션을 풀이하는 데에 자주 쓰이며, BFS(깊이우선탐색)를 하기 위해선 반드시 알아야 하는 자료구조이다.

추상자료형 큐

유한 선형 리스트
메서드는 create(size), is_full(q), is_empty(q), enqueue(q, item), dequeue(q)
삽입이 일어나는 곳은 후단(rear)이 삭제가 일어나는 곳은 전단(front)
만약 큐가 모두 찬 상황에서 enqueue(q, item)을 호출할 경우, 오류 발생
만약 큐에 원소가 없는 경우에서 dequeue(q)를 호출할 경우, 오류 발생
선형큐, 원형큐, 덱으로 나누어짐.

선형큐

1차원 배열을 이용한 큐. 스택과 거의 유사함.
front, rear의 초기값은 모두 -1
만약 front와 rear가 같다면, 큐는 비어있음
rear == size-1이면, 큐는 포화상태
큐가 가득 차 있지 않은 상태에서 삽입 연산 시 rear에 1을 더하고, 큐가 비어 있지 않다면 삭제 연산 시 front에 1을 더한다.

front와 rear이 모두 증가하므로, 배열의 앞부분이 비어 있더라도 사용불가

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 5

typedef int element;
typedef struct{
  int front;
  int rear;
  element data[MAX_SIZE];
} Queue;

void init_queue(Queue *q){
  q->front = -1;
  q->rear = -1;
}

int is_full(Queue *q){
  if (q->rear==MAX_SIZE-1)
    return 1;
  else
    return 0;
}

int is_empty(Queue *q){
  if (q->front == q->rear)
    return 1;
  else
    return 0;
}

void enqueue(Queue *q, int item){
  if (is_full(q)){
    printf("큐가 가득찼습니다.");
    return;
  } else{
    q->data[++(q->rear)] = item;
  }
}

int dequeue(Queue *q){
  if (is_empty(q)){
    printf("큐가 비었습니다.");
    return -1;
  } else{
    int item = q->data[++(q->front)];
    return item;
  }
}

int main(){
  int item = 0;
  Queue q;
  init_queue(&q);
  enqueue(&q, 10);
  enqueue(&q, 20);
  enqueue(&q, 30);
  enqueue(&q, 40);
  enqueue(&q, 50);
  printf("%d %d\n", q.front, q.rear);
  printf("%d %d\n", dequeue(&q), q.front);
  printf("%d %d\n", dequeue(&q), q.front);
  printf("%d %d\n", dequeue(&q), q.front);
  printf("%d %d\n", dequeue(&q), q.front);
  printf("%d %d\n", dequeue(&q), q.front);
  printf("%d %d\n", q.front, q.rear);
  printf(is_empty(&q) ? "큐는 비었어요\n" : "큐에 원소가 있어요\n");
  enqueue(&q, 1);
  return 0;
}

원형큐

선형큐의 대안, front와 rear이 계속 증가하지 않음
front는 첫 번째 요소 바로 앞의 인덱스이며 rear은 마지막 요소의 인덱스
front와 rear의 초기값은 0
만약 front와 rear가 같다면, 큐는 비어있음
포화상태는 (rear + 1) % size == front
포화상태를 구분하기 위해서 하나의 공간은 반드시 비워야 함. 만약 하나의 공간이 비어있지 않다면 오류상태
포화상태가 아닐 때 삽입 연산을 할 경우, rear에 1을 더하고 이를 size로 나머지 연산

비어있지 않을 때 삭제 연산을 할 경우, front에 1을 더하고 이를 size로 나머지 연산

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 5
typedef int element;
typedef struct {
  element data[MAX_SIZE];
  int front;
  int rear;
}Queue;

void init_queue(Queue *q){
  q->front = 0;
  q->rear = 0;
}

int is_full(Queue *q){
  return (q->rear+1) % MAX_SIZE == q->front;
}

int is_empty(Queue *q){
  return q->front == q->rear;
}

void enqueue(Queue *q, int item){
  if (is_full(q)){
    printf("큐가 가득 찼어요. 삽입불가\n");
  } else{
    q->rear = (q->rear + 1) % MAX_SIZE;
    q->data[q->rear] = item;
  }
}

element dequeue(Queue *q){
  if (is_empty(q)){
    printf("큐가 비었어요. 삭제불가\n");
    return 0;
  } else{
    q->front = (q->front + 1) % MAX_SIZE;
    return q->data[q->front];
  }
}

int main(){
  int item = 0;
  Queue q;
  init_queue(&q);
  enqueue(&q, 10);
  enqueue(&q, 20);
  enqueue(&q, 30);
  enqueue(&q, 40);
  printf("%d %d\n", q.front, q.rear);
  printf("%d %d\n", dequeue(&q), q.front);
  printf("%d %d\n", dequeue(&q), q.front);
  printf("%d %d\n", dequeue(&q), q.front);
  printf("%d %d\n", dequeue(&q), q.front);
  printf("%d %d\n", q.front, q.rear);
  printf(is_empty(&q) ? "큐는 비었어요\n" : "큐에 원소가 있어요\n");
  enqueue(&q, 1);
  printf("%d %d\n", q.front, q.rear);
  enqueue(&q, 2);
  enqueue(&q, 3);
  enqueue(&q, 4);
  printf("%d %d\n", q.front, q.rear);
  printf("%d\n",is_full(&q));
  return 0;
}

덱(double-ended queue)

front와 rear에서 모두 삽입과 삭제가 가능한 큐, 원형큐로 구현함
front는 첫 번째 요소 바로 앞의 인덱스이며 rear은 마지막 요소의 인덱스
front와 rear의 초기값은 0
만약 front와 rear가 같다면, 큐는 비어있음
포화상태는 (rear + 1) % size == front
포화상태를 구분하기 위해서 하나의 공간은 반드시 비워야 함. 만약 하나의 공간이 비어있지 않다면 오류상태
포화상태가 아닐 때 front에서 삽입 연산을 할 경우, 현재 front에서 item을 할당 후, front를 (front - 1 + size) & size로 변경.(이때 size를 더하지 않을 경우, 음수 인덱스로 오류 발생)
포화상태가 아닐 때 rear에서 삽입 연산할 경우, rear를 (rear + 1) % size로 변경 후 item을 할당
비어있지 않을 때 front에서 삭제 연산을 할 경우, front에 1을 더하고 이를 size로 나머지 연산한 인덱스의 원소값을 반환

비어있지 않을 때 rear에서 삭제 연산을 할 경우, rear의 원소값을 반환하며 rear을 (rear-1+size) % size로 변경

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 5

typedef int element;

typedef struct {
  int front, rear;
  element data[MAX_SIZE];
} Deque;

void init_deque(Deque *d){
  d -> front = 0;
  d -> rear = 0;
}

int is_full(Deque *d){
  return (d->rear + 1) % MAX_SIZE == d->front;
}

int is_empty(Deque *d){
  return d->front == d->rear;
}

void push_front(Deque *d, int item){
  if (is_full(d)){
    printf("덱이 가득찼어요.\n");
  } else{
    d->data[d->front] = item;
    d->front = (d->front-1+MAX_SIZE) % MAX_SIZE;
  }
}

element delete_front(Deque *d){
  if (is_empty(d)){
      printf("덱이 비었어요.\n");
      return 0;
  } else{
    d->front = (d->front + 1) % MAX_SIZE;
    return d->data[d->front];
  }
}

void push_back(Deque *d, int item){
  if (is_full(d)){
    printf("덱이 가득찼어요.\n");
  } else{
    d->rear = (d->rear + 1) % MAX_SIZE;
    d->data[d->rear] = item;
  }
}

element delete_back(Deque *d){
  if (is_empty(d)){
      printf("덱이 비었어요.\n");
      return 0;
  } else{
    int prev = d->rear;
    d->rear = (d->rear-1+MAX_SIZE)% MAX_SIZE;
    return d->data[prev];
  }
}

int main(){
  Deque d;
  init_deque(&d);
  delete_front(&d);
  push_front(&d, 20);
  printf("%d %d\n", d.front, d.rear);
  printf("%d %d %d\n" , delete_back(&d), d.front, d.rear);
  push_back(&d, 10);
  printf("%d %d\n", d.front, d.rear);
  printf("%d %d %d\n" , delete_front(&d), d.front, d.rear);
}

Twitter Facebook LinkedIn

pugcute

[Data Structure] Queue(큐)

추상자료형 큐

선형큐

원형큐

덱(double-ended queue)

공유하기

댓글남기기

참고

[HTML] HTML 정리 - 입력 양식

[NETWORK] OSI 7Layer

[HTML] HTML 정리

[SQL] 코딩테스트 대비용 SQL