사실, 간단하다 못해 민망합니다. 왜냐하면 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이겠군요;