首页 > 代码库 > python的数据类型

python的数据类型

栈:

  栈(Stack)是一个数据集合,可以理解为只能在一端进入或删除操作的列表

  栈的特点:后进先出(last-in,first-out)

  栈的概念:

    1.栈顶

    2.栈底

  栈的基本操作:

    1.进栈(压栈):push

    2.出栈:pop

    3.取栈顶:gettop

  栈的python实现

  不需要自己定义,使用列表结构即可。

    进栈函数:append

    出栈函数:pop

    查看栈顶函数:li[-1]

  栈的应用--括号匹配问题

    括号匹配问题:给一个字符串,其中包含小括号、中括号、大括号,求该字符串中的括号是否匹配。

    1.()()[]{}          匹配

    2.([{()}])      匹配

    3.[](         不匹配

    4.[(])        不匹配

 1 def check_kuohao(s):
 2     stack = []
 3     for char in s :
 4         if char in {(,[,{}:
 5             stack.append(char)
 6         elif char == ")":
 7             if len(stack) > 0 and stack[-1] == (:
 8                 stack.pop()
 9             else:
10                 return False
11         elif char == "]":
12             if len(stack) > 0 and stack[-1] == [:
13                 stack.pop()
14             else:
15                 return False
16         elif char == "}":
17             if len(stack) > 0 and stack[-1] == {:
18                 stack.pop()
19             else:
20                 return False
21     if len(stack) == 0:
22         return True
23     else:
24         return False

 

队列:

  队列(Queue)是一个数据集合,仅允许在列表的一端进行插入,另一端进行删除

  进行插入的一端成为队尾(rear),插入动作称为进队或入队

  进行删除的一端称为队头(front),删除动作称为出队

  队列的性质:先进先出(First-in,First-out)

  双向队列:队列的两端都允许进行进队和出队操作。

  使用方法: from collections import deque

    创建队列:queue = deque(li)

    进队:append

    出队:popleft

    双向队列队首进队:appendleft

    双星队列队尾进队:pop

  队列的实现原理

技术分享

技术分享

技术分享

技术分享

技术分享

 1 maze = [
 2     [1,1,1,1,1,1,1,1,1,1],
 3     [1,0,0,1,0,0,0,1,0,1],
 4     [1,0,0,1,0,0,0,1,0,1],
 5     [1,0,0,0,0,1,1,0,0,1],
 6     [1,0,1,1,1,0,0,0,0,1],
 7     [1,0,0,0,1,0,0,0,0,1],
 8     [1,0,1,0,0,0,1,0,0,1],
 9     [1,0,1,1,1,0,1,1,0,1],
10     [1,1,0,0,0,0,0,0,0,1],
11     [1,1,1,1,1,1,1,1,1,1]
12 ]
13 
14 dirs = [
15     lambda x,y:(x+1,y),
16     lambda x,y:(x-1,y),
17     lambda x,y:(x,y+1),
18     lambda x,y:(x,y-1),
19 ]
20 
21 def mgmaze(x1,y1,x2,y2):
22     stack=[]
23     stack.append((x1,y1))
24     while len(stack)>0 :  #只要栈不为空
25         curNode = stack[-1]
26         if curNode[0]==x2 and curNode[1] ==y2:
27             #到达终点打印路径
28             for p in stack:
29                 print(p)
30             return True
31         for dir in dirs:
32             nextNode = dir(*curNode)
33             if maze[nextNode[0]][nextNode[1]] == 0:
34                 stack.append(nextNode)
35                 maze[nextNode[0]][nextNode[1]] = 2 #2表示已走过
36                 break
37         else:
38             stack.pop()
39             maze[curNode[0]][curNode[1]] = 2  #死路一条
40     return False
41 
42 mgmaze(1,1,8,8)

 队列实现迷宫方法

 1 from collections import deque
 2 maze = [
 3     [1,1,1,1,1,1,1,1,1,1],
 4     [1,0,0,1,0,0,0,1,0,1],
 5     [1,0,0,1,0,0,0,1,0,1],
 6     [1,0,0,0,0,1,1,0,0,1],
 7     [1,0,1,1,1,0,0,0,0,1],
 8     [1,0,0,0,1,0,0,0,0,1],
 9     [1,0,1,0,0,0,1,0,0,1],
10     [1,0,1,1,1,0,1,1,0,1],
11     [1,1,0,0,0,0,0,0,0,1],
12     [1,1,1,1,1,1,1,1,1,1]
13 ]
14 
15 dirs = [
16     lambda x,y:(x+1,y),
17     lambda x,y:(x-1,y),
18     lambda x,y:(x,y+1),
19     lambda x,y:(x,y-1),
20 ]
21 def mgmaze(x1,y1,x2,y2):     #队列方法
22     queue = deque()
23     path = []
24     queue.append((x1,y1,-1))
25     while len(queue) > 0:
26         curNode = queue.popleft()
27         path.append(curNode)
28 
29         if curNode[0] == x2 and curNode[1] == y2:  #找到终点
30             realpath = []
31             p = len(path) -1
32             while path[p][2] != -1:
33                 realpath.append((path[p][0],path[p][1]))
34                 p = path[p][2]
35             realpath.append((path[p][0],path[p][1]))
36             realpath.reverse()
37             print(realpath)
38             return True
39 
40         for dir in dirs:
41             nextNode = dir(curNode[0],curNode[1])
42             if maze[nextNode[0]][nextNode[1]] == 0 : #能走
43                 queue.append((nextNode[0],nextNode[1],len(path)-1))
44                 maze[nextNode[0]][nextNode[1]] == 2
45     return False
46 mgmaze(1,1,8,8)

 

python的数据类型