剑指offer 面试题09. 用两个栈实现队列（易）

栈和队列有何特点？如何通过画图，将抽象问题形式化？

栈和队列有何特点？

栈：先进后出；队列：先进先出。

如何通过画图，将抽象问题形象化？

参考题解的两幅图片

Tag

栈和队列

题目

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

1
2
3
4
5
6
7
8
9
10
11
12
class CQueue:

    def __init__(self):

    def appendTail(self, value: int) -> None:

    def deleteHead(self) -> int:

# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()
示例 1： 
1
2
3
4
输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]
解释 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入：
["CQueue","appendTail","deleteHead","deleteHead"] 
这一行表示每一行代码的操作
[[],[3],[],[]]
这个表示每一行代码操作后对应的结果

举例：
CQueue 表示新建一个CQueue对象，对应的结果为[]。
appendTail 表示执行一个appendTail()操作，对应要被操作的元素为3
deleteHead 表示执行一个deleteHead操作，对应的结果为[]
deleteHead 表示执行一个deleteHead操作，对应的结果为[]

以上的输入其实是一个代码执行的步骤描述与其对应结果或操作。
并不是说，上面的“输入”表示的输入程序验证的数据。
示例 2：

1
2
3
4
输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

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

直觉

设置两个栈 Stack1 和 Stack2

输入数据，即调用 appendTail 的时候都填充到 Stack1 中（a、b、c），要 deleteHead 的时候，就依次从 Stack1 中弹出再填充到 Stack2 中 （c、b、a），当全部填充到 Stack2 中之后，直接弹出 Stack2中的栈顶元素（也就是之前最早入队的元素）即可。

算法 - 只要是入队，都是往stack1里面压栈。 - 出队时，先尝试将stack1中的数据转移到stack2中。 - 经过转移之后，如果stack2中还是没有任何一行数据，说明stack1也是空的，整体为空栈，返回\(-1\)。 - 如果不是空队，直接返回stack2栈顶的元素，也就是之前最早入队的元素即可。

Snipaste_2020-04-27_15-25-05.png

代码

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
import unittest
from typing import List

class CQueue:

    def __init__(self):
        self.stack1 = list()
        self.stack2 = list()

    def appendTail(self, value: int) -> None:
        # 只要是入队，都是往stack1里面压栈。
        self.stack1.append(value)

    def deleteHead(self) -> int:
        # 出队时，先尝试将stack1中的数据转移到stack2中
        if len(self.stack2) <= 0:
            while len(self.stack1) > 0:
                self.stack2.append(self.stack1.pop())

        # 经过转移之后，如果stack2中还是没有任何一行数据，说明stack1里面也是空的，这就是一个空队
        if len(self.stack2) == 0:
            return -1

        # 如果不是空队，直接返回stack2栈顶的元素，就是之前最早入队的元素即可。
        return self.stack2.pop()


class TestCQueue(unittest.TestCase):

    def setUp(self):
        self.test_class = CQueue()
        self.test_class2 = CQueue()

    # 测试样例1
    # 输入：
    # ["CQueue","appendTail","deleteHead","deleteHead"]
    # [[],[3],[],[]]
    # 输出：[null,null,3,-1]
    def test_CQueue_1(self):
        res = [None]  # CQueue = []
        res.append(self.test_class.appendTail(3))  # [None, None]  CQueue = [3]
        res.append(self.test_class.deleteHead())  # [None, None, 3]  CQueue = []
        res.append(self.test_class.deleteHead())  # [None, None, 3, -1]  CQueue = []
        answer = [None, None, 3, -1]
        self.assertEqual(res, answer)
    
    # 测试样例2
    # 输入：
    # ["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
    # [[],[],[5],[2],[],[]]
    # 输出：[null,-1,null,null,5,2]
    def test_CQueue_2(self):
        res = [None]  # CQueue = []
        res.append(self.test_class2.deleteHead())  # [None, -1]  CQueue = []
        res.append(self.test_class2.appendTail(5))  # [None, -1, None]  CQueue = [5]
        res.append(self.test_class2.appendTail(2))  # [None, -1, None, None]  CQueue = [5, 2]
        res.append(self.test_class2.deleteHead())  # [None, -1, None, None, 5]  CQueue = []
        res.append(self.test_class2.deleteHead())  # [None, -1, None, None, 5, 2]  CQueue = []
        answer = [None, -1, None, None, 5, 2]
        self.assertEqual(res, answer)

    def tearDown(self):
        del self.test_class
        del self.test_class2

