Cでのキューの作成

1年 ago

芽依, 雨夜

4 minutes

C言語におけるキューは、基本的にデータ要素を格納して操作するための線形データ構造です。その順序は「先入れ先出し（FIFO）」の順序に従います。

待ち行列では、配列に最初に入れられた要素が最初に配列から取り除かれます。

例えば、バスのチケット予約の窓口を考えてみましょう。ここでは、Cプログラミングのキューの方式が採用されています。チケットは先着順で配布されます。つまり、最初に入ってきた人が最初にチケットをサービスされます。

両端にオープンなキューがあります。一方の端はデータの挿入用、もう一方の端はデータの削除用に提供されています。

キューは、C、Java、Pythonなどのどんなプログラミング言語でも実装可能です。

C言語におけるキューに関連する操作

キューは抽象データ構造であり、データ要素の操作に以下の操作を提供します。

isEmpty(): To check if the queue is empty
isFull(): To check whether the queue is full or not
dequeue(): Removes the element from the frontal side of the queue
enqueue(): It inserts elements to the end of the queue
Front: Pointer element responsible for fetching the first element from the queue
Rear: Pointer element responsible for fetching the last element from the queue

キューデータ構造の動作

キューは、最初に入れた要素から順に処理される仕組みです。最初に入れた要素が、要素のリストから最初に取り出されます。

Front and Rear pointers keep the record of the first and last element in the queue.
At first, we need to initialize the queue by setting Front = -1 and Rear = -1
In order to insert the element (enqueue), we need to check whether the queue is already full i.e. check the condition for Overflow. If the queue is not full, we’ll have to increment the value of the Rear index by 1 and place the element at the position of the Rear pointer variable. When we get to insert the first element in the queue, we need to set the value of Front to 0.
In order to remove the element (dequeue) from the queue, we need to check whether the queue is already empty i.e. check the condition for Underflow. If the queue is not empty, we’ll have to remove and return the element at the position of the Front pointer, and then increment the Front index value by 1. When we get to remove the last element from the queue, we will have to set the values of the Front and Rear index to -1.

C言語におけるキューの実装

Cでのキューは、配列、リスト、構造体などを使用して実装することができます。以下では、Cでの配列を使用したキューの実装例を示します。

「私は猫が好きです。」

#include <stdio.h>
# define SIZE 100
void enqueue();
void dequeue();
void show();
int inp_arr[SIZE];
int Rear = - 1;
int Front = - 1;
main()
{
    int ch;
    while (1)
    {
        printf("1.Enqueue Operation\n");
        printf("2.Dequeue Operation\n");
        printf("3.Display the Queue\n");
        printf("4.Exit\n");
        printf("Enter your choice of operations : ");
        scanf("%d", &ch);
        switch (ch)
        {
            case 1:
            enqueue();
            break;
            case 2:
            dequeue();
            break;
            case 3:
            show();
            break;
            case 4:
            exit(0);
            default:
            printf("Incorrect choice \n");
        } 
    } 
} 
 
void enqueue()
{
    int insert_item;
    if (Rear == SIZE - 1)
       printf("Overflow \n");
    else
    {
        if (Front == - 1)
      
        Front = 0;
        printf("Element to be inserted in the Queue\n : ");
        scanf("%d", &insert_item);
        Rear = Rear + 1;
        inp_arr[Rear] = insert_item;
    }
} 
 
void dequeue()
{
    if (Front == - 1 || Front > Rear)
    {
        printf("Underflow \n");
        return ;
    }
    else
    {
        printf("Element deleted from the Queue: %d\n", inp_arr[Front]);
        Front = Front + 1;
    }
} 
 
void show()
{
    
    if (Front == - 1)
        printf("Empty Queue \n");
    else
    {
        printf("Queue: \n");
        for (int i = Front; i <= Rear; i++)
            printf("%d ", inp_arr[i]);
        printf("\n");
    }
}

出力：

1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations : 1
Element to be inserted in the Queue: 10

1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations : 1
Element to be inserted in the Queue: 20

1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations : 3
Queue: 
10 20 

1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations : 2
Element deleted from the Queue: 10

1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations: 3
Queue: 
20

スタックを利用したキューの実装

スタックデータ構造は、キューの操作を実装するために使用することができます。それらを使用してキューを実装するには、2つのスタックが必要です。以下の例に取り組む前に、スタックの機能を非常によく理解していることを確認してください。

スタックを使用してキューを実装する方法は、次のような方法で行うことができます。

Making the enqueue operation costly
Making the dequeue operation costly

方法1：enqueue操作のコストを高くする方法

同じものを使用してキュー操作を実装するために、S1とS2という2つのスタックを想定しましょう。

If S1 is not empty, push all elements to stack 2 (S2)
In order to perform the enqueue operation, we will assume ‘x’ to be the element to be entered into the queue. We will push ‘x’ back to Stack S1 so it comes up on the top.
Further, push all the elements of stack S2 back to Stack S1

注意：enqueue操作の時間計算量はO(n)になります。

In order to perform dequeue operation, we’ll need to pop an item from the Stack S1 since now the first inserted element is on the top in S1 instead of being at the bottom.

注意: デキュー操作の時間計算量はO(1)となります。

スタックを使用したEnqueueとDequeue操作の時間複雑度を分析すると、Enqueue操作の方がDequeue操作よりもコストが高いことがわかります。

したがって、前述のように、最初に入力されたまたは最も古い要素をスタックS1の一番上に残しておき、Dequeue操作が呼び出されたときに削除されるようにします。

方法2：Dequeue操作をコストのかかるものにする

再び、同じものを使ってキューの操作を実装するために、S1とS2という2つのスタックを仮定しましょう。

In order to implement enqueue operation, we insert the newly entered element at the top of Stack S1. Thus, the time complexity of the Enqueue operation using Stacks becomes O(1).
For the implementation of dequeue operation, it checks for the Underflow condition of Stack S1 and S2. If both the Stacks stands out to be empty, an error would be raised.
If the Stack S2 is empty and S1 is not empty, then all the elements from Stack S1 are moved to Stack S2 and the top element of Stack S2 is popped out and returned out of the Dequeue operation.
Thus, the time complexity of the dequeue operation using Stacks becomes O(n).

キューデータ構造の応用

CPU Scheduling
Disk Scheduling
Asynchronous data transfer between processors such as File IO, etc.
Breadth-First Search Algorithm (BFS)

結論として。

この記事では、キューデータ構造の動作を理解し、またスタックデータ構造を使用したキューの実装についても簡単に触れました。

参考文献 (Sankō bunken)

Queue in C
Queue using Stacks