1，栈，后进先出，多用于反转
Python里面实现栈，就是把list包装成一个类，再添加一些方法作为栈的基本操作。
栈的实现：
class Stack(object):
#初始化栈为空列表
def __init__(self):
self.items = [] #self.__items = []可以把items变成私有属性 #判断栈是不是为空
def isEmpty(self):
return len(self.items) ==0 #返回栈顶的元素
def peek(self):
return self.items[-1] #返回栈的大小
def size(self):
return len(self.items) #给栈加入新元素
def push(self,a):
self.items.append(a) #删除栈顶的元素
def pop(self):
return self.items.pop()
栈应用实例：十进制转化为二进制
def divideBy2(decNumber):
remstack = Stack() #实例化一个栈，因为需要栈结构来存储数据，也是为了用到栈方法 while decNumber > 0:
rem = decNumber%2 #除二倒取余法，最后反转拼接所有的余数
remstack.push(rem) #余数依次放到栈中储存起来
decNumber = decNumber // 2 binstring = ''
while not remstack.is_empty():
binstring = binstring + str(remstack.pop()) #反序获取栈中的元素 return binstring print divideBy2(10)
2 队列queue
队列实际上就是一个包装了的列表，从list[0]添加新元素，用pop()来获取，符合先进先出的规则。
class Queue:
def __init__(self):
self.items = [] def isEmpty(self):
return self.items == [] def enqueue(self,item): #添加一个新元素item到队列的开头，这叫队尾
self.items.insert(0,item) def dequeue(self): #减去一个最后一个元素，这叫队首
return self.items.pop() def size(self):
return len(self.items) def show(self): #自主添加的，好跟踪查看队列里有啥
return self.items
队列应用实例：热土豆
#就是一队人围着圈报数，从0开始，报到m就出局，看谁活最久。
from pythonds.basic.queue import Queue def HotPotato(namelist,num):
simqueue = Queue()
for name in namelist:
simqueue.enqueue(name) #把先namelist添加到队列中去，ps：从下标是0的位置开始添加，整个插入完成以后序列就反过来了
while simqueue.size()>1:
for i in range(num): #
simqueue.enqueue(simqueue.dequeue())
#从列表的末尾减去什么就把什么添加到列表开头
simqueue.dequeue() #哪个排最后哪个就是热土豆，直接出局
return simqueue.dequeue() print HotPotato(['lili','jiajia','dahu','wangba','daqing','tamato','potato','hehe'],3)
3 双端队列有点类似于列表，不多赘述
4，链表
基本链表的实现： #链表是环环相扣形成的序列结构，每一环首先定义self变量，其次要标记下一个变量。所以访问的时候只能按照顺序来。
class Node:
def __init__(self,initdata):
self.data = initdata
self.next = None def getData(self):
return self.data def getNext(self):
return self.next def setData(self,newdata):
self.data = newdata def setNext(self,newnext):
self.next = newnext
无序链表：
class UnorderedList:
def __init__(self):
self.head = None #表示链表的头部不引用任何内容
def isEmpty(self):
return self.head == None
def add(self,item): #链表中有两个属性，一个是本身，一个是next，
temp = Node(item) #这个设定了链表本身，也就是data,无序链表也是由node构成的
temp.setNext(self.head) #这个设定了next
self.head = temp #把链表的data参数设定为无序列表的头----head
def size(self):
current = self.head
count = 0
while current != None:
count = count +1
current = current.getNext()
return count
def search(self,item):
current = self.head
found = False
while current != None and not found:
if current.getData() == item:
found = True
else:
current = current.getNext()
return found
def remove(self,item):
current = self.head
previous=None
found = False
while not found: #找到要删除的item以后会跳出循环，此时current.getData()是要删除的项目
if current.getData()==item:
found=True
else:
previous=current
current=current.getNext()
if previous ==None: #只有一种情况下，previous会是None，那就是要删除的是第一个，也就是想删除self.head
self.head=current.getNext()
else:
previous.setNext(current.getNext()) # 本来的指向是previous.getData()--item(也就是previous.getNext(),还是current.getData())--current.getNext()
#要想删除item，那就把previous的指向改成current.getNext()，这样item就不能在原来的链表中瞎掺和了
有序链表：
class OrderedList:
def __init__(self):
self.head = None def isEmpty(self): #同无序列表
return self.head == None def show(self):
current = self.head
while current != None:
print current.getData()
current = current.getNext() def __iter__(self):
current = self.head
while current != None:
yield current.getData()
current = current.getNext() def size(self): #同无序列表
current = self.head
count = 0
while current != None:
count +=1
current =current.getNext()
return count def search(self,item): #默认从小到大排列的链表
current = self.head
found = False
stop = False
while current != None and not found and not stop:
if current.getData() == item:
found = True
else:
if current.getData() > item:
stop = True
else:
current = current.getNext()
return found def add(self,item):
current = self.head
previous = None
stop = False
while current != None and not stop: #有一个以上元素的情况
if current.getData() > item:
stop = True
else:
previous = current
current = current.getNext() #不用担心元素添加到最后的情况，因为链表中自带None封住了两头 temp = Node(item)
if previous == None: #添加到链表头的情况
temp.setNext(self.head)
self.head=temp
else:
temp.setNext(current)
previous.setNext(temp) def remove(self, item):
current = self.head
previous = None
found = False
while not found:
# 迭代每一项，得到要删除的那个，并且通过赋值前一个执行删除
if current.getData() == item:
found = True
else:
previous = current
current = current.getNext()
if previous == None:
# 如果删除的是第一项，那么把第二项变成第一项，否则给previous赋值
self.head = current.getNext()
else:
previous.setNext(current.getNext())