データ構造の基礎：配列、リンクリスト、スタック、キューの実装

配列（シーケンシャルリスト）

配列は連続したメモリ領域にデータを格納するデータ構造です。C言語環境では、名前付きのスタック配列または匿名のヒープ配列として実装できます。

配列の設計

配列を操作しやすくするために、専用の「管理構造体」が必要です。この構造体には通常以下の要素が含まれます：

配列の総容量
現在の最後の要素のインデックス位置
配列へのポインタ

配列の練習問題

キーボードから数字入力を受け取り、正の整数を昇順で配列に挿入し、負の整数が入力されたらその絶対値に対応するデータを削除するプログラムを作成します。各入力後、配列の内容を画面に表示します。

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

typedef int DataType;

typedef struct {
    DataType last;      // 最後の要素のインデックス
    DataType *elements; // 配列データ
    DataType capacity;  // 配列の容量
} Array;

// 配列の初期化
Array* initializeArray(int capacity) {
    Array *arr = malloc(sizeof(Array));
    if (arr == NULL) return NULL;
    
    arr->capacity = capacity;
    arr->last = -1;
    arr->elements = malloc(capacity * sizeof(DataType));
    
    if (arr->elements == NULL) {
        free(arr);
        return NULL;
    }
    
    return arr;
}

// 配列が満杯かどうかをチェック
bool isFull(Array *arr) {
    return arr->capacity == arr->last + 1;
}

// データを挿入
bool insertData(Array *arr, int data) {
    if (arr == NULL) return false;
    
    if (isFull(arr)) return false;
    
    arr->elements[++arr->last] = data;
    return true;
}

// 配列が空かどうかをチェック
bool isEmpty(Array *arr) {
    return arr->last == -1;
}

// 配列を表示
void displayArray(Array *arr) {
    if (isEmpty(arr)) return;
    
    for (int i = 0; i <= arr->last; i++) {
        printf("%d\t", arr->elements[i]);
    }
    printf("\n");
}

// 配列から要素を削除
void removeData(Array *arr, int value) {
    if (isEmpty(arr)) return;
    
    for (int i = 0; i <= arr->last; i++) {
        if (arr->elements[i] == value) {
            for (int j = i; j < arr->last; j++) {
                arr->elements[j] = arr->elements[j + 1];
            }
            arr->last--;
            i--; // 削除後の要素をチェック
        }
    }
}

// 配列を破棄
void destroyArray(Array *arr) {
    free(arr->elements);
    arr->elements = NULL;
    free(arr);
    arr = NULL;
}

int main() {
    int capacity;
    printf("配列の容量を入力してください: ");
    scanf("%d", &capacity);
    
    Array *arr = initializeArray(capacity);
    
    int input[5];
    printf("5つの要素を入力してください: ");
    for (int i = 0; i < 5; i++) {
        scanf("%d", &input[i]);
    }
    
    // 入力された要素をソート
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4 - i; j++) {
            if (input[j] > input[j + 1]) {
                int temp = input[j];
                input[j] = input[j + 1];
                input[j + 1] = temp;
            }
        }
    }
    
    // 要素を挿入
    for (int i = 0; i < 5; i++) {
        insertData(arr, input[i]);
    }
    
    // 配列を表示
    printf("現在の配列: ");
    displayArray(arr);
    
    // 要素を削除
    int value;
    printf("削除する要素の値を入力してください: ");
    scanf("%d", &value);
    removeData(arr, value);
    
    // 配列を表示
    printf("削除後の配列: ");
    displayArray(arr);
    
    // 配列を破棄
    destroyArray(arr);
    
    return 0;
}

配列の利点と欠点

利点：
- データ間の関係を記録する余分な情報が不要で、ストレージ密度が高い
- すべてのデータが連続したメモリに格納され、任意のデータに即時アクセスが可能（例：配列のi番目の要素はarr->elements[i]）
欠点：
- 挿入や削除時にデータの物理的な位置を維持する必要があり、データの移動が発生する
- 多数のデータノードの場合、大きな連続メモリ領域が必要
- データノード数が激しく変動する場合、メモリの解放と割り当てが柔軟でない

リンクリスト

リンクリストは、ポインタによる接続関係で構成される線形データ構造です。各構造体変数をノードと呼び、データ領域とポインタ領域の2つのメンバから成ります。ポインタ領域は次のノードのアドレスを格納するために使用されます。

