feat: add rust codes for linkedlist_queue

coderonion · coderonion · commit 9371380b3fad · 2023-03-12T21:16:23.000+08:00
diff --git a/rust/Cargo.toml b/rust/Cargo.toml
@@ -54,6 +54,11 @@ path = "chapter_stack_and_queue/stack.rs"
 name = "linkedlist_stack"
 path = "chapter_stack_and_queue/linkedlist_stack.rs"
 
+# Run Command: cargo run --bin linkedlist_queue
+[[bin]]
+name = "linkedlist_queue"
+path = "chapter_stack_and_queue/linkedlist_queue.rs"
+
 # Run Command: cargo run --bin queue
 [[bin]]
 name = "queue"
diff --git a/rust/chapter_stack_and_queue/linkedlist_queue.rs b/rust/chapter_stack_and_queue/linkedlist_queue.rs
@@ -0,0 +1,120 @@
+/*
+ * File: linkedlist_queue.rs
+ * Created Time: 2023-03-11
+ * Author: sjinzh (sjinzh@gmail.com)
+ */
+
+include!("../include/include.rs");
+
+use std::rc::Rc;
+use std::cell::RefCell;
+
+/* 基于链表实现的队列 */
+#[allow(dead_code)]
+pub struct LinkedListQueue<T> {
+    front: Option<Rc<RefCell<ListNode<T>>>>,    // 头结点 front
+    rear: Option<Rc<RefCell<ListNode<T>>>>,     // 尾结点 rear 
+    que_size: usize,                            // 队列的长度
+}
+
+impl<T: Copy> LinkedListQueue<T> {
+    pub fn new() -> Self {
+        Self {
+            front: None,
+            rear: None,
+            que_size: 0, 
+        }
+    }
+
+    /* 获取队列的长度 */
+    pub fn size(&self) -> usize {
+        return self.que_size;
+    }
+
+    /* 判断队列是否为空 */
+    pub fn is_empty(&self) -> bool {
+        return self.size() == 0;
+    }
+
+    /* 入队 */
+    pub fn push(&mut self, num: T) {
+        // 尾结点后添加 num
+        let new_rear = ListNode::new(num);
+        match self.rear.take() {
+            // 如果队列不为空，则将该结点添加到尾结点后
+            Some(old_rear) => {
+                old_rear.borrow_mut().next = Some(new_rear.clone());
+                self.rear = Some(new_rear);
+            }
+            // 如果队列为空，则令头、尾结点都指向该结点
+            None => {
+                self.front = Some(new_rear.clone());
+                self.rear = Some(new_rear);
+            }
+        }
+        self.que_size += 1;
+    }
+
+    /* 出队 */
+    pub fn poll(&mut self) -> Option<T> {
+        self.front.take().map(|old_front| {
+            match old_front.borrow_mut().next.take() {
+                Some(new_front) => {
+                    self.front = Some(new_front);
+                }
+                None => {
+                    self.rear.take();
+                }
+            }
+            self.que_size -= 1;
+            Rc::try_unwrap(old_front).ok().unwrap().into_inner().val
+        })
+    }
+
+    /* 访问队首元素 */
+    pub fn peek(&self) -> Option<&Rc<RefCell<ListNode<T>>>> {
+        self.front.as_ref()
+    }
+
+    /* 将链表转化为 Array 并返回 */
+    pub fn to_array(&self, head: Option<&Rc<RefCell<ListNode<T>>>>) -> Vec<T> {
+        if let Some(node) = head {
+            let mut nums = self.to_array(node.borrow().next.as_ref());
+            nums.insert(0, node.borrow().val);
+            return nums;
+        }
+        return Vec::new();
+    }
+}
+
+/* Driver Code */
+fn main() {
+    /* 初始化队列 */
+    let mut queue = LinkedListQueue::new();
+
+    /* 元素入队 */
+    queue.push(1);
+    queue.push(3);
+    queue.push(2);
+    queue.push(5);
+    queue.push(4);
+    print!("队列 queue = ");
+    print_util::print_array(&queue.to_array(queue.peek()));
+
+    /* 访问队首元素 */
+    let peek = queue.peek().unwrap().borrow().val;
+    print!("\n队首元素 peek = {}", peek);
+
+    /* 元素出队 */
+    let poll = queue.poll().unwrap();
+    print!("\n出队元素 poll = {}，出队后 queue = ", poll);
+    print_util::print_array(&queue.to_array(queue.peek()));
+
+    /* 获取队列的长度 */
+    let size = queue.size();
+    print!("\n队列长度 size = {}", size);
+
+    /* 判断队列是否为空 */
+    let is_empty = queue.is_empty();
+    print!("\n队列是否为空 = {}", is_empty);
+}
diff --git a/zig/chapter_stack_and_queue/linkedlist_queue.zig b/zig/chapter_stack_and_queue/linkedlist_queue.zig
@@ -50,7 +50,7 @@ pub fn LinkedListQueue(comptime T: type) type {
         }  
 
         // 入队
-        pub fn offer(self: *Self, num: T) !void {
+        pub fn push(self: *Self, num: T) !void {
             // 尾结点后添加 num
             var node = try self.mem_allocator.create(inc.ListNode(T));
             node.init(num);
@@ -102,11 +102,11 @@ pub fn main() !void {
     defer queue.deinit();
 
     // 元素入队
-    try queue.offer(1);
-    try queue.offer(3);
-    try queue.offer(2);
-    try queue.offer(5);
-    try queue.offer(4);
+    try queue.push(1);
+    try queue.push(3);
+    try queue.push(2);
+    try queue.push(5);
+    try queue.push(4);
     std.debug.print("队列 queue = ", .{});
     inc.PrintUtil.printArray(i32, try queue.toArray());
 
diff --git a/zig/chapter_stack_and_queue/linkedlist_stack.zig b/zig/chapter_stack_and_queue/linkedlist_stack.zig
@@ -6,7 +6,6 @@ const std = @import("std");
 const inc = @import("include");
 
 // 基于链表实现的栈
-// 编译期泛型
 pub fn LinkedListStack(comptime T: type) type {
     return struct {
         const Self = @This();
