1.2.3. スタックとキュー

1. 概要

　データ構造は、データを効率的に管理・操作するための仕組みであり、情報処理における基盤となる重要な概念です。その中でも「スタックとキュー」は最も基本的なデータ構造の一つで、多くのプログラミング言語やシステム設計において利用されています。

　スタックは「後入れ先出し（LIFO: Last-In-First-Out）」、キューは「先入れ先出し（FIFO: First-In-First-Out）」という異なるデータ処理方式を持ち、それぞれの特性に応じた場面で活用されています。これらのデータ構造を理解することは、効率的なアルゴリズム設計やプログラム実装において不可欠な知識となります。

2. 詳細説明

2.1. スタック（Stack）

　スタックは、LIFO（Last-In-First-Out：後入れ先出し）の原則に従うデータ構造です。これは、最後に追加された要素が最初に取り出されるという特性を持ちます。実生活では、積み重ねられた皿の山を想像するとわかりやすいでしょう。新しい皿は一番上に置かれ、取るときも一番上から取り出します。

図1: スタックの動作図

2.1.1. スタックの基本操作

1. プッシュ（Push）: スタックの一番上に新しい要素を追加する操作
2. ポップ（Pop）: スタックの一番上から要素を取り出す操作
3. ピーク（Peek）: スタックの一番上の要素を参照するが取り出さない操作

2.1.2. スタックの実装例（疑似コード）

// スタックの基本実装 class Stack { private items = []

// プッシュ操作
push(element) {
    this.items.push(element)
}

// ポップ操作
pop() {
    if (this.isEmpty()) 
        return "スタックが空です"
    return this.items.pop()
}

// ピーク操作
peek() {
    if (this.isEmpty())
        return "スタックが空です"
    return this.items\[this.items.length - 1\]
}

// スタックが空かどうかの確認
isEmpty() {
    return this.items.length == 0
}

}

// スタックの基本実装
class Stack {
    private items = []
    
    // プッシュ操作
    push(element) {
        this.items.push(element)
    }
    
    // ポップ操作
    pop() {
        if (this.isEmpty()) 
            return "スタックが空です"
        return this.items.pop()
    }
    
    // ピーク操作
    peek() {
        if (this.isEmpty())
            return "スタックが空です"
        return this.items[this.items.length - 1]
    }
    
    // スタックが空かどうかの確認
    isEmpty() {
        return this.items.length == 0
    }
}

2.1.3. Java言語でのスタック実装例

import java.util.ArrayList;

public class Stack { private ArrayList items = new ArrayList<>();

// プッシュ操作
public void push(T element) {
    items.add(element);
}

// ポップ操作
public T pop() {
    if (isEmpty()) {
        throw new IllegalStateException("スタックが空です");
    }
    return items.remove(items.size() - 1);
}

// ピーク操作
public T peek() {
    if (isEmpty()) {
        throw new IllegalStateException("スタックが空です");
    }
    return items.get(items.size() - 1);
}

// スタックが空かどうかの確認
public boolean isEmpty() {
    return items.isEmpty();
}

// スタックのサイズ取得
public int size() {
    return items.size();
}

}

import java.util.ArrayList;

public class Stack<T> {
    private ArrayList<T> items = new ArrayList<>();
    
    // プッシュ操作
    public void push(T element) {
        items.add(element);
    }
    
    // ポップ操作
    public T pop() {
        if (isEmpty()) {
            throw new IllegalStateException("スタックが空です");
        }
        return items.remove(items.size() - 1);
    }
    
    // ピーク操作
    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("スタックが空です");
        }
        return items.get(items.size() - 1);
    }
    
    // スタックが空かどうかの確認
    public boolean isEmpty() {
        return items.isEmpty();
    }
    
    // スタックのサイズ取得
    public int size() {
        return items.size();
    }
}

2.2. キュー（Queue）