リンクリストの基本操作

ノードの設計
空のリンクリストの初期化
ノードの追加と削除
リンクリストの走査
リンクリストの破棄

単方向リンクリスト

ヘッダなしの単方向リンクリスト

// ノードの定義
struct Node {
    int data;           // データ領域
    struct Node *next;  // 次のノードへのポインタ
};

// 新しいノードの作成
Node* createNode(int data) {
    Node *newNode = malloc(sizeof(Node));
    if (newNode == NULL) return NULL;
    
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// リンクリストの作成
Node* createList() {
    Node *head = NULL;
    Node *tail = NULL;
    int data;
    
    while (1) {
        printf("データを入力（0で終了）: ");
        scanf("%d", &data);
        
        if (data == 0) break;
        
        Node *newNode = createNode(data);
        if (newNode == NULL) return NULL;
        
        if (head == NULL) {
            head = tail = newNode;
        } else {
            newNode->next = head;
            head = newNode;
        }
    }
    
    return head;
}

// ノードの更新
Node* updateNode(Node *head, int oldValue, int newValue) {
    Node *current = head;
    
    while (current != NULL) {
        if (current->data == oldValue) {
            current->data = newValue;
        }
        current = current->next;
    }
    
    return head;
}

// ノードの挿入
Node* insertNode(Node *head, int targetValue, int newValue) {
    Node *current = head;
    Node *previous = NULL;
    
    while (current != NULL) {
        if (current->data == targetValue) {
            Node *newNode = createNode(newValue);
            if (newNode == NULL) return head;
            
            newNode->next = current->next;
            current->next = newNode;
            return head;
        }
        previous = current;
        current = current->next;
    }
    
    return head;
}

// ノードの削除
Node* deleteNode(Node *head, int value) {
    Node *current = head;
    Node *previous = NULL;
    
    while (current != NULL) {
        if (current->data == value) {
            if (previous == NULL) {
                head = current->next;
            } else {
                previous->next = current->next;
            }
            free(current);
            return head;
        }
        previous = current;
        current = current->next;
    }
    
    return head;
}

// リンクリストの表示
void displayList(Node *head) {
    Node *current = head;
    
    while (current != NULL) {
        printf("%d\t", current->data);
        current = current->next;
    }
    printf("\n");
}

// リンクリストの破棄
void destroyList(Node *head) {
    Node *current = head;
    Node *next;
    
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
}

int main() {
    // リンクリストの作成
    Node *head = createList();
    
    // ノードの更新
    head = updateNode(head, 4, 44);
    printf("更新後のリスト: ");
    displayList(head);
    
    // ノードの挿入
    head = insertNode(head, 44, 55);
    printf("挿入後のリスト: ");
    displayList(head);
    
    // ノードの削除
    head = deleteNode(head, 1);
    printf("削除後のリスト: ");
    displayList(head);
    
    // リンクリストの破棄
    destroyList(head);
    
    return 0;
}

ヘッダ付きの単方向リンクリスト

// データノードの定義
typedef struct DataNode {
    int data;
    struct DataNode *next;
} DataNode;

// ヘッダノードの定義
typedef struct Header {
    DataNode *first;
    DataNode *last;
    int count;
} Header;

// ヘッダの初期化
Header* initializeHeader() {
    Header *header = malloc(sizeof(Header));
    if (header == NULL) return NULL;
    
    header->first = NULL;
    header->last = NULL;
    header->count = 0;
    
    return header;
}

// 新しいデータノードの作成
DataNode* createDataNode(int data) {
    DataNode *newNode = malloc(sizeof(DataNode));
    if (newNode == NULL) return NULL;
    
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 末尾にノードを追加
void appendNode(Header *header, DataNode *node) {
    if (header->first == NULL) {
        header->first = header->last = node;
    } else {
        header->last->next = node;
        header->last = node;
    }
    header->count++;
}

// リンクリストの作成
Header* createLinkedList() {
    Header *header = initializeHeader();
    int data;
    
    while (1) {
        printf("データを入力（0で終了）: ");
        scanf("%d", &data);
        
        if (data == 0) break;
        
        DataNode *newNode = createDataNode(data);
        if (newNode == NULL) return NULL;
        
        appendNode(header, newNode);
    }
    
    return header;
}

// ノードの更新
Header* updateLinkedListNode(Header *header, int oldValue, int newValue) {
    DataNode *current = header->first;
    
    while (current != NULL) {
        if (current->data == oldValue) {
            current->data = newValue;
        }
        current = current->next;
    }
    
    return header;
}

// ノードの挿入
Header* insertLinkedListNode(Header *header, int targetValue, int newValue) {
    DataNode *current = header->first;
    DataNode *previous = NULL;
    
    while (current != NULL) {
        if (current->data == targetValue) {
            DataNode *newNode = createDataNode(newValue);
            if (newNode == NULL) return header;
            
            newNode->next = current->next;
            current->next = newNode;
            header->count++;
            return header;
        }
        previous = current;
        current = current->next;
    }
    
    return header;
}

// ノードの削除
Header* deleteLinkedListNode(Header *header, int value) {
    DataNode *current = header->first;
    DataNode *previous = NULL;
    
    while (current != NULL) {
        if (current->data == value) {
            if (previous == NULL) {
                header->first = current->next;
            } else {
                previous->next = current->next;
            }
            
            if (current == header->last) {
                header->last = previous;
            }
            
            free(current);
            header->count--;
            return header;
        }
        previous = current;
        current = current->next;
    }
    
    return header;
}

// リンクリストの表示
void displayLinkedList(Header *header) {
    DataNode *current = header->first;
    
    while (current != NULL) {
        printf("%d\t", current->data);
        current = current->next;
    }
    printf("\n");
}

// リンクリストの破棄
void destroyLinkedList(Header *header) {
    DataNode *current = header->first;
    DataNode *next;
    
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
    
    free(header);
}

int main() {
    // リンクリストの作成
    Header *header = createLinkedList();
    
    // リンクリストの表示
    printf("元のリスト: ");
    displayLinkedList(header);
    
    // ノードの更新
    int oldVal, newVal;
    printf("更新する値と新しい値を入力: ");
    scanf("%d %d", &oldVal, &newVal);
    header = updateLinkedListNode(header, oldVal, newVal);
    printf("更新後のリスト: ");
    displayLinkedList(header);
    
    // ノードの挿入
    printf("挿入する位置の値と新しい値を入力: ");
    scanf("%d %d", &oldVal, &newVal);
    header = insertLinkedListNode(header, oldVal, newVal);
    printf("挿入後のリスト: ");
    displayLinkedList(header);
    
    // ノードの削除
    printf("削除する値を入力: ");
    scanf("%d", &oldVal);
    header = deleteLinkedListNode(header, oldVal);
    printf("削除後のリスト: ");
    displayLinkedList(header);
    
    // リンクリストの破棄
    destroyLinkedList(header);
    
    return 0;
}

双方向リンクリスト

// データノードの定義
typedef struct DoubleNode {
    int data;
    struct DoubleNode *prev;
    struct DoubleNode *next;
} DoubleNode;

// ヘッダノードの定義
typedef struct DoubleHeader {
    DoubleNode *first;
    DoubleNode *last;
    int count;
} DoubleHeader;

// ヘッダの初期化
DoubleHeader* initializeDoubleHeader() {
    DoubleHeader *header = malloc(sizeof(DoubleHeader));
    if (header == NULL) return NULL;
    
    header->first = NULL;
    header->last = NULL;
    header->count = 0;
    
    return header;
}

// 新しいデータノードの作成
DoubleNode* createDoubleNode(int data) {
    DoubleNode *newNode = malloc(sizeof(DoubleNode));
    if (newNode == NULL) return NULL;
    
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// 末尾にノードを追加
void appendDoubleNode(DoubleHeader *header, DoubleNode *node) {
    if (header->first == NULL) {
        header->first = header->last = node;
    } else {
        header->last->next = node;
        node->prev = header->last;
        header->last = node;
    }
    header->count++;
}

// リンクリストの作成
DoubleHeader* createDoubleLinkedList() {
    DoubleHeader *header = initializeDoubleHeader();
    int data;
    
    while (1) {
        printf("データを入力（0で終了）: ");
        scanf("%d", &data);
        
        if (data == 0) break;
        
        DoubleNode *newNode = createDoubleNode(data);
        if (newNode == NULL) return NULL;
        
        appendDoubleNode(header, newNode);
    }
    
    return header;
}

// ノードの更新
DoubleHeader* updateDoubleNode(DoubleHeader *header, int oldValue, int newValue) {
    DoubleNode *current = header->first;
    
    while (current != NULL) {
        if (current->data == oldValue) {
            current->data = newValue;
        }
        current = current->next;
    }
    
    return header;
}

// ノードの挿入
DoubleHeader* insertDoubleNode(DoubleHeader *header, int targetValue, int newValue) {
    DoubleNode *current = header->first;
    
    while (current != NULL) {
        if (current->data == targetValue) {
            DoubleNode *newNode = createDoubleNode(newValue);
            if (newNode == NULL) return header;
            
            newNode->next = current->next;
            newNode->prev = current;
            
            if (current->next != NULL) {
                current->next->prev = newNode;
            }
            
            current->next = newNode;
            header->count++;
            return header;
        }
        current = current->next;
    }
    
    return header;
}

// ノードの削除
DoubleHeader* deleteDoubleNode(DoubleHeader *header, int value) {
    DoubleNode *current = header->first;
    
    while (current != NULL) {
        if (current->data == value) {
            if (current->prev != NULL) {
                current->prev->next = current->next;
            } else {
                header->first = current->next;
            }
            
            if (current->next != NULL) {
                current->next->prev = current->prev;
            } else {
                header->last = current->prev;
            }
            
            free(current);
            header->count--;
            return header;
        }
        current = current->next;
    }
    
    return header;
}

// リンクリストの表示
void displayDoubleLinkedList(DoubleHeader *header) {
    DoubleNode *current = header->first;
    
    while (current != NULL) {
        printf("%d\t", current->data);
        current = current->next;
    }
    printf("\n");
}

// リンクリストの破棄
void destroyDoubleLinkedList(DoubleHeader *header) {
    DoubleNode *current = header->first;
    DoubleNode *next;
    
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
    
    free(header);
}

int main() {
    // 双方向リンクリストの作成
    DoubleHeader *header = createDoubleLinkedList();
    
    // リンクリストの表示
    printf("元のリスト: ");
    displayDoubleLinkedList(header);
    
    // ノードの更新
    int oldVal, newVal;
    printf("更新する値と新しい値を入力: ");
    scanf("%d %d", &oldVal, &newVal);
    header = updateDoubleNode(header, oldVal, newVal);
    printf("更新後のリスト: ");
    displayDoubleLinkedList(header);
    
    // ノードの挿入
    printf("挿入する位置の値と新しい値を入力: ");
    scanf("%d %d", &oldVal, &newVal);
    header = insertDoubleNode(header, oldVal, newVal);
    printf("挿入後のリスト: ");
    displayDoubleLinkedList(header);
    
    // ノードの削除
    printf("削除する値を入力: ");
    scanf("%d", &oldVal);
    header = deleteDoubleNode(header, oldVal);
    printf("削除後のリスト: ");
    displayDoubleLinkedList(header);
    
    // リンクリストの破棄
    destroyDoubleLinkedList(header);
    
    return 0;
}

双方向循環リンクリスト

// データノードの定義
typedef struct CircularNode {
    int data;
    struct CircularNode *prev;
    struct CircularNode *next;
} CircularNode;

// ヘッダノードの定義
typedef struct CircularHeader {
    CircularNode *first;
    int count;
} CircularHeader;

// ヘッダの初期化
CircularHeader* initializeCircularHeader() {
    CircularHeader *header = malloc(sizeof(CircularHeader));
    if (header == NULL) return NULL;
    
    header->first = NULL;
    header->count = 0;
    
    return header;
}

// 新しいデータノードの作成
CircularNode* createCircularNode(int data) {
    CircularNode *newNode = malloc(sizeof(CircularNode));
    if (newNode == NULL) return NULL;
    
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// 末尾にノードを追加
void appendCircularNode(CircularHeader *header, CircularNode *node) {
    if (header->first == NULL) {
        header->first = node;
        node->next = node;
        node->prev = node;
    } else {
        CircularNode *last = header->first->prev;
        last->next = node;
        node->prev = last;
        node->next = header->first;
        header->first->prev = node;
    }
    header->count++;
}

// リンクリストの作成
CircularHeader* createCircularLinkedList() {
    CircularHeader *header = initializeCircularHeader();
    int data;
    
    while (1) {
        printf("データを入力（0で終了）: ");
        scanf("%d", &data);
        
        if (data == 0) break;
        
        CircularNode *newNode = createCircularNode(data);
        if (newNode == NULL) return NULL;
        
        appendCircularNode(header, newNode);
    }
    
    return header;
}

// リンクリストが循環しているかチェック
bool isCircular(CircularHeader *header) {
    if (header->first == NULL) return false;
    
    CircularNode *slow = header->first;
    CircularNode *fast = header->first->next;
    
    while (fast != NULL && fast->next != NULL) {
        if (slow == fast) return true;
        
        slow = slow->next;
        fast = fast->next->next;
    }
    
    return false;
}

// 2つのリンクリストをマージ
CircularHeader* mergeCircularLists(CircularHeader *list1, CircularHeader *list2) {
    if (list1->first == NULL) return list2;
    if (list2->first == NULL) return list1;
    
    CircularNode *last1 = list1->first->prev;
    CircularNode *last2 = list2->first->prev;
    
    last1->next = list2->first;
    list2->first->prev = last1;
    
    last2->next = list1->first;
    list1->first->prev = last2;
    
    list1->count += list2->count;
    free(list2);
    
    return list1;
}

// リンクリストの表示
void displayCircularLinkedList(CircularHeader *header) {
    if (header->first == NULL) return;
    
    CircularNode *current = header->first;
    int count = 0;
    
    do {
        printf("%d\t", current->data);
        current = current->next;
        count++;
    } while (current != header->first && count < header->count);
    
    printf("\n");
}

// リンクリストの破棄
void destroyCircularLinkedList(CircularHeader *header) {
    if (header->first == NULL) return;
    
    CircularNode *current = header->first;
    CircularNode *next;
    
    for (int i = 0; i < header->count; i++) {
        next = current->next;
        free(current);
        current = next;
    }
    
    free(header);
}

int main() {
    // 双方向循環リンクリストの作成
    CircularHeader *header1 = createCircularLinkedList();
    CircularHeader *header2 = createCircularLinkedList();
    
    // リンクリストの表示
    printf("リスト1: ");
    displayCircularLinkedList(header1);
    printf("リスト2: ");
    displayCircularLinkedList(header2);
    
    // リンクリストのマージ
    header1 = mergeCircularLists(header1, header2);
    printf("マージ後のリスト: ");
    displayCircularLinkedList(header1);
    
    // 循環チェック
    printf("循環しているか: %s\n", isCircular(header1) ? "はい" : "いいえ");
    
    // リンクリストの破棄
    destroyCircularLinkedList(header1);
    
    return 0;
}

スタック

スタックは特殊な線形データ構造で、固定された一端でのみ操作が可能です。この特性により「後入れ先出し」（LIFO）の論理が現れます。

順序スタック

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

typedef int DataType;

// スタックの定義
typedef struct {
    DataType *elements; // スタック要素
    int capacity;       // スタックの容量
    int top;            // スタックトップのインデックス
} Stack;

// スタックの初期化
Stack* initializeStack(int capacity) {
    Stack *stack = malloc(sizeof(Stack));
    if (stack == NULL) return NULL;
    
    stack->elements = malloc(capacity * sizeof(DataType));
    if (stack->elements == NULL) {
        free(stack);
        return NULL;
    }
    
    stack->capacity = capacity;
    stack->top = -1;
    
    return stack;
}

// スタックが満杯かチェック
bool isStackFull(Stack *stack) {
    return stack->top == stack->capacity - 1;
}

// スタックが空かチェック
bool isStackEmpty(Stack *stack) {
    return stack->top == -1;
}

// スタックにプッシュ
bool push(Stack *stack, DataType data) {
    if (isStackFull(stack)) return false;
    
    stack->elements[++stack->top] = data;
    return true;
}

// スタックからポップ
bool pop(Stack *stack, DataType *data) {
    if (isStackEmpty(stack)) return false;
    
    *data = stack->elements[stack->top--];
    return true;
}

// スタックの表示
void displayStack(Stack *stack) {
    for (int i = 0; i <= stack->top; i++) {
        printf("%d\t", stack->elements[i]);
    }
    printf("\n");
}

int main() {
    int capacity;
    printf("スタックの容量を入力: ");
    scanf("%d", &capacity);
    
    Stack *stack = initializeStack(capacity);
    
    printf("データを入力（数字でプッシュ、文字でポップ）: ");
    
    while (1) {
        int input;
        if (scanf("%d", &input)) {
            // 数字の入力：プッシュ
            if (!push(stack, input)) {
                printf("スタックが満杯です\n");
            }
            displayStack(stack);
        } else {
            // 文字の入力：ポップ
            DataType popped;
            if (!pop(stack, &popped)) {
                printf("スタックが空です\n");
            } else {
                printf("ポップした値: %d\n", popped);
                displayStack(stack);
            }
            // 入力バッファをクリア
            while (getchar() != '\n');
        }
    }
    
    return 0;
}

リンクリストスタック

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

typedef int DataType;

// スタックノードの定義
typedef struct StackNode {
    DataType data;
    struct StackNode *next;
} StackNode;

// リンクリストスタックの定義
typedef struct {
    StackNode *top; // スタックトップ
    int size;       // スタックサイズ
} LinkedListStack;

// スタックの初期化
LinkedListStack* initializeLinkedListStack() {
    LinkedListStack *stack = malloc(sizeof(LinkedListStack));
    if (stack == NULL) return NULL;
    
    stack->top = NULL;
    stack->size = 0;
    
    return stack;
}

// スタックが空かチェック
bool isLinkedListStackEmpty(LinkedListStack *stack) {
    return stack->size == 0;
}

// スタックにプッシュ
bool pushLinkedListStack(LinkedListStack *stack, DataType data) {
    StackNode *newNode = malloc(sizeof(StackNode));
    if (newNode == NULL) return false;
    
    newNode->data = data;
    newNode->next = stack->top;
    stack->top = newNode;
    stack->size++;
    
    return true;
}

// スタックからポップ
bool popLinkedListStack(LinkedListStack *stack, DataType *data) {
    if (isLinkedListStackEmpty(stack)) return false;
    
    StackNode *temp = stack->top;
    *data = temp->data;
    stack->top = temp->next;
    free(temp);
    stack->size--;
    
    return true;
}

// スタックの表示
void displayLinkedListStack(LinkedListStack *stack) {
    StackNode *current = stack->top;
    
    while (current != NULL) {
        printf("%d", current->data);
        current = current->next;
    }
    printf("\n");
}

// 10進数を8進数に変換
void decimalToOctal(int decimal) {
    LinkedListStack *stack = initializeLinkedListStack();
    
    while (decimal > 0) {
        int remainder = decimal % 8;
        pushLinkedListStack(stack, remainder);
        decimal /= 8;
    }
    
    printf("8進数: ");
    displayLinkedListStack(stack);
    
    // スタックの破棄
    while (!isLinkedListStackEmpty(stack)) {
        DataType dummy;
        popLinkedListStack(stack, &dummy);
    }
    free(stack);
}

int main() {
    int decimal;
    printf("10進数を入力: ");
    scanf("%d", &decimal);
    
    decimalToOctal(decimal);
    
    return 0;
}

キュー

キューは固定された両端でのみ操作が可能な特殊な線形データ構造です。この特性により「先入れ先出し」（FIFO）の論理が現れます。

循環キュー

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

typedef int DataType;

// キューの定義
typedef struct {
    DataType *elements; // キュー要素
    int front;         // フロントインデックス
    int rear;          // リアインデックス
    int capacity;      // キューの容量
} Queue;

// キューの初期化
Queue* initializeQueue(int capacity) {
    Queue *queue = malloc(sizeof(Queue));
    if (queue == NULL) return NULL;
    
    queue->elements = malloc(capacity * sizeof(DataType));
    if (queue->elements == NULL) {
        free(queue);
        return NULL;
    }
    
    queue->capacity = capacity;
    queue->front = 0;
    queue->rear = 0;
    
    return queue;
}

// キューが空かチェック
bool isQueueEmpty(Queue *queue) {
    return queue->front == queue->rear;
}

// キューが満杯かチェック
bool isQueueFull(Queue *queue) {
    return (queue->rear + 1) % queue->capacity == queue->front;
}

// キューにエンキュー
bool enqueue(Queue *queue, DataType data) {
    if (isQueueFull(queue)) return false;
    
    queue->elements[queue->rear] = data;
    queue->rear = (queue->rear + 1) % queue->capacity;
    
    return true;
}

// キューからデキュー
bool dequeue(Queue *queue, DataType *data) {
    if (isQueueEmpty(queue)) return false;
    
    *data = queue->elements[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    
    return true;
}

// キューの表示
void displayQueue(Queue *queue) {
    if (isQueueEmpty(queue)) {
        printf("キューは空です\n");
        return;
    }
    
    int i = queue->front;
    while (i != queue->rear) {
        printf("%d\t", queue->elements[i]);
        i = (i + 1) % queue->capacity;
    }
    printf("\n");
}

int main() {
    int capacity;
    printf("キューの容量を入力: ");
    scanf("%d", &capacity);
    
    Queue *queue = initializeQueue(capacity);
    
    printf("データを入力（数字でエンキュー、文字でデキュー）: ");
    
    while (1) {
        int input;
        if (scanf("%d", &input)) {
            // 数字の入力：エンキュー
            if (!enqueue(queue, input)) {
                printf("キューが満杯です\n");
            }
            displayQueue(queue);
        } else {
            // 文字の入力：デキュー
            DataType dequeued;
            if (!dequeue(queue, &dequeued)) {
                printf("キューが空です\n");
            } else {
                printf("デキューした値: %d\n", dequeued);
                displayQueue(queue);
            }
            // 入力バッファをクリア
            while (getchar() != '\n');
        }
    }
    
    return 0;
}

リンクリストキュー

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

typedef int DataType;

// キューノードの定義
typedef struct QueueNode {
    DataType data;
    struct QueueNode *next;
} QueueNode;

// リンクリストキューの定義
typedef struct {
    QueueNode *front; // フロントポインタ
    QueueNode *rear;  // リアポインタ
    int size;        // キューサイズ
} LinkedListQueue;

// キューの初期化
LinkedListQueue* initializeLinkedListQueue() {
    LinkedListQueue *queue = malloc(sizeof(LinkedListQueue));
    if (queue == NULL) return NULL;
    
    queue->front = NULL;
    queue->rear = NULL;
    queue->size = 0;
    
    return queue;
}

// キューが空かチェック
bool isLinkedListQueueEmpty(LinkedListQueue *queue) {
    return queue->size == 0;
}

// キューにエンキュー
bool enqueueLinkedListQueue(LinkedListQueue *queue, DataType data) {
    QueueNode *newNode = malloc(sizeof(QueueNode));
    if (newNode == NULL) return false;
    
    newNode->data = data;
    newNode->next = NULL;
    
    if (isLinkedListQueueEmpty(queue)) {
        queue->front = queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
    
    queue->size++;
    return true;
}

// キューからデキュー
bool dequeueLinkedListQueue(LinkedListQueue *queue, DataType *data) {
    if (isLinkedListQueueEmpty(queue)) return false;
    
    QueueNode *temp = queue->front;
    *data = temp->data;
    
    if (queue->size == 1) {
        queue->front = queue->rear = NULL;
    } else {
        queue->front = temp->next;
    }
    
    free(temp);
    queue->size--;
    
    return true;
}

// キューの表示
void displayLinkedListQueue(LinkedListQueue *queue) {
    if (isLinkedListQueueEmpty(queue)) {
        printf("キューは空です\n");
        return;
    }
    
    QueueNode *current = queue->front;
    
    while (current != NULL) {
        printf("%d\t", current->data);
        current = current->next;
    }
    printf("\n");
}

int main() {
    LinkedListQueue *queue = initializeLinkedListQueue();
    
    printf("データを入力（数字でエンキュー、文字でデキュー）: ");
    
    while (1) {
        int input;
        if (scanf("%d", &input)) {
            // 数字の入力：エンキュー
            if (!enqueueLinkedListQueue(queue, input)) {
                printf("メモリ不足\n");
            }
            displayLinkedListQueue(queue);
        } else {
            // 文字の入力：デキュー
            DataType dequeued;
            if (!dequeueLinkedListQueue(queue, &dequeued)) {
                printf("キューが空です\n");
            } else {
                printf("デキューした値: %d\n", dequeued);
                displayLinkedListQueue(queue);
            }
            // 入力バッファをクリア
            while (getchar() != '\n');
        }
    }
    
    return 0;
}

タグ: データ構造 C言語配列リンクリストスタック

5月24日 03:40 投稿

異端開発室