python算法刷题——栈和队列（一）

算法菜鸡的刷题记录，写的代码可能比较多冗余，可以到leetcode解题区看更多大佬们优雅的解题~

一、栈和队列

栈（stack）： 后进先出。
栈的一些标准操作：

s.pop()		# 出栈
s.push()	# 入栈
s.top()		# 获取栈顶元素（不出栈）
s.size()	# 获取栈的大小（元素个数）
s.empty()	# 判断栈是否为空，返回true or false

队列（queue）： 先进先出。
队列的一些标准操作：

q.pop()		# 出队
q.push()	# 入队
q.front()	# 获取队首元素（出队一端）
q.back()	# 获取队尾元素（入队一端）
q.size()	# 获取队列大小
q.empty()	# 判断队列是否为空，返回true or false

python中的栈和队列的一些标准操作：

from Queue import Queue, LifoQueue

q = Queue(maxsize=x)	# Queue，一般队列，maxsize--指定队列大小，可选参数
lq = LifoQueue(maxsize=x)	#LifoQueue，后进先出队列，相当于栈

"""只用q举例，lq方法同"""
q.put(x)	# 入队
q.get()		# 出队，会返回出队元素
q.qsize()	# 获取当前队列元素个数
q.full()	# 判断队列是否已满
q.empty()	# 判断队列是否为空

二、实战

1. leetcode 225 用队列实现栈

思考点：

• 可以修改队列的入队方式，使得队列入队之后结构与栈相同，其余操作就可以直接进行。
• 也可以修改队列的出队方式，使得队列的出队顺序与栈相同。

以修改入队方式为例，如何修改？

• 临时队列的应用

from queue import Queue
class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data_queue = Queue()	# data_queue用于实际存储数据
        self.tmp_queue = Queue()	# tmp_queue作为临时队列使用

	"""
	1. 每次入队之前，先将元素push到tmp_queue中，此时该元素处于队首
	2. 将data_queue的元素依次push到tmp_queue中（假设此时data_queue的元素已经按照栈的结构存储）
	3. 再将tmp_queue的元素复制到data_queue中（data_queue是实际用来作为存储的元素）
	"""

    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        self.tmp_queue.put(x)
        while not self.data_queue.empty():
            self.tmp_queue.put(self.data_queue.get())
        while not self.tmp_queue.empty():
            self.data_queue.put(self.tmp_queue.get())


    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        return self.data_queue.get()

	"""这里要注意queue中没有直接的top方法，get()方法会将元素弹出，需要重新压入"""
    def top(self) -> int:
        """
        Get the top element.
        """
        x = self.data_queue.get()
        self.push(x)
        return x


    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return self.data_queue.empty()

时间复杂度：push操作为O(n)，其余为O(1)
空间复杂度：O(n)

• 当然其实可以用一个队列也能完成，思路也简单明了，当我们要入栈时，将元素x push到队列中，同时将位于x前面的元素出队再入队，这样x就变成了队首元素。具体实现如下（主要是修改了Push方法，其余与上面代码一致）：

    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        tmp = self.data_queue.qsize()
        self.data_queue.put(x)
        while tmp>0:
            self.data_queue.put(self.data_queue.get())
            tmp -= 1

2. leetcode 232 使用栈实现队列

这题与上题原理和思考方式都类似，我们可以参照着来实现。（这里使用了LifoQueue，当然也可以直接用list实现栈）

• 使用临时栈

from queue import LifoQueue
class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data_stack = LifoQueue()
        self.tmp_stack = LifoQueue()

	"""
	1. 先将data_stack中的元素依次push到tmp_stack中（data_Stack是已经按照队列的顺序存储的数据栈，push到tmp_stack后tmp_stack得到的是一个与data_stack相反的栈）
	2. 将元素x压入data_stack中，此时相当于队尾元素放在栈底
	3. 将tmp_stack中的元素重新压入data_stack中
	"""
    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        while not self.data_stack.empty():
            self.tmp_stack.put(self.data_stack.get())
        self.data_stack.put(x)
        while not self.tmp_stack.empty():
            self.data_stack.put(self.tmp_stack.get())


    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        return self.data_stack.get()

	"""这里注意与上一题不同，栈是后进先出的，所以只需要直接调用put方法将其放回栈顶即可，不要调用push将其放入栈底！！！"""
    def peek(self) -> int:
        """
        Get the front element.
        """
        x = self.data_stack.get()
        self.data_stack.put(x)
        return x

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return self.data_stack.empty()

时间复杂度：入队O(n)，出队O(1)
空间复杂度：O(n)

另一种同样是使用了两个栈，但是能够实现入队和出队时间复杂度都达到O(1)的方法，如下：

from queue import LifoQueue
class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.push_stack = LifoQueue()
        self.pop_stack = LifoQueue()

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.push_stack.put(x)

	"""
	1.当pop_stack为空时，一次性将所有的push_stack中的元素压入pop_stack中，此时pop_stack中的元素与实际队列的存储顺序是一致的
	2.弹出pop_stack栈顶元素即可
	"""
    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        if self.pop_stack.empty():
            while not self.push_stack.empty():
                self.pop_stack.put(self.push_stack.get())
        return self.pop_stack.get()


    def peek(self) -> int:
        """
        Get the front element.
        """
        if self.pop_stack.empty():
            while not self.push_stack.empty():
                self.pop_stack.put(self.push_stack.get())
        x = self.pop_stack.get()
        self.pop_stack.put(x)
        return x

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return self.push_stack.empty() and self.pop_stack.empty()

