灯的个人博客

forever young,forever weeping.

0%

230323-用两个栈实现队列

发表于 更新于 分类于

用两个栈实现队列

题目

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

示例 1：

输入：
[“CQueue”,”appendTail”,”deleteHead”,”deleteHead”,”deleteHead”]
[[],[3],[],[],[]]
输出：[null,null,3,-1,-1]
示例 2：

输入：
[“CQueue”,”deleteHead”,”appendTail”,”appendTail”,”deleteHead”,”deleteHead”]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]
提示：

1 <= values <= 10000
最多会对 appendTail、deleteHead 进行 10000 次调用

题解

原生方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
use std::collections::VecDeque;

struct CQueue {
    stack: VecDeque<i32>,
}

impl CQueue {
    fn new() -> Self {
        CQueue {
            stack: VecDeque::new(),
        }
    }

    fn append_tail(&mut self, value: i32) {
        self.stack.push_front(value);
    }

    fn delete_head(&mut self) -> i32 {
        let v = self.stack.pop_back();
        match v {
            Some(v) => v,
            None => -1,
        }
    }
}

双 vec

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#[derive(Default)]
struct CQueue {
    stack1: Vec<i32>,
    stack2: Vec<i32>,
}

impl CQueue {
    fn new() -> Self {
        Self::default()
    }

    fn append_tail(&mut self, value: i32) {
        self.stack1.push(value);
    }

    fn delete_head(&mut self) -> i32 {
        if let Some(i) = self.stack2.pop() {
            return i;
        };
        while let Some(i) = self.stack1.pop() {
            self.stack2.push(i);
        }
        self.stack2.pop().unwrap_or(-1)
    }
}

思路

  • 第一反应是找原生队列支持，确实有，引入标准库就可以了。
  • 做完后发现跟题目不太符合，需要用两个栈来实现队列的功能。
  • 栈是先进后出，队列是先进先出
  • 原生 vec 可以实现栈的功能，pus- pop。
  • 把出栈的内容 push 到第二个 vec 里面，然后 在第二 vec pop 出来，就实现了类似队列的功能
  • 比如 stack1.push(1),stack1.push(2), stack1 = [1,2]; stack2 = [];
  • stakc2.push(stack1.pop()),stack1 = [1];stack2= [2]
  • stakc2.push(stack1.pop()),stack1 = [];stack2= [2,1]
  • stack2.pop(),stack1 = [];stack2= [2],返回值 1
  • stack2.pop(),stack1 = [];stack2= [],返回值 2

来源