Struct leetcode_for_rust::cd0232_implement_queue_using_stacks::MyQueue

pub struct MyQueue;

Solutions

Approach 1: Linkedlist

• Time complexity: O(1)

• Space complexity: O(1)

use std::collections::LinkedList;

struct MyQueue {
    queue: LinkedList<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 { queue: LinkedList::new(), };

    }

    /** Push element x to the back of queue. */
    fn push(&mut self, x: i32) {
        self.queue.push_back(x);

    }

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

    /** Get the front element. */
    fn peek(&mut self) -> i32 {
        let n = self.queue.pop_front().unwrap();
        self.queue.push_front(n);
        return n;
    }

    /** Returns whether the queue is empty. */
    fn empty(&self) -> bool {
        return self.queue.is_empty();
    }
}
/**
 * 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();
 */

Approach 2: Stack

• Time complexity: O(n)

• Space complexity: O(n)

#[derive(Default)]
struct MyQueue {
    stack: Vec<i32>,
    queue: 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 {
        Default::default()
    }

    /** Push element x to the back of queue. */
    fn push(&mut self, x: i32) {
        while let Some(q) = self.queue.pop() { self.stack.push(q); }
        self.stack.push(x);
        while let Some(s) = self.stack.pop() { self.queue.push(s); }
    }

    /** Removes the element from in front of queue and returns that element. */
    fn pop(&mut self) -> i32 {
        self.queue.pop().unwrap()
    }

    /** Get the front element. */
    fn peek(&self) -> i32 {
        *self.queue.last().unwrap()
    }

    /** Returns whether the queue is empty. */
    fn empty(&self) -> bool {
        self.queue.is_empty()
    }
}

/**
 * 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();
 */