　キューは、FIFO（First-In-First-Out：先入れ先出し）の原則に従うデータ構造です。これは、最初に追加された要素が最初に取り出されるという特性を持ちます。実生活では、レジに並ぶ人の列をイメージするとわかりやすいでしょう。列に加わる人は後ろに並び、処理されるのは前から順番です。

図2: キューの動作図

2.2.1. キューの基本操作

1. エンキュー（Enqueue）: キューの末尾に新しい要素を追加する操作
2. デキュー（Dequeue）: キューの先頭から要素を取り出す操作
3. フロント（Front）: キューの先頭要素を参照するが取り出さない操作

2.2.2. キューの実装例（疑似コード）

// キューの基本実装 class Queue { private items = []

// エンキュー操作
enqueue(element) {
    this.items.push(element)
}

// デキュー操作
dequeue() {
    if (this.isEmpty()) 
        return "キューが空です"
    return this.items.shift()
}

// フロント操作
front() {
    if (this.isEmpty())
        return "キューが空です"
    return this.items\[0\]
}

// キューが空かどうかの確認
isEmpty() {
    return this.items.length == 0
}

}

// キューの基本実装
class Queue {
    private items = []
    
    // エンキュー操作
    enqueue(element) {
        this.items.push(element)
    }
    
    // デキュー操作
    dequeue() {
        if (this.isEmpty()) 
            return "キューが空です"
        return this.items.shift()
    }
    
    // フロント操作
    front() {
        if (this.isEmpty())
            return "キューが空です"
        return this.items[0]
    }
    
    // キューが空かどうかの確認
    isEmpty() {
        return this.items.length == 0
    }
}

2.2.3. Python言語でのキュー実装例

from collections import deque

class Queue: def __init__(self): self.items = deque()

# エンキュー操作
def enqueue(self, element):
    self.items.append(element)
    
# デキュー操作
def dequeue(self):
    if self.is\_empty():
        raise IndexError("キューが空です")
    return self.items.popleft()
    
# フロント操作
def front(self):
    if self.is\_empty():
        raise IndexError("キューが空です")
    return self.items\[0\]
    
# キューが空かどうかの確認
def is\_empty(self):
    return len(self.items) == 0
    
# キューのサイズ取得
def size(self):
    return len(self.items)

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()
        
    # エンキュー操作
    def enqueue(self, element):
        self.items.append(element)
        
    # デキュー操作
    def dequeue(self):
        if self.is_empty():
            raise IndexError("キューが空です")
        return self.items.popleft()
        
    # フロント操作
    def front(self):
        if self.is_empty():
            raise IndexError("キューが空です")
        return self.items[0]
        
    # キューが空かどうかの確認
    def is_empty(self):
        return len(self.items) == 0
        
    # キューのサイズ取得
    def size(self):
        return len(self.items)

データ構造	操作	時間計算量	説明
スタック	プッシュ (Push)	O(1)	スタックの一番上に要素を追加
ポップ (Pop)	O(1)	スタックの一番上から要素を取り出し
ピーク (Peek)	O(1)	スタックの一番上の要素を参照
キュー	エンキュー (Enqueue)	O(1)	キューの末尾に要素を追加
デキュー (Dequeue)	O(1)	キューの先頭から要素を取り出し
フロント (Front)	O(1)	キューの先頭の要素を参照

表1: スタックとキューの基本操作と計算量

3. 応用例

3.1. スタックの応用例

1. 関数呼び出し管理: プログラム実行時の関数呼び出しとリターンはスタックで管理されます。
2. 式の評価: 数式の括弧のバランス確認や後置記法（逆ポーランド記法）の評価にスタックが使われます。
3. バックトラッキング: ゲームやパズルの解法でバックトラッキングが必要な場合、状態をスタックに保存します。
4. ウェブブラウザの「戻る」ボタン: 訪問したページの履歴をスタックで管理します。

図3: 関数呼び出しスタックの例

3.2. キューの応用例

