数据结构与算法(3)栈与递归

dushine00 2020-01-12

1 栈的理解

  1. 栈是一个数据集合,可以理解为只能在一端进行插入或者删除操作的列表。

  2. 栈的特点:后进先出

  3. 栈的基本操作

    1. 进栈:push
    2. 出栈:pop
    3. 取栈顶:gettop
  4. def brace_match(s):
        stack = []
        d = {"(":")", "[":"]", "{":"}"}
        for ch in s:
            if ch in {'(','[','{'}:
                stack.append(ch)
            elif len(stack) == 0:
                print('多了右括号%s' % ch)
                return False
            elif d[stack[-1]] == ch:
                stack.pop()
            else:
                print('括号%s处不匹配' % ch)
                return False
        if len(stack) == 0:
            return True
        else:
            print('剩余括号未匹配')
            return False

2 队列的理解

队列的理解:

  1. 队列(queue)是一个数据集合,仅允许在列表一端进行插入,另一端进行删除。
  2. 进行插入的一端称为队尾(rear),插入动作被称为进队或者入队。
  3. 进行删除的一端称为队头(front),删除动作称为出队。
  4. 队列的性质:先进先出(first-in,first-out)
  5. 双向队列:队列两端都允许进行进队和出队操作

队列的内置模块:from collections import deque

  1. 创建队列:queue = deque(li)
  2. 进队:append
  3. 出队: popleft
  4. 双向队列首进队: appendleft
  5. 双向队列尾进队:pop

3 递归实现斐波那契函数

# 递归:
def my_num(x):
    if x == 1:
        return 1
    elif x == 2:
        return 2
    else:
        return my_num(x-2) + my_num(x-1)
for i in range(1, 10):
    print(my_num(i))

4 车辆调度问题

def VehicleReecorder(Trucks, k):
    BufferRails = []
    for i in range(k):
        BufferRails.append([])
    currentCarriage = 1
    for i in Trucks:
        if i == currentCarriage:
            print(f'{i}')
            currentCarriage += 1
            continue
        else:
            for buffer in BufferRails:
                if not buffer:
                    buffer.append(i)
                    break
                else:
                    if min(buffer) > i:
                        buffer.append(i)
                        break
    for buffer_list in BufferRails:
        for i in range(len(buffer_list)):
            last = buffer_list.pop()
            if last == currentCarriage:
                print(f'{i}')
                currentCarriage +=1

相关推荐