232用栈实现队列

题目类型

栈，队列

思路

用两个栈来实现队列，比如有两个栈 stack1,stack2，

• push方法：直接将元素存放到stack1中；时间复杂度O(1)

• pop方法：如果stack2为空，则将stack1的元素，从栈顶依次弹出压入stack2；然后从stack2 栈顶弹出一个元素，则相当与队列中最早入队列的元素。

  如果stack2不为空，直接弹出stack2栈顶元素即可。最差时间复杂度：O(n)

• peek方法：与pop方法类似，只是最后不弹出，只是返回栈顶元素即可。最差时间复杂度O(n)

• empty方法：判断stack1与stack2是否为空，不为空则返回false；为空返回true。 时间复杂度O(1)

use std::cell::RefCell;

struct MyQueue {
    stack1: RefCell<Vec<i32>>, // 继承可变性
    stack2: RefCell<Vec<i32>>,
}


/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl MyQueue {

    /** Initialize your data structure here. */
    fn new() -> Self {
        return MyQueue{stack1: RefCell::new(vec!()), stack2: RefCell::new(vec!())};
    }

    /** Push element x to the back of queue. */
    fn push(&self, x: i32) {
        self.stack1.borrow_mut().push(x);
        return;
    }

    // 将stack1中的依次pop，并push到stack2中
    fn transfer(&self) {
        let stack2_len = self.stack2.borrow().len();
        if stack2_len == 0 {
            while let Some(val) = self.stack1.borrow_mut().pop() {
                self.stack2.borrow_mut().push(val);
            }
        }
    }

    /** Removes the element from in front of queue and returns that element. */
    fn pop(&self) -> i32 {
        Self::transfer(&self);
        return self.stack2.borrow_mut().pop().unwrap();
    }

    /** Get the front element. */
    fn peek(&self) -> i32 {
        Self::transfer(&self);
        return self.stack2.borrow()[self.stack2.borrow().len()-1];// 返回最后一个元素的内容
    }

    /** Returns whether the queue is empty. */
    fn empty(&self) -> bool {
        if self.stack1.borrow().len() == 0 && self.stack2.borrow().len() == 0 {
            return true;
        }
        return false;
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * let obj = MyQueue::new();
 * obj.push(x);
 * let ret_2: i32 = obj.pop();
 * let ret_3: i32 = obj.peek();
 * let ret_4: bool = obj.empty();
 */

// 测试：lib.rs 将上述方法、MyQueue 用pub修饰
mod impl_queue_with_stack;

#[cfg(test)]
mod tests {
    use crate::impl_queue_with_stack::MyQueue;

    #[test]
    fn test_impl_queue_with_stack() {

        let c = MyQueue::new();
        c.push(1);
        c.push(2);
        assert_eq!(c.peek(), 1);
        assert_eq!(c.pop(), 1);
        assert_eq!(c.empty(), false);
    }
}

Leetcode 结果：

执行用时	内存消耗	语言
0 ms	2.1 MB	Rust

Tips

1. RefCell的使用

2. 数组的truncate方法：截取前面若干个元素

   let mut vec = vec![1, 2, 3, 4, 5];
   vec.truncate(2);
   assert_eq!(vec, [1, 2]);
   

Leetcode中相似的题型

20.有效的括号

155.最小栈