1. プリントジョブの管理: プリンターに送られる印刷ジョブは、キューによって順番に処理されます。
2. CPUタスクスケジューリング: オペレーティングシステムではプロセスの実行順序をキューで管理します。
3. 幅優先探索（BFS）: グラフやツリーの探索アルゴリズムでは、訪問すべき頂点をキューで管理します。
4. バッファリング: データの送受信時に一時的にデータを蓄えるバッファはキューとして実装されます。

図4: 幅優先探索（BFS）におけるキューの利用例

4. 例題

例題1: スタックの操作

　以下のスタック操作の結果を示してください。スタックは初期状態で空です。

1. プッシュ(5)
2. プッシュ(3)
3. ポップ()
4. プッシュ(7)
5. プッシュ(2)
6. ポップ()
7. ポップ()
8. プッシュ(9)
9. プッシュ(1)
10. ポップ()
11. プッシュ(8)
12. ポップ()
13. ポップ()

解答例

操作ごとのスタックの状態変化は以下の通りです：

1. プッシュ(5): [5]
2. プッシュ(3): [5, 3]
3. ポップ(): 3を取り出し、スタックは[5]
4. プッシュ(7): [5, 7]
5. プッシュ(2): [5, 7, 2]
6. ポップ(): 2を取り出し、スタックは[5, 7]
7. ポップ(): 7を取り出し、スタックは[5]
8. プッシュ(9): [5, 9]
9. プッシュ(1): [5, 9, 1]
10. ポップ(): 1を取り出し、スタックは[5, 9]
11. プッシュ(8): [5, 9, 8]
12. ポップ(): 8を取り出し、スタックは[5, 9]
13. ポップ(): 9を取り出し、スタックは[5]

最終的なスタックの状態: [5]

例題2: キューの操作

　以下のキュー操作の結果を示してください。キューは初期状態で空です。

1. エンキュー(10)
2. エンキュー(20)
3. デキュー()
4. エンキュー(30)
5. エンキュー(40)
6. デキュー()
7. エンキュー(50)
8. デキュー()
9. デキュー()

解答例

操作ごとのキューの状態変化は以下の通りです：

1. エンキュー(10): [10]
2. エンキュー(20): [10, 20]
3. デキュー(): 10を取り出し、キューは[20]
4. エンキュー(30): [20, 30]
5. エンキュー(40): [20, 30, 40]
6. デキュー(): 20を取り出し、キューは[30, 40]
7. エンキュー(50): [30, 40, 50]
8. デキュー(): 30を取り出し、キューは[40, 50]
9. デキュー(): 40を取り出し、キューは[50]

最終的なキューの状態: [50]

例題3: スタックとキューの応用

　ある文字列が回文（前から読んでも後ろから読んでも同じ）かどうかを判定するプログラムをスタックとキューを使って設計してください。

解答例

スタックとキューを組み合わせることで、回文判定を効率的に行うことができます。

function isPalindrome(str) { // 文字列から空白と特殊文字を除去し、小文字に変換 str = str.toLowerCase().replace(/[^a-z0-9]/g, ”)

let stack = new Stack()
let queue = new Queue()

// 文字列の各文字をスタックとキューに追加
for (let i = 0; i < str.length; i++) {
    stack.push(str\[i\])
    queue.enqueue(str\[i\])
}

// スタックとキューから文字を取り出して比較
while (!stack.isEmpty()) {
    if (stack.pop() !== queue.dequeue()) {
        return false  // 異なる文字があれば回文ではない
    }
}

return true  // すべての文字が一致すれば回文

}

function isPalindrome(str) {
    // 文字列から空白と特殊文字を除去し、小文字に変換
    str = str.toLowerCase().replace(/[^a-z0-9]/g, '')
    
    let stack = new Stack()
    let queue = new Queue()
    
    // 文字列の各文字をスタックとキューに追加
    for (let i = 0; i < str.length; i++) {
        stack.push(str[i])
        queue.enqueue(str[i])
    }
    
    // スタックとキューから文字を取り出して比較
    while (!stack.isEmpty()) {
        if (stack.pop() !== queue.dequeue()) {
            return false  // 異なる文字があれば回文ではない
        }
    }
    
    return true  // すべての文字が一致すれば回文
}

