【データ構造】キューとスタックの基本解説

2025/01/13

キューとスタックの基礎知識

このページでは、キューとスタックという基本的なデータ構造について解説します。

キュー (Queue)

キューは「先入れ先出し (FIFO: First-In-First-Out)」のデータ構造です。コンビニのレジ待ちの列や、バスの乗車列などがキューの概念に近いです。

列に並んだ順番に、先頭から順に処理されるのが特徴です。

主な操作

enqueue (追加): キューの末尾に要素を追加します。
dequeue (取り出し): キューの先頭から要素を取り出します。

キューの用途には、ジョブスケジューリングやネットワークパケットの処理、幅優先探索 (BFS) などがあります。

以下に C 言語を用いた基本的なキューの実装例を示します。

#include <stdio.h>
#include <stdlib.h>
#define MAX 100
 
typedef struct {
    int data[MAX];
    int front;
    int rear;
} Queue;
 
// キューの初期化
void initQueue(Queue *q) {
    q->front = 0;
    q->rear = 0;
}
 
// enqueue: 要素を追加
void enqueue(Queue *q, int value) {
    if ((q->rear + 1) % MAX == q->front) {
        printf("Queue is full!\n");
        return;
    }
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % MAX;
}
 
// dequeue: 要素を取り出し
int dequeue(Queue *q) {
    if (q->front == q->rear) {
        printf("Queue is empty!\n");
        return -1;
    }
    int value = q->data[q->front];
    q->front = (q->front + 1) % MAX;
    return value;
}
 
// メイン関数例
int main() {
    Queue q;
    initQueue(&q);
    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
 
    printf("Dequeue: %d\n", dequeue(&q)); // 10
    printf("Dequeue: %d\n", dequeue(&q)); // 20
    return 0;
}

スタック (Stack)

スタックは「後入れ先出し (LIFO: Last-In-First-Out)」のデータ構造です。本の山やお皿の積み重ねがスタックの概念に近い例です。

最後に追加された要素から取り出されるのが特徴です。

主な操作

push (追加): スタックの上に要素を追加します。
pop (取り出し): スタックの上から要素を取り出します。

スタックの用途には、関数呼び出しの管理や深さ優先探索 (DFS)、逆ポーランド記法の計算などがあります。

スタックはこのように PC やプログラムのメモリ管理等に使われていて、たまに耳にするであろうスタックオーバーフローなどは、スタックの性質を理解することでなぜ起こるかが理解できます。

その性質を利用するとセキュリティの脆弱性を突くことができ、その逆の防御もすることができるのでセキュリティの観点からも重要なデータ構造です。

以下に C 言語を用いた基本的なスタックの実装例を示します。

 
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
 
typedef struct {
    int data[MAX];
    int top;
} Stack;
 
// スタックの初期化
void initStack(Stack *s) {
    s->top = -1;
}
 
// push: 要素を追加
void push(Stack *s, int value) {
    if (s->top >= MAX - 1) {
        printf("Stack is full!\n");
        return;
    }
    s->data[++(s->top)] = value;
}
 
// pop: 要素を取り出し
int pop(Stack *s) {
    if (s->top < 0) {
        printf("Stack is empty!\n");
        return -1;
    }
    return s->data[(s->top)--];
}
 
// メイン関数例
int main() {
    Stack s;
    initStack(&s);
    push(&s, 10);
    push(&s, 20);
    push(&s, 30);
 
    printf("Pop: %d\n", pop(&s)); // 30
    printf("Pop: %d\n", pop(&s)); // 20
    return 0;
}

キューとスタックの違い

特徴	キュー	スタック
データ処理順序	先入れ先出し (FIFO)	後入れ先出し (LIFO)
主な操作	enqueue, dequeue	push, pop
主な用途	ジョブキュー、BFS など	関数呼び出し管理、DFS など