Rustでスタックとキュー

『アルゴリズムとデータ構造』を Rust で実装してみるシリーズ。9章のスタックとキュー。

Rust のグローバルな変数は、制限が多く使いづらい。

スタックはこんな感じ。

const MAX: usize = 100_000; // スタック配列の最大サイズ

static mut ST: [i32; MAX] = [0; MAX]; // スタックを表す配列
static mut TOP: usize = 0; // スタックの先頭を表す添字

// スタックを初期化する
pub fn init() {
    unsafe {
        TOP = 0; // スタックの添字を初期位置に
    }
}

// スタックが空かどうかを判定する
fn is_empty() -> bool {
    unsafe {
        TOP == 0 // スタックサイズが 0 かどうか
    }
}

// スタックが満杯かどうかを判定する
fn is_full() -> bool {
    unsafe {
        TOP == MAX // スタックサイズが MAX かどうか
    }
}

// push
pub fn push(x: i32) {
    if is_full() {
        println!("error: stack is full.");
        return;
    }
    unsafe {
        ST[TOP] = x; // x を格納して
        TOP += 1; // TOP を進める
    }
}

// pop
pub fn pop() -> i32 {
    if is_empty() {
        println!("error: stack is empty.");
        return -1;
    }
    unsafe {
        TOP -= 1; // TOP をデクリメントして
        return ST[TOP]; // TOP の位置にある要素を返す
    }
}

キューはこんな感じ。

const MAX: usize = 100_000; // キュー配列の最大サイズ

static mut QU: [i32; MAX] = [0; MAX]; // キューを表す配列
static mut TAIL: usize = 0; // キューの要素区間を表す変数
static mut HEAD: usize = 0; // キューの要素区間を表す変数

// キューを初期化する
pub fn init() {
    unsafe {
        TAIL = 0;
        HEAD = 0;
    }
}

// キューが空かどうかを判定する
fn is_empty() -> bool {
    unsafe { HEAD == TAIL }
}

// キューが満杯かどうかを判定する
fn is_full() -> bool {
    unsafe { HEAD == (TAIL + 1) % MAX }
}

// enqueue
pub fn enqueue(x: i32) {
    if is_full() {
        println!("error: queue is full.");
        return;
    }
    unsafe {
        QU[TAIL] = x;
        TAIL += 1;
        if TAIL == MAX {
            TAIL = 0;
        } // リングバッファの終端に来たら 0 に
    }
}

// dequeue
pub fn dequeue() -> i32 {
    if is_empty() {
        println!("error: queue is empty.");
        return -1;
    }
    unsafe {
        let res = QU[HEAD];
        HEAD += 1;
        if HEAD == MAX {
            HEAD = 0;
        } // リングバッファの終端に来たら 0 に
        res
    }
}

GitHub のリポジトリはこちら https://github.com/quantized-cube/book_algorithm_solution_rust