【C言語】第8章第4回：スタックとキューの基本と実装

スタックとキューは、プログラム内でデータを効率的に管理するための重要なデータ構造です。本記事では、これらの仕組みと実装方法を学びます。

0. 記事の概要

この記事を読むメリット

• データ構造の基礎理解：スタックとキューの基本を学べます。
• 実践的なスキル：データ構造を活用してプログラムを効率化できます。
• 応用力の向上：複雑なデータ処理への応用が可能になります。

この記事で学べること

• スタックの基本操作と実装
• キューの基本操作と実装
• これらのデータ構造の応用例

活用のイメージ

スタックやキューは、ブラウザの履歴管理、タスクスケジューリング、データの一時保存など、さまざまな場面で利用されます。

1. スタックの基本

1.1 スタックとは？

スタックは、「後入れ先出し」（LIFO：Last In, First Out）のデータ構造です。

例：スタックに「A, B, C」の順でデータを入れると、最初に取り出されるのは「C」です。

1.2 スタックの基本操作

• Push：データをスタックに追加
• Pop：スタックからデータを削除
• Peek：スタックの最上部のデータを取得

1.3 スタックの実装

#include <stdio.h>
#define MAX 100

typedef struct {
    int data[MAX];
    int top;
} Stack;

// スタックの初期化
void initStack(Stack *stack) {
    stack->top = -1;
}

// Push操作
int push(Stack *stack, int value) {
    if (stack->top == MAX - 1) {
        printf("Stack overflow\n");
        return -1;
    }
    stack->data[++stack->top] = value;
    return 0;
}

// Pop操作
int pop(Stack *stack) {
    if (stack->top == -1) {
        printf("Stack underflow\n");
        return -1;
    }
    return stack->data[stack->top--];
}

// Peek操作
int peek(Stack *stack) {
    if (stack->top == -1) {
        printf("Stack is empty\n");
        return -1;
    }
    return stack->data[stack->top];
}

int main() {
    Stack stack;
    initStack(&stack);

    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);

    printf("Top element: %d\n", peek(&stack));
    printf("Popped element: %d\n", pop(&stack));
    printf("Popped element: %d\n", pop(&stack));

    return 0;
}

動作解説

1. 初期化：initStack()でスタックを初期化します。
2. データ追加：push()でデータをスタックに追加します。
3. データ削除：pop()で最上部のデータを削除します。
4. 確認：peek()でスタックの最上部のデータを確認します。

2. キューの基本

2.1 キューとは？

キューは、「先入れ先出し」（FIFO：First In, First Out）のデータ構造です。

例：キューに「A, B, C」の順でデータを入れると、最初に取り出されるのは「A」です。

2.2 キューの基本操作

• Enqueue：データをキューに追加
• Dequeue：キューからデータを削除
• Front：キューの先頭のデータを取得

2.3 キューの実装

#include <stdio.h>
#define MAX 100

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

// キューの初期化
void initQueue(Queue *queue) {
    queue->front = 0;
    queue->rear = 0;
}

// Enqueue操作
int enqueue(Queue *queue, int value) {
    if ((queue->rear + 1) % MAX == queue->front) {
        printf("Queue is full\n");
        return -1;
    }
    queue->data[queue->rear] = value;
    queue->rear = (queue->rear + 1) % MAX;
    return 0;
}

// Dequeue操作
int dequeue(Queue *queue) {
    if (queue->front == queue->rear) {
        printf("Queue is empty\n");
        return -1;
    }
    int value = queue->data[queue->front];
    queue->front = (queue->front + 1) % MAX;
    return value;
}

// Front操作
int front(Queue *queue) {
    if (queue->front == queue->rear) {
        printf("Queue is empty\n");
        return -1;
    }
    return queue->data[queue->front];
}

int main() {
    Queue queue;
    initQueue(&queue);

    enqueue(&queue, 10);
    enqueue(&queue, 20);
    enqueue(&queue, 30);

    printf("Front element: %d\n", front(&queue));
    printf("Dequeued element: %d\n", dequeue(&queue));
    printf("Dequeued element: %d\n", dequeue(&queue));

    return 0;
}

動作解説

1. 初期化：initQueue()でキューを初期化します。
2. データ追加：enqueue()でデータをキューに追加します。
3. データ削除：dequeue()で先頭のデータを削除します。
4. 確認：front()でキューの先頭のデータを確認します。

3. 練習問題

以下の課題に挑戦して、スタックとキューの理解を深めましょう。

1. キューを改良して、サイズを可変にしてみてください。
2. スタックを使用して、文字列が回文かどうかをチェックするプログラムを作成してください。
3. キューを用いて、タスクの優先度管理を実装してください。

4. 練習問題の解答と解説

問2の解答

#include <stdio.h>
#include <string.h>
#define MAX 100

typedef struct {
    char data[MAX];
    int top;
} Stack;

// スタックの初期化
void initStack(Stack *stack) {
    stack->top = -1;
}

// Push操作
void push(Stack *stack, char value) {
    stack->data[++stack->top] = value;
}

// Pop操作
char pop(Stack *stack) {
    return stack->data[stack->top--];
}

// 回文チェック
int isPalindrome(const char *str) {
    Stack stack;
    initStack(&stack);
    int len = strlen(str);

    for (int i = 0; i < len; i++) {
        push(&stack, str[i]);
    }

    for (int i = 0; i < len; i++) {
        if (str[i] != pop(&stack)) {
            return 0; // 回文ではない
        }
    }

    return 1; // 回文
}

int main() {
    const char *test = "radar";
    if (isPalindrome(test)) {
        printf("\"%s\" is a palindrome.\n", test);
    } else {
        printf("\"%s\" is not a palindrome.\n", test);
    }
    return 0;
}

このプログラムでは、スタックを使用して文字列が回文かどうかをチェックします。

5. まとめ

本記事では、スタックとキューの基本操作と実装方法を学びました。次回は、これらを応用したプログラム設計について解説します。