为了OFFER，我加深学习，搞懂了栈
@Author：Runsrn
@Date：2020/9/8
现在大四基本是重刷数据结构和算法，因为笔试真的太重要了。 我又重温了争大佬专栏的栈，又巩固了下。而且我发现留言区大佬的笔记很多，下面很多都是来自大佬总结的。
一、什么是栈？
1、栈是一种操作受限的数据结构，只支持入栈和出栈操作。
2、典型的“栈”结构：后进者先出，先进者后出。
3、从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。
4、特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。
二、为什么需要栈？
1.栈是一种操作受限的数据结构，其操作特性用数组和链表均可实现。
2.但，任何数据结构都是对特定应用场景的抽象，数组和链表虽然使用起来更加灵活，但却暴露了几乎所有的操作，难免会引发错误操作的风险。
3.所以，当某个数据集合只涉及在某端插入和删除数据，且满足后进者先出，先进者后出的操作特性时，我们应该首选栈这种数据结构。
三、如何实现栈？
1.栈的API ，Java代码实现，代码来自争大佬。
// 基于数组实现的顺序栈
public class ArrayStack {
private String[] items; // 数组
private int count; // 栈中元素个数
private int n; //栈的大小 // 初始化数组，申请一个大小为n的数组空间
public ArrayStack(int n) { this.items = new String[n]; this.n = n; this.count = 0;
} // 入栈操作
public boolean push(String item) { // 数组空间不够了，直接返回false，入栈失败。 if (count == n) return false; // 将item放到下标为count的位置，并且count加一 items[count] = item; ++count; return true;
} // 出栈操作
public String pop() { // 栈为空，则直接返回null if (count == 0) return null; // 返回下标为count-1的数组元素，并且栈中元素个数count减一 String tmp = items[count-1]; --count; return tmp;
}
}
- 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
2.数组实现（自动扩容）
时间复杂度分析：根据均摊复杂度的定义，可以得数组实现（自动扩容）符合大多数情况是O(1)级别复杂度，个别情况是O(n)级别复杂度，比如自动扩容时，会进行完整数据的拷贝。
空间复杂度分析：在入栈和出栈的过程中，只需要一两个临时变量存储空间，所以O(1)级别。我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。
3.链表实现
时间复杂度分析：压栈和弹栈的时间复杂度均为O(1)级别，因为只需更改单个节点的索引即可。
空间复杂度分析：在入栈和出栈的过程中，只需要一两个临时变量存储空间，所以O(1)级别。我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。
四、栈的应用
1.栈在函数调用中的应用
操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构，用来存储函数调用时的临时变量。每进入一个函数，就会将其中的临时变量作为栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。
2.栈在表达式求值中的应用（比如：34+13*9+44-12/3）
利用两个栈，其中一个用来保存操作数，另一个用来保存运算符。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较，若比运算符栈顶元素优先级高，就将当前运算符压入栈，若比运算符栈顶元素的优先级低或者相同，从运算符栈中取出栈顶运算符，从操作数栈顶取出2个操作数，然后进行计算，把计算完的结果压入操作数栈，继续比较。
3.栈在括号匹配中的应用（比如：{}{[()]()}） Leetcode 20 题
用栈保存为匹配的左括号，从左到右一次扫描字符串，当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号，如果能匹配上，则继续扫描剩下的字符串。如果扫描过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。
当所有的括号都扫描完成之后，如果栈为空，则说明字符串为合法格式；否则，说明未匹配的左括号为非法格式。
4.如何实现浏览器的前进后退功能？
我们使用两个栈X和Y，我们把首次浏览的页面依次压如栈X，当点击后退按钮时，再依次从栈X中出栈，并将出栈的数据一次放入Y栈。当点击前进按钮时，我们依次从栈Y中取出数据，放入栈X中。当栈X中没有数据时，说明没有页面可以继续后退浏览了。当Y栈没有数据，那就说明没有页面可以点击前进浏览了。
五、思考题
我们在讲栈的应用时，讲到用函数调用栈来保存临时变量，为什么函数调用要用“栈”来保存临时变量呢？用其他数据结构不行吗？
答：因为函数调用的执行顺序符合后进者先出，先进者后出的特点。比如函数中的局部变量的生命周期的长短是先定义的生命周期长，后定义的生命周期短；还有函数中调用函数也是这样，先开始执行的函数只有等到内部调用的其他函数执行完毕，该函数才能执行结束。
正是由于函数调用的这些特点，根据数据结构是特定应用场景的抽象的原则，我们优先考虑栈结构。
我们都知道，JVM 内存管理中有个“堆栈”的概念。栈内存用来存储局部变量和方法调用，堆内存用来存储 Java 中的对象。那 JVM 里面的“栈”跟我们这里说的“栈”是不是一回事呢？如果不是，那它为什么又叫作“栈”呢？
答：JVM里面的栈和我们这里说的是一回事，被称为方法栈。和前面函数调用的作用是一致的，用来存储方法中的局部变量。
leetcode上关于栈的题目大家可以先做20,155,232,844,224,682,496。我请重新再写了下，发现难度没有之前的大。
六、20有效的扩号
'''
@Author： Runsen
@WeChat：RunsenLiu
@微信公众号： Python之王
@CSDN： https://blog.csdn.net/weixin_44510615
@Github： https://github.com/MaoliRUNsen
@Date： 2020/9/8
'''
class Solution: def isValid(self, s: str) -> bool: stack = [] d = {"{": "}", "[": "]", "(": ")"} for i in s: if i in d: stack.append(i) else: # 记住如果使用了stack.pop() 那么就已经默认删除了 pop这里已经执行了 # 还有not stack和 len(stack) == 0等价 if (len(stack) == 0) or (d[stack.pop()] != i): return False return len(stack) == 0
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
7、155最小栈（方法：辅助栈）
class MinStack: def __init__(self): # 使用辅助栈，q2来存储最小值 self.q1 = [] self.q2 = [] def push(self, x): self.q1.append(x) # 这里需要判断q2是不是为空，或者q2[-1]大于x，说明最小值不是q2[-1]， if (len(self.q2) == 0) or (x <=self.q2[-1]): self.q2.append(x) else: # 那么q2就添加q2[-1】 self.q2.append(self.q2[-1]) def pop(self): # 删除就是把q1和q2都删除了 self.q1.pop() self.q2.pop() def top(self): return self.q1[-1] def getMin(self): return self.q2[-1]
- 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
8、 232用栈实现队列
class MyQueue: def __init__(self): self.s = [] def push(self, x: int) -> None: self.s.append(x) def pop(self) -> int: return self.s.pop(0) def peek(self) -> int: return self.s[0] def empty(self) -> bool: return not bool(self.s) # return not self.s 和上面同价
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
这里，我想起了上面的有效的扩号中的not stack，和bool stack做一个对比
>>> a = []
>>> not a
True
>>> bool(a)
False
>>> a = [1]
>>> not a
False
>>> bool(a)
True
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
not a就是len(a) == 0，bool就是len(a) != 0 。感觉来的
9、844比较含退格的字符串
class Solution: def backspaceCompare(self, S: str, T: str) -> bool: # 定义一个函数返回最终的结果 def solve(s): # 定义一个栈，如果没有遇到# 就存储起来 stack = [] for i in s: if i == "#": if len(stack) !=0: stack.pop() else: continue else: stack.append(i) return ''.join(stack) return solve(S) == solve(T)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
10、682棒球比赛
class Solution: def calPoints(self, ops: List[str]) -> int: # 做法 用一个栈来记录每轮数据 stack1 = [] for i in ops: if i == "C": # 直接删除最后一个 stack1.pop() elif i =="D": stack1.append(stack1[-1] * 2) elif i == "+": stack1.append(stack1[-1] + stack1[-2]) else: stack1.append(int(i)) return sum(stack1)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
11、496下一个更大元素 I
输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。
对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。
对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。
class Solution: def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]: stack = [] for i in nums1: index = nums2.index(i) # 如果index就是最后一个就不用干了 if index == (len(nums2) - 1): stack.append(-1) continue else: # 说明不是最后一个 index+1可以不取到本身 while index < len(nums2): if nums2[index] > i: stack.append(nums2[index]) break if index == len(nums2) -1 and (nums2[index] > i): stack.append(nums2[index]) if index == len(nums2) -1 and (nums2[index] <= i): stack.append(-1) index = index + 1 return stack
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
上面全部通过，以后遇到栈，就是在恐怖的算法面试中遇见了爱情！！！！！
如果你想跟博主建立亲密关系，可以关注博主，或者关注博主公众号“Python之王”，了解一个非本科程序员是如何成长的。
博主ID：润森（weixin_44510615），希望大家点赞、评论、收藏
文章来源: maoli.blog.csdn.net，作者：刘润森！，版权归原作者所有，如需转载，请联系作者。
原文链接：maoli.blog.csdn.net/article/details/108474268
- 点赞
- 收藏
- 关注作者
评论（0）