逻辑数据结构包括：线形结构、树形结构、图形结构、集合；存储结构包括：顺序存储、链式存储、索引存储、散列存储。
同一种逻辑结构可以有四种存储结构，不同的存储结构增、删、查、改的速度不同。逻辑结构与存储结构排列组合，就得到4*4=16种结构。
在C/C++中，栈和队列的常用实现方式为数组和链表，存储方式分别是：顺序存储和链式存储。
在Python中，栈和队列的常用实现方式为list，存储方式是索引，实现起来要比C/C++简单的多，而且大小可以动态扩展，存取也非常方便，可以说它集成了顺序存储
和链式存储的优点，索引表本身就是顺序存储啊，就是数组，它是怎样实现动态扩展长度的呢？这个就不知道了，有空看看Python的实现代码源代码。Python也是可以
用链式存储实现线性结构的，见下面的代码，但没有list实现方便。C/C++中的内置类型（类）中没有索引存储的，你也许想到指针数组，的确，它是一种索引结构，但用
它不容易实现线性结构，因为当你添加元素时，要先用变量创建该元素，而且变量名与线性表中已有元素的变量名不能相同，每次添加都要用不同的变量名，看来这种方
式不行，那我们可以动态molloc，用指针指向该molloc，然后通过指针给新元素赋值，然后再把指针指向的地址保存在链表数组中，这样是可以，但太麻烦了。在Python
中，编程语言自动帮你实现了这个过程，这对用户来说就简单的一比了。总得来说，用list实现栈和队列和两种方法，一种是实例对象的数据属性是list，另一种是类直接
继承list类。第二种方法简单，但由于继承了list，而list提供了很多对外接口，如extend()等，这些接口其实是标准栈不应该有的。所以建议用第一种方法实现。
Stack类--实现1（推荐）
class Stack(list):
def __init__(self):
self.__stack = [] def is_empty(self):
return not bool(len(self)) def push(self,data):
self.__stack.append(data) def pop(self):
if len(self.__stack)>0:
return self.__stack.pop() def peek(self):
if len(self.__stack)>0:
return self.__stack[-1] def get_length(self):
return len(self.__stack)
Stack类--实现2（不建议使用）
class Stack(list):
def is_empty(self):
return not bool(len(self)) def push(self,data):
self.append(data) def pop(self):
if len(self)>0:
return self.pop() def peek(self):
if len(self)>0:
return self[-1] def get_length(self):
return len(self)
Stack类--实现3（链式存储，不建议使用）
class Node(object):
def __init__(self,data):
self.data = data
self.next = None class Stack(object):
def __init__(self,head_node):
self.top = head_node
self.bottom = head_node def push(self,node):
node.next = self.top
self.top = node def pop(self):
if self.top == None:
return None
else:
key = self.top
self.top = self.top.next
if self.top == None:
self.bottom = None
return key s = Stack(Node(12))
s.push(Node(13))
s.push(Node(15))
s.push(Node(18))
s.push(Node(2))
while True:
a = s.pop()
if a != None:
print a.data
continue
else:
break
Queue类--实现1（推荐）
class Queue(object):
def __init__(self):
self.__queue = [] def is_empty(self):
return not bool(len(self.__queue)) def peek(self):
if len(self.__queue)>0:
return self.__stack[0] def enqueue(self,node):
self.__queue.append(node) def dequeue(self):
if len(self.__queue)>0:
return self.__queue.pop(0) def get_length(self):
return len(self.__queue)
Queue类--实现2（不建议使用）
class Queue(list):
def is_empty(self):
return not bool(len(self)) def peek(self):
if len(self)>0
return self[0] def enqueue(self,node):
self.append(node) def dequeue(self,node):
if len(self)>0:
return self.pop(0) def get_length(self):
return len(self)
BST类（二叉树类）
我们一般很少用一般二叉树，而是用进一步约束的二叉树，如二叉搜索树、红黑树等，这些树是一般二叉树的子类，
所以二叉树有的方法，这些方法都可以有。
class Node(object):
def __init__(self,data):
self.data = data
self.__left = None
self.__right = None
self.__parent = None @property
def left(self):
return self.__left @left.setter
def left(self,node):
if node is None or type(node) is Node:
self.__left = node
if type(node) is Node:
node.parent = self
else:
raise Exception,'left node must be None or Node type' @property
def right(self):
return self.__right @right.setter
def right(self,node):
if node is None or type(node) is Node:
self.__right = node
if type(node) is Node:
node.parent = self
else:
raise Exception,'right node must be None or Node type' @property
def parent(self):
return self.__parent @parent.setter
def parent(self,node):
if node is None or type(node) is Node:
self.__parent = node
else:
raise Exception,'parent node must be None or Node type' class BST(object):
def __init__(self):
self.__root = None @property
def root(self):
return self.__root @root.setter
def root(self,node):
if node is None or type(node) is Node:
self.__root = node
if type(node) is Node:
node.parent = None
else:
raise Exception,'parent node must be None or Node type' def pre_order(self,node):
#递归结束点
if node == None:
return []
#分支结点
data = [node.data]
left = self.pre_order(node.left)
right = self.pre_order(node.right)
return data +left +right def in_order(self,node):
if node == None:
return [] left = self.pre_order(node.left)
data = [node.data]
right = self.pre_order(node.right)
return left + data + right def post_order(self,node):
if node == None:
return [] left = self.pre_order(node.left)
right = self.pre_order(node.right)
data = [node.data]
return left + right + data #查找以node为根结节的树的最大关键值节点
def find_max(self,node):
if node == None:
return None
p = node
while True:
if p.right != None:
p = p.right
continue
else:
break
return p def find_min(self,node):
if node == None:
return None
p = node
while True:
if p.left != None:
p = p.left
continue
else:
break
return p def search(self,node,key):
# 跟二分查找的递归方式非常像
#结束点
if node == None:
return None #分支节点
if key == node.data:
return node
if key > node.data:
return self.search(node.right,key)
else:
return self.search(node.left,key) def insert(self,root,new_node):
#结束点
if new_node.data > root.data:
if root.right == None:
root.right = new_node
return True
if new_node.data == root.data:
return False
if new_node.data < root.data:
if root.left == None:
root.left = new_node
return True #分支节点
if new_node.data > root.data:
if root.right != None:
branch_ret = self.insert(root.right,new_node)
if new_node.data < root.data:
if root.left != None:
branch_ret = self.insert(root.left,new_node)
return branch_ret def delete(self,node):
#这个方法比较繁琐，有空再写
pass