首先
我们要分清楚一些概念和他们之间的关系
数组（array) 表（list) 链表（linked list) 数组链表（array list) 队列（queue) 栈（stack)
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()