文章目录

• 栈
• 栈的实现
• 练习题 423 · 有效的括号序列
• 栈的调用
• 队列
• 练习题 492 · 队列维护

栈

python没有栈，需要用list去实现。list也有pop操作。list可以说比stack更厉害一些，因为list可以按索引访问。


peek是查看栈顶元素，但是不弹出。

栈的实现

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

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

括号必须依照 “()” 顺序表示， “()[]{}” 是有效的括号，但 “([)]” 则是无效的括号。

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

这道题因为上课的时候老师讲了，所以我没有自己想，之前也做过类似的题，大体知道用什么方法做。

if not 的用法更新：注意’’’’ 和“ ”是不一样的。另外[]可以用

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

栈的调用

一个主调函数去调用被调函数，被调函数就会执行，当被调函数执行完毕，就返回到主调函数中调用它的位置。那么在操作系统底层，是怎么维护主调和被调的函数关系的？

main pc就是记录main函数的program count。



每次调用一个被调函数，都会在栈中记录原主函数的pc。

baz结束后，baz函数的变量全部被清除。找到离栈顶最近的pc。pc可以回到上一个主函数调用的被调函数的位置。

bar函数执行完，释放arr，去找foo pc。回到foo函数

foo函数释放name变量，回到main函数

main函数执行完毕，释放num。栈为空。

Question：为什么这需要一个栈的数据结构呢？
栈是一个线性的数据结构。
当有很多很多的函数不断的往栈里压入的时候，就会报错：栈溢出。index
out of range. stack overflow. 可能是写成死循环了。

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

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

队列

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

官方答案：

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()。