Vol.5: Queue

Queue 자료의 작동 방식을 생각하고 활용하는 방법을 이해합니다.
C 언어를 이용하여 Queue의 자료 구조를 직접 실현할 수 있습니다.

Queue란?

👌 Queue는 뒤에서 들어가서 전방으로 나오는 자료 구조(Data Structure)입니다.
👌 이러한 특성으로부터 스케줄링, 탐색 알고리즘 등으로 다방면에 활용됩니다.

PUSH:Queue에 데이터를 넣습니다.
POP:Queue에서 데이터를 검색합니다.

Queue는 뒤에서 들어가서 앞으로 나오는 자료 구조(Data Structure)입니다.

예)

PUSH(7) – PUSH(5) – PUSH(4) – POP() – PUSH(6) – POP()

🤔 결과는?

Queue 구현

👌Queue는 배열을 이용한 구현 방법과 Linked List를 이용한 구현 방법으로 나뉩니다.
👌 가장 기본적인 형태의 자료구조이며, 실현의 난이도는 낮은 편입니다.

배열을 이용한 Queue 실현

예) 실행할 코드의 예

//Queueの宣言
#include <stdio.h>
#define SIZE 10000
#define INF 99999999
int queue[SIZE];
int front = 0;
int rear = 0;

//Queue挿入関数
void push(int data) {
  if (rear >= SIZE) {
    printf("Queue Overflowが発生しました。\n");
    return;
  }
  queue[rear++] = data;
}
//Queue抽出関数
int pop() {
  if (front == rear) {
    printf("Queue Underflowが発生しました。\n");
    return -INF;
  }
  return queue[front++];
}
//Queue全体の出力関数
void show() {
  printf("--- Queueの前 ---\n");
  for (int i = front; i < rear; i++) {
    printf("%d\n", queue[i]);
  }
  printf("--- Queueの後ろ ---\n");
}
//完成したQueueを使用する
int main(void) {
  push(7);
  push(5);
  push(4);
  pop();
  push(6);
  pop();
  show();
  system("pause");
  return 0;
}

🤔 결과는?result->--- Queueの前 ---
4
6
--- Queueの後ろ ---

Linked List를 이용한 Queue 실현

예) 실행할 코드의 예

//Queueの宣言
#include<stdio.h>
#include<stdlib.h>
#define INF 99999999
typedef struct Node{
  int data;
  struct Node *next;
} Node;
typedef struct Queue{
  Node *front;
  Node *rear;
  int count;
} Queue;

//Queue挿入関数
void push(Queue *queue, int data) {
  Node *node = (Node*)malloc(sizeof(Node));
  node->data = data;
  node->next = NULL;
  if (queue->count == 0) {
    queue->front = node;
  }
  else {
    queue->rear->next = node;
  }
  queue->rear = node;
  queue->count++;
}

//Queue抽出関数
int pop(Queue *queue) {
  if (queue->count == 0) {
    printf("Queue Underflowが発生しました。\n");
    return -INF;
  }
  Node *node = queue->front;
  int data = node->data;
  queue->front = node->next;
  free(node);
  queue->count--;
  return data;
}

//Queue全体の出力関数
void show(Queue *queue) {
  Node *cur = queue->front;
  printf("--- Queueの前 ---\n");
  while (cur != NULL) {
    printf("%d\n", cur->data);
    cur = cur->next;
  }
  printf("--- Queueの後ろ ---\n");
}

//完成したQueueを使用する
int main(void) {
  Queue queue;
  queue.front = queue.rear = NULL;
  queue.count = 0;
  push(&queue, 7);
  push(&queue, 5);
  push(&queue, 4);
  pop(&queue);
  push(&queue, 6);
  pop(&queue);
  show(&queue);
  system("pause");
  return 0;
}

🤔 결과는?result->--- Queueの前 ---
4
6
--- Queueの後ろ ---
요약
👌 Queue는 배열 또는 연결 목록을 사용하여 구현할 수 있습니다.

📚 참고 강의: 컴퓨터 공학 전공 필수 올인원 패키지 Online
👆 위의 강의는 C와 C++ 언어를 전제로 설명합니다.