if __name__ == '__main__':
 
    # 允许添加多个测试的方法
    # 1、构造用例集
    suite = unittest.TestSuite()
    # 2、允许添加多个测试，执行顺序是按加载顺序进行。
    suite.addTest(TestCQueue("test_CQueue_1"))
    suite.addTest(TestCQueue("test_CQueue_2"))
    # 3、实例化runner类
    runner = unittest.TextTestRunner()
    # 4、执行测试
    runner.run(suite)

举一反三：用两个队列实现一个栈

直觉

算法

  • 还是使用两个队列 Queue1 和 Queue2 。
  • 只要是入栈，只往 Queue1 里面入队。
  • 出栈时，先判断 Queue2 是不是空的。
    • 当 Queue2 不为空时，说明已经弹栈过了，依次从 Queue2 中出队再入队到 Queue1 中，当 Queue2 还剩一个元素时，不再出队了，将其返回。
    • 当 Queue2 为空且 Queue1 不为空时，依次从 Queue1 中出队再入队到 Queue2 中，当 Queue1 还剩一个元素时，不再填充了，将其返回。
    • 当 Queue2 和 Queue1 同时为空时，说明是空栈，返回 \(-1\)。
Snipaste_2020-04-27_15-25-27.png

代码

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import unittest
from typing import List

# 先进后出
class CStack:

    def __init__(self):
        self.queue1 = list()
        self.queue2 = list()

    def enterStack(self, value: int) -> None:
        # 入栈时，只往queue1里面入队。
        self.queue1.append(value)

    def exitStack(self) -> int:
        # 出栈时，先判断 Queue2 是不是空的
        if len(self.queue2) > 0:  # Queue2 不为空 说明已经弹栈过了
             # 当 Queue2 不为空时，说明已经弹栈过了，依次从Queue2中出队再出队到 Queue1 中，当 Queue2 还剩一个元素时，不再出队了，将其返回。
            while len(self.queue2) > 1:
                self.queue1.append(self.queue2.pop(0))
            return self.queue2.pop(0)
        
        # Queue2 为空 说明还没有弹栈过
        if len(self.queue1) > 0:  # Queue1 不为空
            # 当 Queue2 为空且 Queue1 不为空时，依次从 Queue1 中出队再出队到 Queue2 中，当 Queue1 还剩一个元素时，不再出队了，将其返回。
            while len(self.queue1) > 1:
                self.queue2.append(self.queue1.pop(0))
            return self.queue1.pop(0)
        else:  # 当 Queue2 和 Queue1 同时为空时，说明是空栈，返回-1。
            return -1



class TestCStack(unittest.TestCase):

    def setUp(self):
        self.test_class = CStack()
        self.test_class2 = CStack()

    # 测试样例1
    # 输入：
    # ["CStack","enterStack","exitStack","exitStack"]
    # [[],[3],[],[]]
    # 输出：[null,null,3,-1]
    def test_CStack_1(self):
        res = [None]  # CStack = []
        res.append(self.test_class.enterStack(3))  # [None, None]  CStack = [3]
        res.append(self.test_class.exitStack())  # [None, None, 3]  CStack = []
        res.append(self.test_class.exitStack())  # [None, None, 3, -1]  CStack = []
        answer = [None, None, 3, -1]
        self.assertEqual(res, answer)
    
    # 测试样例2
    # 输入：
    # ["CStack","exitStack","enterStack","enterStack","exitStack","exitStack"]
    # [[],[],[5],[2],[],[]]
    # 输出：[null,-1,null,null,2,5]
    def test_CStack_2(self):
        res = [None]  # CStack = []
        res.append(self.test_class2.exitStack())  # [None, -1]  CStack = []
        res.append(self.test_class2.enterStack(5))  # [None, -1, None]  CStack = [5]
        res.append(self.test_class2.enterStack(2))  # [None, -1, None, None]  CStack = [5, 2]
        res.append(self.test_class2.exitStack())  # [None, -1, None, None, 2]  CStack = [5]
        res.append(self.test_class2.exitStack())  # [None, -1, None, None, 2, 5]  CStack = []
        answer = [None, -1, None, None, 2, 5]
        self.assertEqual(res, answer)

    def tearDown(self):
        del self.test_class
        del self.test_class2

if __name__ == '__main__':
 
    # 允许添加多个测试的方法
    # 1、构造用例集
    suite = unittest.TestSuite()
    # 2、允许添加多个测试，执行顺序是按加载顺序进行。
    suite.addTest(TestCStack("test_CStack_1"))
    suite.addTest(TestCStack("test_CStack_2"))
    # 3、实例化runner类
    runner = unittest.TextTestRunner()
    # 4、执行测试
    runner.run(suite)