数据结构之栈、队列和递归

[TOC]

栈(stack)

栈是一种只能在一端进行操作的线性表，它最大的特点是进行数据操作时必须遵循“后进先出（Last In FirstOut，LIFO）”的原则

• 术语

  栈顶(top)：可以进行增删改查操作的一端

  栈底(bottom)：无法进行上述操作

• 栈的基本操作

• 栈的抽象数据类型的定义

栈的顺序存储

class SequenceStack:
    def __init__(self):
        self.stack = []
        self.top = -1

    def push(self,data):
        self.stack.append(data)
        self.top += 1

    def pop(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        else:
            data = self.stack.pop()
            self.top -= 1
            return data

    def is_empty(self):
        return self.top == -1

    def len(self):
        return self.top+1

    def getTop(self):
        if self.is_empty():
            print("Stack is empty")
            return
        else:
            return self.stack[self.top]

    def display(self):
        if self.is_empty():
            print("Stack is empty")
        else:
            for i in range(self.len()):
                print(f"第{i+1}元素：{self.stack[i]}")

案例应用

1、匹配括号

from sequence_stack import SequenceStack

txt = "(()()()())(((())))(()((())()))"

def perCheck(txt):
    stack = SequenceStack()
    for t in txt:
        if t == '(':
            stack.push(t)
        elif t == ')':
            if stack.is_empty():
                return False
            else:
                stack.pop()
        else:
            continue
    return stack.is_empty()

print(perCheck(txt))

2、进制转换

from sequence_stack import SequenceStack
def binaryTransform(num):
    stack = SequenceStack()
    while num>0:
        d = num % 2
        stack.push(d)
        num = num//2

    binStr = ''
    while stack.is_empty() == False:
        d = stack.pop()
        binStr = binStr + str(d)

    return binStr

num = 233
print(binaryTransform(num))

栈的链式存储

队列

队列是有序集合，添加操作发生在“尾部”，移除操作则发生在“头部”。最新添加的元素必须在队列的尾部等待，在队列中时间最长的元素则排在最前面。这种排序原则被称作FIFO（first-in first-out）

队列的顺序存储

class Queue:

    def __init__(self):
        self.queue = []

    def is_empty(self):
        return self.queue == []

    def enqueue(self,data):
        self.queue.insert(0,data)
        return

    def dequeue(self):
        # if self.is_empty():
        #     raise IndexError("queue is empty")
        self.queue.pop()
        return

    def size(self):
        return len(self.queue)

    def display(self):
        print(self.queue)

案例应用

1、传炸弹

from queue import Queue
def transmitBomb(namelist,num):
    q = Queue()
    for name in namelist:
        q.enqueue(name)

    die_list = []
    while q.size() != 1:
        for i in range(num):
            bomb = q.dequeue()
            q.enqueue(bomb)
            q.display()

        die_list.append(q.dequeue())

    return q.get_head(),die_list

name_list = ["Bill", "David", "Susan", "Jane", "Kent", "Brad"]
print(transmitBomb(name_list, 7))

2、打印机

# coding:utf-8
import random
from squeue import sQueue

class Task:

    def __init__(self,cTime):
        self.createTime = cTime
        self.pages = random.randrange(1,21)

    def get_cTime(self):
        return self.createTime

    def get_pages(self):
        return self.pages

    def wait_time(self,currentSec):
        return currentSec - self.createTime

class Printer:
    def __init__(self,ppm):
        self._isWork = False
        self.currentTask = None
        self.pagesPerMinute = ppm
        self.timeRemaining = 0

    def is_working(self):
        return self._isWork

    def tick(self):
        if self.currentTask != None:
            self.timeRemaining -= 1
            if self.timeRemaining <= 0:
                self._isWork = False
                self.currentTask = None

    def start_next(self,nextTask):
        self.currentTask = nextTask
        self.timeRemaining = self.currentTask.get_pages()/self.pagesPerMinute*60
        self._isWork = True


if __name__ == '__main__':
    test_time = 3600
    printer_queue = sQueue()
    printer = Printer(ppm=5)
    waitTime = []

    for currentSec in range(test_time):

        if random.randrange(1,181) == 180:
            print(f"新任务生成，{currentSec}")
            newTask = Task(currentSec)
            printer_queue.enqueue(newTask)

        if printer.is_working() == False and printer_queue.is_empty() == False:
            nextTask = printer_queue.dequeue()
            printer.start_next(nextTask)
            waitTime.append(nextTask.wait_time(currentSec))
            print(f"开始打印下一个：{nextTask.get_cTime()},{nextTask.get_pages()},等待时间：{nextTask.wait_time(currentSec)}")

        printer.tick()

    avgTime = sum(waitTime)/len(waitTime)
    print(f"平均等待时间：{avgTime}sec，任务剩余数：{printer_queue.size()}")

递归

递归是解决问题的一种方法，它将问题不断地分成更小的子问题，直到子问题可以用普通的方法解决。

举例：递归求和函数

def recursionSum(numlist):
    if len(numlist) == 2:
        return numlist[0] + numlist[1]
    else:
        return numlist[0] + recursionSum(numlist[1:])

numlist = [1,2,34,4,5]
print(recursionSum(numlist))

• 递归三原则

  • 递归算法必须有基本情况：问题切分到最小时，处理并开始返回，类似循环终止条件

  • 递归算法必须改变其状态并向基本情况靠近：问题需要一步步切分的

  • 递归算法必须递归地调用自己

• Python如何实现递归函数调用：栈帧

举例：

# int转换为2-16进制字符串
def intToBinaryStr(num:int,base):
    convertStr = '0123456789ABCDEF'
    if num//base<=0:
        return convertStr[num%base]
    else:
        return intToBinaryStr(num//base,base) + convertStr[num%base]

num = 100
print(intToBinaryStr(num, 2))

用栈重写：

#非递归？
stack = SequenceStack()

def intToBinaryStr_stack(num:int,base):
    convertStr = '0123456789ABCDEF'
    if num // base <= 0:
        stack.push(convertStr[num])
    else:
        stack.push(convertStr[num%base])
        intToBinaryStr_stack(num//base,base)

这个例子展示了Python如何实现递归函数调用。当调用函数时，Python分配一个栈帧来处理该函数的局部变量。当函数返回时，返回值就在栈的顶端，以供调用者访问。

栈帧限定了函数所用变量的作用域。尽管反复调用相同的函数，但是每一次调用都会为函数的局部变量创建新的作用域。

栈帧（Stack Frame）是计算机程序在运行期间用于管理函数调用和返回的数据结构。每当函数被调用时，都会创建一个新的栈帧来保存函数的局部变量、参数、返回地址和其他相关信息。

栈帧是在程序的执行过程中动态创建和销毁的，它们以堆栈（stack）的方式组织在一起。每个栈帧都有自己的内存空间，用于存储函数调用时所需的数据。栈帧之间按照后进先出（LIFO）的原则进行管理，即最后一个创建的栈帧先被销毁。

当一个函数被调用时，当前函数的栈帧被推入堆栈中，新的栈帧被创建并成为当前栈帧，在其中执行函数的代码。当函数执行完毕后，当前栈帧被弹出堆栈，上一个栈帧恢复成当前栈帧，并继续执行其余的代码。