Rust로 짜본 간단한 Stack

사실, 간단하다 못해 민망합니다. 왜냐하면 Rust에서 제공하는 Vec이 이미 큐를 지원하고 있고 그것을 단지 이용했을 뿐이니까요.

Rust는 엄격한 소유권 정책이 있어서 아직 까지 Stack를 직접 구현하는 것이 힘듭니다; 그리고 아직 힙을 이용하기 위해 필요한 Box를 배우지 않았습니다! 그래서 일단 이 정도로;;

pub struct Stack<T> {
    list: Vec<T>,
}

impl<T> Stack<T> {
    pub fn new() -> Queue<T> {
        Stack{ list: Vec::new() }
    }

    pub fn push(&mut self, value: T) {
        self.list.push(value);
    }

    pub fn pop(&mut self) -> T {
        self.list.pop().unwrap()
    }
}

fn main() {
    let mut stack = Stack::<i32>::new();

    stack.push(312);
    stack.push(789);

    println!("{}", stack.pop());
    println!("{}", stack.pop());
}
좋아요 2

두가지 버젼의 Stack을 구현해봤습니다.

| 첫번쨰 버젼

enum StackNode<T> {
    Node(T, Box<StackNode<T>>),
    Nil,
}

struct Stack<T> {
    count: i32,
    last: StackNode<T>,
}

impl<'a, T> Stack<T> {
    pub fn new() -> Stack<T> {
        Stack {
            count: 0,
            last: StackNode::Nil,
        }
    }

    pub fn push(&mut self, v: T) {
        // 이것 찾느라 엄청 오래 걸렸음. 이 방법 말고 다른 방법은 없을까?
        let tmp = mem::replace(&mut self.last, StackNode::Nil);
        self.last = StackNode::Node(v, Box::new(tmp));
        self.count += 1;
    }

    pub fn pop(&mut self) -> Option<T> {
        if self.count == 0 {
            return None;
        }

        self.count -= 1;

        let tmp = mem::replace(&mut self.last, StackNode::Nil);
        if let StackNode::Node(v, next) = tmp {
            self.last = *next;

            Some(v)
        } else {
            None
        }
    }

    pub fn count(&self) -> i32 {
        self.count
    }
}

| 두번쨰 버젼

struct StackNode<T> {
    data: T,
    next: Option<Box<StackNode<T>>>,
}

struct Stack<T> {
    count: i32,
    last: Option<Box<StackNode<T>>>,
}

impl<T> Stack<T> {
    fn new() -> Stack<T> {
        Stack {
            count: 0,
            last: None,
        }
    }

    fn push(&mut self, v: T) {
        self.last = Some(Box::new(StackNode {
            data: v,
            next: self.last.take(),
        }));

        self.count += 1;
    }

    fn pop(&mut self) -> Option<T> {
        self.count -= 1;

        match self.last.take() {
            None => None,
            Some(mut v) => {
                self.last = v.next.take();
                Some(v.data)
            }
        }
    }

    fn count(&self) -> i32 {
        self.count
    }
}

fn main() {
    let mut s = Stack::new();

    println!("In 1");
    s.push(1);
    println!("In 2");
    s.push(2);
    println!("In 3");
    s.push(3);
    println!("In 4");
    s.push(4);
    println!("In 5");
    s.push(5);

    println!("Count = {}", s.count());

    println!("Out {:?}", s.pop().unwrap());
    println!("Out {:?}", s.pop().unwrap());
    println!("Out {:?}", s.pop().unwrap());
    println!("Out {:?}", s.pop().unwrap());
    println!("Out {:?}", s.pop().unwrap());

    println!("Count = {}", s.count());
}

Vec으로 짠 처음 코드를 다시 봤더니… Queue가 아니라 Stack이겠군요;