由于节后有面试，现在又把以前的学习的数据结构和算法知识拿出来重新温习一下，之所以要温习，因为上周去面试的时候发现很多问题自己有思路，但是用代码实现却觉得比较困难，大多数觉得很轻松很简单的数据结构和算法题，对一些细节却模糊了。温故而知新，以前大多数是c或者java实现的，因为最近用python比较多，那就用python来实现以下。
栈，是计算机中比较重要的算法，其特点具有后进先出。事实上，向python和javascript这样的解释性语言或者说具有辅助编译性特点的语言。其类型中数组的操作就具有栈的特点。比如Array.push,Array.pop等方法。因为是数组，所以栈的结构是顺序性的，也就是默认申请一个数组，动态的对数组进行管理。对数组的动态管理是有成本的，频繁的删除、插入操作会导致栈的性能较差，因此大多数栈会使用链表来实现，因为对os来讲向堆中申请内存是比较充裕的。下面就来看看链表栈的实现：
from abc import ABCMeta, abstractmethod,abstractproperty class IStack: __metaclass__=ABCMeta @abstractmethod def Push(self):pass @abstractmethod def Pop(self):pass @abstractmethod def Top(self):pass @abstractproperty def IsEmpty(self):pass @abstractproperty def Length(self):pass @abstractmethod def Display(self):pass
首先定义了一个IStack的接口（虽然python不想csharp那样具有定义接口的定制语法，但是python给使用者提供了一种类似接口的方式特性，比如twisted就是zope的实现）。其中，abc模块包含了一个叫做ABCMeta的metaclass。这个metaclass由内置的isinstance()和issubclass()特别处理，并包含一批会被Python开发人员广泛用到的基础抽象基类。将来的Python版本可能会加入更多的抽象基类。定义一个接口的好处就是在实现IStack这个接口的类会检查是否完整基础了接口，否则会抛出异常。因为python是弱类型的。
同时，还需要定义每个节点的数据接口，以方便我们的操作
class Node(object):def __init__(self,elem=None,node=None): self.__element=elem self.__next=node @property def Element(self):return self.__element @Element.setter def Element(self,val):self.__element=val @property def Next(self):return self.__next @Next.setter def Next(self,val):self.__next=val
里面有关于Element和Next的属性，以上的python的属性是通过decorate实现的。当然有很多其他的方式，比如动态的__getter__方式，这样写无非可以是代码更清晰。
链表栈的实现
from IStack import IStack from Node import Node class LinkStack(IStack): def __init__(self): self.__top=None self.__length=0 def Push(self,element): node=Node(elem=element,node=self.__top) self.__top=node self.__length+=1 return True def Pop(self): if(self.__length==0):raise Exception('栈为空') elem=self.__top.Element self.__top=self.__top.Next self.__length-=1 return elem def Top(self): if(self.__length==0):raise Exception('栈为空') return self.__top.Element def IsEmpty(self): if(self.__length==0):return True else:return False def Length(self): return self.__length def Display(self): data=[] cur=self.__top while(cur): data.append(cur.Element) cur=cur.Next return data
这里面__top和__length记录栈的边界和目前大小，以方便其他操作。