使用栈实现队列的下列操作：
. push(x) – 将一个元素放入队列的尾部。
. pop() – 从队列首部移除元素。
. peek() – 返回队列首部的元素。
. empty() – 返回队列是否为空。
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
题型归类: Vec, Linked-list
使用MyQueue这个struct, 构造一个序列的操作，可以直接使用vec来实现，push可以直接使用，pop有不一样，区别就是vec的pop是弹出末尾的元素，这里要求弹出头元素, 我们可以使用vec的remove方法来替代； peek方法没有，需要自己实现；empty方法直接有is_empty方法了。
// 代码实现
struct MyQueue {
stack:Vec<i32>
}
impl MyQueue {
fn new() -> Self {
MyQueue {
stack: Vec::new()
}
}
fn push(&mut self, v:i32) {
&self.stack.push(v);
}
fn pop(&mut self) -> i32 {
self.stack.remove(0)
}
fn peek(&self) -> i32 {
self.stack[0]
}
fn empty(&self) -> bool {
self.stack.is_empty()
}
}
#[cfg(test)]
mod test {
use crate::MyQueue;
pub fn my_queue_test() {
let mut queue = MyQueue::new();
queue.push(1);
queue.push(2);
assert_eq!(vec![1,2], queue.stack);
assert_eq!(1, queue.peek());
assert_eq!(2, queue.pop());
assert_eq!(false, queue.empty());
assert_eq!(vec![2], queue.stack);
}
}
执行用时 : 0 ms , 在所有 Rust 提交中击败了 100.00% 的用户
内存消耗 : 2.1 MB , 在所有 Rust 提交中击败了 100.00% 的用户
这个题就是一个简单的队列实现，没有涉及什么算法，就是需要对vec熟悉。我们可以试一试自己用一个struct来实现一个队列，并实现这些方法。
使用struct 和Linked-list链表来实现。每次push相当于往末端节点增加，pop就弹出头部节点，更新链表为去掉头部的链表。为了性能，不使用循环去查找节点，我们需要记录链表的尾节点，有length属性，记录链表的长度。因为在链表中，我们每个节点会同时被next和tail持有，所有需要用Rc智能指针，然后用RefCell来修改。
// 代码实现
use std::rc::Rc;
use std::cell::RefCell;
#[derive(Debug)]
struct Node {
val: i32,
next: Rc<RefCell<Option<Node>>>,
}
#[derive(Debug)]
pub struct MyQueue {
length: i32,
list: Rc<RefCell<Option<Node>>>,
tail: Rc<RefCell<Option<Node>>>,
}
impl MyQueue {
pub fn new() -> Self {
// 新建一个空列表
let node = Rc::new(RefCell::new(None));
MyQueue {
length: 0,
list: node.clone(),
tail: node.clone(),
}
}
pub fn push(&mut self, v: i32) {
// 将一个元素放入队列的尾部
let tail = Rc::new(RefCell::new(None));
let node = Node {
val: v,
next: tail.clone(),
};
// 更新最后一个节点的值
*self.tail.borrow_mut() = Some(node);
// 更新tail指针，指向新的尾节点
self.tail = tail;
self.length += 1;
}
pub fn peek(&self) -> i32 {
// 返回队列首部的元素
match &*self.list.borrow() {
Some(node) => node.val,
None => panic!("empty list")
}
}
pub fn pop(&mut self) -> i32 {
// 从队列首部移除元素
let mut next;
let v = match &*self.list.borrow() {
Some(node) => {
let v = node.val;
next = node.next.clone();
v
}
None => panic!("empty list")
};
self.list = next;
self.length -= 1;
v
}
pub fn empty(&self) -> bool {
// 返回队列是否为空
if self.length == 0 {
true
} else {
false
}
}
}
#[cfg(test)]
mod test {
use crate::MyQueue;
#[test]
pub fn queue_test() {
let mut queue = MyQueue::new();
queue.push(1);
queue.push(2);
assert_eq!(1, queue.peek());
assert_eq!(1, queue.pop());
assert_eq!(false, queue.empty());
assert_eq!(2, queue.pop());
assert_eq!(true, queue.empty());
}
}
执行用时 : 0 ms , 在所有 Rust 提交中击败了 100.00% 的用户
内存消耗 : 2.1 MB , 在所有 Rust 提交中击败了 100.00% 的用户
思路二的一开始的困惑点是，没有重新更新tail指针，所以tail指针一直指向原来的位置，所有每次borrow_mut更新值后，一直值原地更新，绕了好久才绕明白了，原来是我需要用新的tail值来更新原来的tail值，虽然两个都是Rc::New(RefCell::new(None)), 但是内存地址，是不一样的。
思路一和思路二都对题目的意思理解错误了，用栈实现队列操作，栈操作就只有push和pop两个操作，我们要仅用栈的push和pop两个操作，实现题目要求的 push, pop, peek, empty 方法。
// 代码实现
#[derive(Debug)]
struct MyQueue {
stack: Vec<i32>
}
impl MyQueue {
fn new() -> Self {
MyQueue {
stack: Vec::new()
}
}
fn trans(vec1: &mut Vec<i32>, vec2: &mut Vec<i32>) {
// 把vec1中的数据 reverse 后， 放入vec2中
while let Some(i) = vec1.pop() {
vec2.push(i);
}
}
fn push(&mut self, v: i32) {
let mut x = vec![];
MyQueue::trans(&mut self.stack, &mut x);
// 恢复为正常排序后，在末尾push入元素
x.push(v);
// 把x 的数据倒序装入stack中
MyQueue::trans(&mut x, &mut self.stack);
}
fn pop(&mut self) -> i32 {
self.stack.pop().expect("empty stack now")
}
fn peek(&mut self) -> i32 {
let i = self.stack.pop().expect("empty stack now");
self.stack.push(i);
i
}
fn empty(&mut self) -> bool {
match self.stack.pop() {
Some(v) => {
self.stack.push(v);
false
}
None => true
}
}
}
#[cfg(test)]
mod test {
use crate::MyQueue;
#[test]
fn myqueue_test() {
let mut v = MyQueue::new();
v.push(1);
v.push(2);
assert_eq!(1, v.peek());
assert_eq!(1, v.pop());
assert_eq!(false, v.empty());
assert_eq!(vec![2], v.stack);
}
}
执行用时 : 0 ms , 在所有 Rust 提交中击败了 100.00% 的用户
内存消耗 : 2 MB , 在所有 Rust 提交中击败了 100.00% 的用户
2019-09-10 14:05