Rust로 짜본 간단한 Stack

🦀 Rust 소모임
1

사실, 간단하다 못해 민망합니다. 왜냐하면 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());
}
4개의 좋아요
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이겠군요;

1개의 좋아요
3

얼마전 @dimohy 뵙고 의욕생겨서 해본 ㅎㅎㅎ
Single-Linked 방식으로 만들었습니다.

  • single_side_node.rs
use std::rc::Rc;

#[derive(Clone)]
pub struct SingleSideNode<T>
{
    pub value: T,
    pub next_node: NextNode<T>,
}

pub enum NextNode<T>
{
    Nil,
    Next(Rc<SingleSideNode<T>>),
}

impl<T> Clone for NextNode<T> {
    fn clone(&self) -> Self {
        match self {
            NextNode::Nil => NextNode::Nil,
            NextNode::Next(n) => NextNode::Next(n.clone())
        }
    }
}

impl<T> SingleSideNode<T>
{
    pub fn new(x: Option<T>, next: NextNode<T>) -> SingleSideNode<T> {
        {
            return SingleSideNode
            {
                value: match x {
                    Some(v) => v,
                    None => panic!("Cannot create a node with a None value"),
                },
                next_node: match next {
                    NextNode::Nil => { NextNode::Nil }
                    NextNode::Next(n) => NextNode::Next(n)
                },
            };
        }
    }
}
  • my_stack.rs
use std::rc::Rc;
use crate::single_side_node::{NextNode, SingleSideNode};

pub struct Stack<T>
where T: Clone
{
   pub count: i64,
   last: Option<Rc<SingleSideNode<T>>>,
}

impl<'a, T> Stack<T>
where
    T: Clone + 'a,
{
    pub fn new() -> Stack<T>
    {
        Stack {
            count: 0,
            last: None
        }
    }

    pub fn push(&mut self, value: T)
    {
        self.count += 1;
        let mut new_node = SingleSideNode::new(Some(value), NextNode::Nil);

        match &self.last {
            None => {
                self.last = Some(Rc::new(new_node));
            }
            Some(node) => {
                new_node.next_node = NextNode::Next(node.clone());

                let strong = Rc::new(new_node);
                self.last = Some(strong);
            }
        }
    }

    pub fn pop(&mut self) -> Option<T>
    {
        match &self.last {
            None => None,
            Some(node) => {
                let node = node.clone();
                let value = node.value.clone();
                self.last = match &node.next_node {
                    NextNode::Next(n) => Some(n.clone()),
                    NextNode::Nil => None,
                };
                self.count -= 1;
                Some(value)
            }
        }
    }
}
  • main.rs
mod my_stack;
mod single_side_node;
mod single_linked_list;

fn main() {
    println!("Hello, world!");

    let mut st : my_stack::Stack<i32> = my_stack::Stack::new();
    st.push(1);
    st.push(5);
    st.pop();
    st.push(7);
    st.pop();
    st.push(2);


    println!("{:?}", st.pop());
    println!("{:?}", st.pop());
    println!("{:?}", st.pop());
}

솔직히 잘 되는건지도 잘 모르겠습니다…
틀린 점 보이면 차차 고쳐보려구요…

image
image345×763 26.1 KB

Output을 Option<T>로 했습니다.
pop을 과하게 하면(바닥에서 요청 할 경우) None을 리턴 하게 해뒀어요.

Iterator를 넣어서 들어있는 항목 다 보여주는 것도 하고 싶은데 너무 복잡해져서…

24-07-09 수정

다듬으면서 안 쓰는 부분 정리하고,
컴파일러 빌드로 0 warnings 달성!

image
image1157×95 9.33 KB

메모리 누수 걱정도 해 봤는데, Rc 자체가 어느 정도 잡아주지 않을까 싶네요.
이런 부분은 어떻게 신경 써야 할 지 배울게 많다고 느꼈습니다.

2개의 좋아요