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 binstringprint 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 Queuedef 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())