Leetcode 算法面试冲刺 栈与队列 理论 上(十八)

文章目录

python没有栈,需要用list去实现。list也有pop操作。list可以说比stack更厉害一些,因为list可以按索引访问。
Leetcode 算法面试冲刺 栈与队列 理论 上(十八)
Leetcode 算法面试冲刺 栈与队列 理论 上(十八)
peek是查看栈顶元素,但是不弹出。
Leetcode 算法面试冲刺 栈与队列 理论 上(十八)

栈的实现

Leetcode 算法面试冲刺 栈与队列 理论 上(十八)

练习题 423 · 有效的括号序列

给定一个字符串所表示的括号序列,包含以下字符: ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, 判定是否是有效的括号序列。

括号必须依照 “()” 顺序表示, “()[]{}” 是有效的括号,但 “([)]” 则是无效的括号。
Leetcode 算法面试冲刺 栈与队列 理论 上(十八)

def isValidParentheses(self, s):
    # write your code here
        if not s: return True

        stack = []

        for i, ch in enumerate(s):
            if ch == '(' or ch == "[" or ch == '{':
                stack.append(ch)
            else:
                if not stack:
                    return False
                elif (ch == ')' and stack[-1] == '(') or \
                    (ch == ']' and stack[-1] == '[') or \
                    (ch == '}' and stack[-1] == '{'):
                    stack.pop()
                else:
                    return False

        return not stack

这道题因为上课的时候老师讲了,所以我没有自己想,之前也做过类似的题,大体知道用什么方法做。
Leetcode 算法面试冲刺 栈与队列 理论 上(十八)
if not 的用法更新:注意’’’’ 和“ ”是不一样的。另外[]可以用

if not "":
    print(1)
    
if not " ":
    print(11)
    
if not []:
    print(2)

栈的调用

Leetcode 算法面试冲刺 栈与队列 理论 上(十八)
一个主调函数去调用被调函数,被调函数就会执行,当被调函数执行完毕,就返回到主调函数中调用它的位置。那么在操作系统底层,是怎么维护主调和被调的函数关系的?
Leetcode 算法面试冲刺 栈与队列 理论 上(十八)
main pc就是记录main函数的program count。
Leetcode 算法面试冲刺 栈与队列 理论 上(十八)
Leetcode 算法面试冲刺 栈与队列 理论 上(十八)
Leetcode 算法面试冲刺 栈与队列 理论 上(十八)
每次调用一个被调函数,都会在栈中记录原主函数的pc。
Leetcode 算法面试冲刺 栈与队列 理论 上(十八)
baz结束后,baz函数的变量全部被清除。找到离栈顶最近的pc。pc可以回到上一个主函数调用的被调函数的位置。
Leetcode 算法面试冲刺 栈与队列 理论 上(十八)
bar函数执行完,释放arr,去找foo pc。回到foo函数
Leetcode 算法面试冲刺 栈与队列 理论 上(十八)
foo函数释放name变量,回到main函数
Leetcode 算法面试冲刺 栈与队列 理论 上(十八)
main函数执行完毕,释放num。栈为空。
Leetcode 算法面试冲刺 栈与队列 理论 上(十八)
Question:为什么这需要一个栈的数据结构呢?
栈是一个线性的数据结构。
当有很多很多的函数不断的往栈里压入的时候,就会报错:栈溢出。index
out of range. stack overflow. 可能是写成死循环了。

def *(count = 1):
    count += 1
    print(count)
    *(count)
    
*(count = 1)

刚刚我自己跑了下,调用100次,就溢出了。
栈的存在,让函数之间的调用变得优雅,简单。

队列

Leetcode 算法面试冲刺 栈与队列 理论 上(十八)
Leetcode 算法面试冲刺 栈与队列 理论 上(十八)
Leetcode 算法面试冲刺 栈与队列 理论 上(十八)
Leetcode 算法面试冲刺 栈与队列 理论 上(十八)
head和tail两个指针,分别指向链表的首尾。方便进队列和出队列。

练习题 492 · 队列维护

按链表实现队列。支持以下基本方法:

  • enqueue(item).将新元素放入队列中。
  • dequeue(). 将第一个元素移出队列,返回它。

class MyQueue:
    """
    @param: item: An integer
    @return: nothing
    """
    def __init__(self):
        self.first = None
        self.last = None

    def enqueue(self, item):
        # write your code here
        if not self.first:
            self.first = ListNode(item)
            self.last = self.first
        else:
            self.last.next = ListNode(item)
            self.last = self.last.next

    """
    @return: An integer
    """
    def dequeue(self):
        # write your code here
        if self.first:
            cur = self.first
            self.first = cur.next
            return cur.val

Leetcode 算法面试冲刺 栈与队列 理论 上(十八)

Leetcode 算法面试冲刺 栈与队列 理论 上(十八)
官方答案:

class MyQueue(object):

    def __init__(self):
        # do some intialize if necessary
        self.first, self.last = None, None

    # @param {int} item an integer
    # @return nothing
    def enqueue(self, item):
        # Write yout code here
        if self.first is None:
            self.first = Node(item)
            self.last = self.first
        else:
            self.last.next = Node(item)
            self.last = self.last.next

    # @return an integer
    def dequeue(self):
        # Write your code here
        if self.first is not None:
            item = self.first.val
            self.first = self.first.next
            return item

        return -1000

class Node():

    def __init__(self, _val):
        self.next = None
        self.val = _val

Queue有一个maxsize,如果不写,默认是0. maxsize<1表示无限的大小。如果是100,就是100的长度。

操作系统的内容有一个消息队列,我们动鼠标或者键盘都会放到这个消息队列里面,操作系统的kernel就会按照这个消息的先进先出,依次完成任务。

from queue import Queue
q = Queue()
for i in range(10):
    q.put(i)

while not q.empty():
    print(q.get(), end=" ")
print()
print(q.qsize())

注意while的条件,我写

while q:

就会进入死循环,说明q虽然为空了,但是还是有值。所以要用empty()。

上一篇:1.28实验:探究一个好的数据结构对链表的影响(本实验为改进代码实验)


下一篇:windows 局域网远程桌面mstsc走过的坑