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

首先

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

数组（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()