欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

python数据结构-数组/列表/栈/队列及实现

程序员文章站 2022-11-22 07:55:10
首先 我们要分清楚一些概念和他们之间的关系 数组(array) 表(list) 链表(linked list) 数组链表(array list) 队列(queue) 栈(stack) list列表 array数组 python中内置list数据结构 存放的数据类型可以不同。 但是有个缺点 list存 ......

首先

我们要分清楚一些概念和他们之间的关系

数组(array)  表(list)  链表(linked list)  数组链表(array list)   队列(queue)  栈(stack)

python数据结构-数组/列表/栈/队列及实现

list列表

array数组

python中内置list数据结构 存放的数据类型可以不同。

但是有个缺点 list存放的是数据的索引也就是指针 这需要数据的原有存储加上数据的指针 增加了消耗

 

python中numpy库的array 存放单一类型数据 

 python中数组并不是基本数据类型 但是可以调用array库 或者numpy库使用数组array 

array库只能创建一维数组 numpy中的数组适用性非常广  建议使用numpy

1 import array
2 arr=array.array('i',[1,2,3,4])   #创建数组
3 print(arr,type(arr))

相互转换

1 import numpy as np
2 arr=np.array([1,2,3,4])   #创建数组
3 li=arr.tolist()           #数组转换为列表
4 new_arr=np.array(li)      #列表转数组
5 print(arr,type(arr))
6 print(li,type(li))
7 print(new_arr,type(new_arr))
#输出
[1 2 3 4] <class 'numpy.ndarray'>
[1, 2, 3, 4] <class 'list'>
[1 2 3 4] <class 'numpy.ndarray'>

可以发现list元素之间有逗号隔开,array之间没有符号隔开

 

queue队列  -只允许在一段进行删除操作在另一端进行插入操作的数组结构

stack栈  -删除与插入操作在同一端进行的数组结构

特点

queue -先进先出 fifo first in first out

stack  -先进后出 filo first in last out

共同点:栈和队列都是一种操作受限制的线性表

用途:栈:表达式的括号匹配问题,迷宫求解

           队列:银行排队,操作系统进程问题,舞伴问题

 

python实现队列:(有注释)

 1 class node(object):
 2     def __init__(self,val):  #节点传入值
 3         self.next=none       #每个节点定义2个属性 next指向下一个位置
 4         self.val=val         #                  val 节点的值
 5 
 6 class queue(object):
 7     def __init__(self):
 8         self.first=none      #每个队列定义2个属性 first删除端
 9         self.last=none       #                   last插入端
10 
11     def enqueue(self,n):
12         n=node(n)
13         if(self.first==none): #如果队列为空
14             self.first=n
15             self.last=n
16         else:                 #如果队列不为空
17             self.last.next=n  #插入端的指向为n
18             self.last=n       #插入端的最后一个值为n
19 
20     def dequeue(self):
21         if (self.first==none):
22             return none
23         else:
24             reval=self.first.val
25             self.first=self.first.next  #将删除端的第一个指定为下一个
26             return reval
27     def allquit(self):             # allquit作用:队列中元素放入list中方便打印
28         alist=[]
29         while (self.first!=none):       #循环
30             temp=self.first.val         #和dequeue的操作相同
31             self.first=self.first.next
32             alist.append(temp)
33         return alist
34 
35 if __name__ == "__main__":
36     q=queue()
37     q.enqueue(1)
38     q.enqueue(2)
39     q.enqueue(3)
40     q.dequeue()
41     print(q.allquit())

python实现栈:(有注释)

 1 class node(object):
 2     def __init__(self,val):
 3         self.next=none
 4         self.val=val
 5 class stack(object):
 6     def __init__(self):
 7         self.top=none              #和queue不同栈删除插入都在一端 所以只定义一个位置
 8 
 9     def push(self,n):
10         n=node(n)
11         if(self.top==none):        #如果栈为空
12             self.top=n
13         else:
14             n.next=self.top        #插入元素的下一个为顶格元素
15             self.top = n           #顶格元素为插入值
16 
17     def pop(self):                 #删除顶格元素
18         if(self.top==none):        #如果栈为空
19             return none
20         else:
21             temp=self.top.val
22             self.top=self.top.next #新的顶格元素为老顶格元素的上一个
23             return temp
24 
25     def allquit(self):             #打印栈方法
26         alist=[]
27         while(self.top!=none):     #循环
28             temp=self.top.val      #和pop()方法操作相同
29             self.top=self.top.next
30             alist.append(temp)
31         print(alist)
32 
33 if __name__== "__main__" :
34     s=stack()
35     s.push(1)
36     s.push(3)
37     s.push(5)
38     s.pop()
39     s.allquit()