struct MyQueue {
    in_stack: Vec<i32>,
    out_stack: Vec<i32>,
}


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

    fn new() -> Self {
        Self {
            in_stack: vec![],
            out_stack: vec![]
        }
    }
    
    fn push(&mut self, x: i32) {
        self.in_stack.push(x);
    }
    
    fn pop(&mut self) -> i32 {
        if let Some(out) = self.out_stack.pop() {
            out
        } else {
            loop {
                if let Some(in_) = self.in_stack.pop() {
                    self.out_stack.push(in_);
                } else {
                    return self.out_stack.pop().unwrap();
                }
            }
        }
    }
    
    fn peek(&mut self) -> i32 {
        if let Some(out) = self.out_stack.last() {
            *out
        } else {
            let mut out = 0;
            loop {
                if let Some(s) = self.in_stack.pop() {
                    out = s;
                    self.out_stack.push(s);
                } else {
                    return out;
                }
            }
        }
    }
    
    fn empty(&self) -> bool {
        self.in_stack.is_empty() && self.out_stack.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();
 */

struct MyStack {
    queue: Vec<i32>,
}

impl MyStack {
    fn new() -> Self {
        MyStack { queue: vec![] }
    }

    fn push(&mut self, x: i32) {
        self.queue.push(x);
    }

    fn pop(&mut self) -> i32 {
        let len = self.queue.len() - 1;
        for _ in 0..len {
            let tmp = self.queue.remove(0);
            self.queue.push(tmp);
        }
        self.queue.remove(0)
    }

    fn top(&mut self) -> i32 {
        let res = self.pop();
        self.queue.push(res);
        res
    }

    fn empty(&self) -> bool {
        self.queue.is_empty()
    }
}

impl Solution {
    pub fn is_valid(s: String) -> bool {
        if s.len() % 2 != 0 {
            return false;
        }
        
        let mut stack = Vec::new();
        
        for c in s.chars() {
            match c {
                '(' | '[' | '{' => stack.push(c), // 左括号入栈
                ')' => if stack.pop() != Some('(') { return false; },
                ']' => if stack.pop() != Some('[') { return false; },
                '}' => if stack.pop() != Some('{') { return false; },
                _ => return false, // 非法字符
            }
        }
        
        stack.is_empty() // 确保栈为空（所有左括号已匹配）
    }
}

impl Solution {
    pub fn remove_duplicates(s: String) -> String {
        let mut stack = Vec::new();

        for c in s.chars() {
            match stack.last() {
                Some(&top) if top == c => {
                    stack.pop();
                }
                _ => {
                    stack.push(c);
                }
            }
        }

        stack.into_iter().collect()
    }
}

impl Solution {
    pub fn eval_rpn(tokens: Vec<String>) -> i32 {
        let mut stack = Vec::new();

        for i in tokens {
            if let Ok(num) = i.parse::<i32>() {
                stack.push(num); // 数字直接入栈
            } else {
                // 如果是运算符，弹出两个操作数
                let b = stack.pop().unwrap();
                let a = stack.pop().unwrap();
                let res = match i.as_str() {
                    "+" => a + b,
                    "-" => a - b,
                    "*" => a * b,
                    "/" => a / b,
                    _ => unreachable!(), // 题目保证输入合法，不会执行到这里
                };
                stack.push(res);
            }
        }

        stack.pop().unwrap()
    }
}

use std::collections::VecDeque;

impl Solution {
    pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let k = k as usize;
        let mut res = Vec::new();
        let mut queue = VecDeque::new();
        
        for (i, &v) in nums.iter().enumerate() {
            // 移除队列中不在当前窗口的元素
            while let Some(&front) = queue.front() {
                if front + k <= i {
                    queue.pop_front();
                } else {
                    break;
                }
            }
            // 移除队列尾部比当前元素小的元素
            while let Some(&back) = queue.back() {
                if nums[back] <= v {
                    queue.pop_back();
                } else {
                    break;
                }
            }
            // 将当前索引加入队列
            queue.push_back(i);
            // 当窗口形成时，记录当前窗口的最大值
            if i >= k - 1 {
                res.push(nums[*queue.front().unwrap()]);
            }
        }
        res
    }
}

use std::collections::{ HashMap, BinaryHeap };
use std::cmp::Reverse;

impl Solution {
    pub fn top_k_frequent(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let mut count = HashMap::new();

        nums.into_iter().for_each(|v| {
            *count.entry(v).or_insert(0) += 1;
        });

        let k = k as usize;
        let mut pq = BinaryHeap::new(); 
        count.into_iter().for_each(|(key, value)| {
            pq.push((Reverse(value), key));
            if pq.len() > k {
                pq.pop();
            }
        });

        pq.into_iter().map(|(_, num)| num).collect()
    }
}