このアルゴリズムの考え方：

• キューからは先頭（文字列の最初）から文字を取り出す（FIFO）
• スタックからは末尾（文字列の最後）から文字を取り出す（LIFO）
• 回文であれば、これらの文字は常に一致するはずです

例題4: 応用情報技術者試験形式問題

　あるプログラムで以下のデータ構造と操作が定義されている。この操作を順に実行した後の結果として、正しいものを選びなさい。

// データ構造の定義 class DataStructure { private items = []

// 操作A
operationA(element) {
    this.items.push(element)
}

// 操作B
operationB() {
    if (this.items.length == 0) 
        return null
    return this.items.shift()
}

// 現在の状態を取得
getState() {
    return this.items.slice()
}

}

// データ構造の定義
class DataStructure {
    private items = []
    
    // 操作A
    operationA(element) {
        this.items.push(element)
    }
    
    // 操作B
    operationB() {
        if (this.items.length == 0) 
            return null
        return this.items.shift()
    }
    
    // 現在の状態を取得
    getState() {
        return this.items.slice()
    }
}

操作:

1. 操作A(1)
2. 操作A(2)
3. 操作A(3)
4. 操作B()
5. 操作A(4)
6. 操作B()
7. 操作A(5)

選択肢:

1. [3, 4, 5]
2. [3, 5]
3. 1, 2, 3]
4. [5, 4, 3]

解答例

• 操作A: items.push(element) – 要素を配列の末尾に追加（スタックのプッシュまたはキューのエンキュー）
• 操作B: items.shift() – 配列の先頭から要素を削除して返す（キューのデキューに相当）

このデータ構造はキューとして機能していることがわかります。

操作の実行過程:

1. 操作A(1): [1]
2. 操作A(2): [1, 2]
3. 操作A(3): [1, 2, 3]
4. 操作B(): 1を取り出し、[2, 3]
5. 操作A(4): [2, 3, 4]
6. 操作B(): 2を取り出し、[3, 4]
7. 操作A(5): [3, 4, 5]

したがって、最終的な状態は [3, 4, 5] となり、正解は a. です。

この問題では、FIFOの特性（キュー）を持つデータ構造かLIFOの特性（スタック）を持つデータ構造かを判断し、それに基づいて操作の結果を追跡する能力が試されています。

5. まとめ

　スタックとキューは、コンピュータサイエンスにおける基本的なデータ構造です。スタックはLIFO（後入れ先出し）の原則に従い、主にプッシュとポップの操作によって要素の追加と削除を行います。一方、キューはFIFO（先入れ先出し）の原則に従い、エンキューとデキューの操作を通じてデータを管理します。

　これらのデータ構造は、関数呼び出し、式の評価、タスク管理、探索アルゴリズムなど、プログラミングのさまざまな場面で活用されています。スタックとキューの基本概念を理解し、それぞれの特性に応じた適切な使い分けができることは、効率的なプログラミングにおいて非常に重要です。

　応用情報技術者試験では、これらのデータ構造の基本的な性質や操作を理解し、適切な応用場面を判断できる能力が求められます。実際のプログラム実装においても、言語が提供するスタックやキューの機能を活用することで、より効率的で読みやすいコードを書くことができるでしょう。

5.1 試験対策のポイント

1. 基本操作の理解: スタックのプッシュ/ポップ、キューのエンキュー/デキューの違いを明確に理解する
2. 計算量の把握: 各操作の時間計算量（O(1)など）を理解する
3. 特徴的な応用例: スタックは深さ優先探索、キューは幅優先探索に用いられることを覚えておく
4. 実装方法: 配列やリンクドリストでの実装方法の違いを理解する
5. 言語標準ライブラリの把握: 主要プログラミング言語におけるスタックとキューの実装方法を知っておく