LeetCode刷题之栈、队列、堆的解题方法及相关练习

﹏ヽ暗。殇╰゛Y 2023-02-18 05:24 22阅读 0赞

**理论引述**

栈Stack：先进后出的线性表  
队列Queue：先进先出的线性表  
[python中heapq堆的讲解][python_heapq]

a = [1,2,3,4,5]
    print(a.pop())  # 结果为5，说明弹出的是数组中的最后一个元素

--------------------

**习题目录**

\[1\]. [快乐的LeetCode — 225. 用队列实现栈的三种解法][LeetCode _ 225.]  
\[2\]. [快乐的LeetCode — 面试题09. 用两个栈实现队列][LeetCode _ _09.]  
[\[3\]. 快乐的Leetcode — 155. 最小栈 (面试题30. 包含min函数的栈)][3_. _Leetcode _ 155. _ _30. _min]  
\[4\]. [快乐的LeetCode — 面试题31. 栈的压入、弹出序列][LeetCode _ _31.]  
\[5\]. [快乐的LeetCode — 215. 数组中的第K个最大元素][LeetCode _ 215. _K]

--------------------

**1.使用队列实现栈时，可以转化思路为数组顺序的变换**

**图解表述：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center]  
**代码表述：**

class MyStack:
    
        def __init__(self):
            self.queue = []
    
        def push(self, x):
            self.queue.append(x)           # 先进
            length = len(self.queue)
            for i in range(length-1):
                first = self.queue[0]      # 后出
                del self.queue[0]
                self.queue.append(first)
    
        def pop(self):
            target = self.queue[0]
            del self.queue[0]
            return target
    
        def top(self):
            return self.queue[0]
    
        def empty(self):
            return len(self.queue) == 0

--------------------

**2.使用栈实现队列**

*  push(x) – 将一个元素放入队列的尾部。
 *  pop() – 从队列首部移除元素。
 *  peek() – 返回队列首部的元素。
 *  empty() – 返回队列是否为空。

**代码表述：**

class MyQueue(object):
        def __init__(self):
            self.quene = []
    
        def push(self, x):
            self.quene.append(x)      # 先进
    
        def pop(self):
            target = self.quene[0]    # 先出
            del self.quene[0]
            return target
    
        def peek(self):
            return self.quene[0]
    
        def empty(self):
            return len(self.quene) == 0

--------------------

**3.包含min函数的栈**

[快乐的Leetcode — 155. 最小栈 (面试题30. 包含min函数的栈)][3_. _Leetcode _ 155. _ _30. _min]

--------------------

**4.面试题31. 栈的压入、弹出序列**

关键点：每次入栈后，循环判断 “栈顶元素 == 弹出序列的当前元素” 是否成立，将符合弹出序列顺序的栈顶元素全部弹出。

class Solution(object):
        def validateStackSequences(self, pushed, popped):
            stack, i = [], 0
            for num in pushed:
                stack.append(num)
                while stack and stack[-1] == popped[i]:
                    stack.pop()
                    i += 1
            return not stack

--------------------

**5.数组中的第K个最大元素**

[快乐的LeetCode — 215. 数组中的第K个最大元素][LeetCode _ 215. _K]

[python_heapq]: https://blog.csdn.net/weixin_43283397/article/details/104983664
[LeetCode _ 225.]: https://blog.csdn.net/weixin_43283397/article/details/104768204
[LeetCode _ _09.]: https://blog.csdn.net/weixin_43283397/article/details/104761182
[3_. _Leetcode _ 155. _ _30. _min]: https://blog.csdn.net/weixin_43283397/article/details/105466602
[LeetCode _ _31.]: https://blog.csdn.net/weixin_43283397/article/details/106802525
[LeetCode _ 215. _K]: https://blog.csdn.net/weixin_43283397/article/details/106803595
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200616112141825.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw==,size_16,color_FFFFFF,t_70#pic_center