此时入队和出队操作的时间复杂度都是O(1)，为什么出队也是O(1)呢？这里涉及到摊还思想 ，简单理解就是，每一个元素都入栈两次、出栈两次（push_stack和pop_stack），所以平均的复杂度是O(1)。更具体的理解参考官方题解。

3.leetcode155 最小栈

这个题目有个注意的点是在常数时间内 检索到。遍历栈或者用一些排序方式固然可以找到最小值，但是无法在满足常数时间的要求。
要在常数时间内实现，我们会想到，如果有一个变量来记录最小值，需要的时候直接取到就可以实现O(1)。
这里借助一个辅助栈，这个栈要记录什么呢？由于入栈出栈操作是动态的，所以最小值也是动态的，我们可以用一个栈来维护每一个状态下的最小值。具体实现如下：

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.data_stack = []
        self.min_stack = []

    """
	1. 当第一个元素入栈时，它就是当前栈的最小值，于是Push到min_stack
	2. 当入栈元素小于min_stack的栈顶元素时，说明该元素入栈之后是当前状态的最小值，因此将它push到min_stack中
	3. 当入栈元素大于min_stack的栈顶元素时，说明该元素入栈之后当前状态的最小值没有发生改变，因此将原来的最小值（就是min_stack栈顶元素）push到min_stack中
	"""
    def push(self, x: int) -> None:
        self.data_stack.append(x)
        if self.min_stack == [] or self.min_stack[-1] > x:
            self.min_stack.append(x)
        else:
            self.min_stack.append(self.min_stack[-1])

    def pop(self) -> None:
        self.data_stack = self.data_stack[0:-1]
        self.min_stack = self.min_stack[0:-1]

    def top(self) -> int:
        return self.data_stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

4. leetcode946 验证栈序列

这个题目简单说就是验证出栈顺序(poped)是否正确，那很自然想到可以模拟一个它的出栈入栈顺序来验证。具体来看实现：

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        if not pushed and not popped:
            return True
        tmp_stack = []	# 用于模拟入栈
        """
		1. 遍历pushed，模拟入栈
		2. 在入栈过程中，如果栈顶元素与poped的第一个元素相同，则该元素从tmp_stack中出栈，同样从pooped中去除（或者采用指针移到下一个位置的方式），否则下一个元素入栈
		3. 如果最后poped == []（或者指针将要越界），说明序列合法
		"""
        for i in pushed:
            tmp_stack.append(i)
            while tmp_stack and tmp_stack[-1] == popped[0]:
                tmp_stack = tmp_stack[0:-1]
                popped = popped[1:]
                if not popped:
                    return True
        return False

时间复杂度O(n)（遍历pushed），空间复杂度O(n)

5.leetcode224 基本计算器

这题不是非常理解写的非常乱……建议跳过……

这是一个hard题，在官方题解和一些讲解中的代码看的迷迷糊糊，要自己实现还有点困难，这里先说一下思路，然后附上我傻瓜式的实现。后面再来补充一些更好的方法。
思路比较简单，没什么技巧，就是硬解（-^-|||）
遍历字符串：
1.如果是数字，加入num_stack中；
2.如果是+/-，加入op_stack中，设置compute=True；
3.如果是左括号，说明现在还不能进行计算（优先级的问题），设置compute=False;
4.如果是右括号，说明括号里的内容遍历完了，可以进行运算了，设置compute=True;

什么时候进行运算：
1.compute必须为true；
2.满足运算规则（就是比如加减法，两个数字对应一个运算符才能进行运算）

如何进行运算：
1.栈顶的符号相当于当前状态时最内层的运算符，所以取栈顶符号进行运算
2.数字是从左到右入栈的，计算时应该从左到右运算；最内层的数字最后入栈，所以也是栈顶开始运算

class Solution:
    def calculate(self, s):
        num_stack = []	#记录数据
        op_stack = []	#记录运算符
        num = 0
        res = 0
        compute = False		# 用于标记现在是否可以运算
        i = 0
        while i < len(s):
			"""
			这里可以想成如果len(num_stack)==len(op_stack)的话说明先前有括号/或者下一个数字还未入栈，不能进行运算
			"""
            if len(num_stack) > len(op_stack) and compute and op_stack:
                if op_stack[-1] == '+':
                    res = num_stack[-2] + num_stack[-1]
                elif op_stack[-1] == '-':
                    res = num_stack[-2] - num_stack[-1]
                num_stack = num_stack[0:-2]
                num_stack.append(res)
                op_stack = op_stack[0:-1]

            if '0' <= s[i] <= '9':
                while i < len(s) and '0' <= s[i] <= '9':
                    num = (num * 10) + int(s[i])
                    i = i + 1
                num_stack.append(num)
                num = 0
                continue

            elif s[i] == '+' or s[i] == '-':
                op_stack.append(s[i])
                compute = True

            elif s[i] == '(':
                compute = False

            else:
                compute = True
            i = i + 1

        while op_stack:
            if op_stack[-1] == '+':
                res = num_stack[-2] + num_stack[-1]
            elif op_stack[-1] == '-':
                res = num_stack[-2] - num_stack[-1]
            num_stack = num_stack[0:-2]
            num_stack.append(res)
            op_stack = op_stack[0:-1]

 
        return num_stack[-1]

视频（b站的leetcode算法讲解）里就讲了这几题，太长了下一篇再来记录一下栈和队列的其他题目~