栈Stack

定义Definition

栈: 只允在一端进行插入或删除操作的线性表。

特点: 后进先出

队列Queue

定义Definition

队列是一种先进先出的线性表。

它只允许在表的一端进行插入，而在另一端删除元素。在队列中允许插入的一端叫做队尾，允许删除的一端则称为队头。

特点: 先进先出

剑指offer

题目

用两个栈实现一个队列。

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

示例1: 

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

示例2: 

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

理解Code

首先,我考虑在Python中实现这道题目.然后明白题目中要求定义两个函数, 分别实现在队列的添加和删除元素的功能.

这个队列还要求用两个栈来实现. Python中哪有现成的栈给我调用呢? 没有的,只能用列表来实现了.

而且appendTail这个函数是没有返回值的, 但是需要传递值.

deleteHead函数是需要有返回值的(如果队列为空则返回-1, 不为空则返回整个队列)

OK下面开始写代码!

Demo

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
# 剑指Offer题目:(用两个栈实现队列
"""
只是用一个栈stack1 当做队列, 另一个栈stack2来辅助操作
要想加入新的元素出现在栈底,需要将其中的元素全部移动到另一个栈stack2,
然后将要入队列的元素方法stack1的栈底, 最后再将stack2栈中的元素放入stack1, 类似于汉诺塔问题
"""
class CQueue:
    # 使用两个python中的列表模拟栈(其他语言Java, C都类似
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    # 定义添加元素到队列的函数 (这里使用了两个列表模拟两个伪栈(后进先出
    def appendTail(self, value: int) -> None:
        # 当第一个栈非空,就将栈中的元素末尾元素弹出, 并且追加到另一个栈的末尾
        while self.stack1:
            # 弹出栈1的末尾元素, 放到栈2的末尾
            self.stack2.append(self.stack1.pop())
        # 第一个栈元素直至弹出完成(为空) 就添加新的元素入栈
        self.stack1.append(value)
        # 同理,这个while循环的作用也是将栈2的元素整体移动到栈1中
        while self.stack2:
            # 当栈2不为空,就将栈2的末尾元素放到栈1的末尾(整体平移
            self.stack1.append(self.stack2.pop())
        # 这里stack1 是存储元素的,stack2是辅助stack1存储的作用
        return self.stack1
    # 定义删除队列的元素 的方法(两个列表模拟两个栈
    def deleteHead(self) -> int:
        # 如果栈1中元素为空就返回 -1
        if not self.stack1:
            return -1
        # 将栈中元素返回(由栈底到栈顶依次弹出)因为模拟的是队列(先进先出
        return self.stack1.pop()