More than 3 years have passed since last update.

データ構造とアルゴリズム Vol.5

Last updated at 2021-04-05Posted at 2021-01-18

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->

4
6
--- Queueの後ろ ---```

# Linked Listを利用したQueueを実現
#### 例）実行するコードの例
```C
//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;
}