本章的内容非常简单，数据结构是程序员基础中的基础，虽然简单但一定要好好掌握。鉴于我已经在编程世界中摸爬滚打多年，此处的笔记不会做得太详细，只是讲之前自己遗漏的内容进行一下补全，详细的内容可以参看专门的数据结构书籍。
栈
先进后出的结构，是最常用的一种数据结构,递归过程、函数调用等操作，全都依赖于这种栈结构。一个最简单的栈结构应该有如下四个操作:
isEmpty(): 判断当前栈中是否有元素pop(): 返回栈顶元素，并且弹出(删除)栈顶元素。top(): 返回栈顶元素，但是不弹出。push(item): 栈中压入一个新元素item。
通常来说，一个栈至少应该有两种异常情况:
- 上溢: 对空栈执行了
pop()或top()操作. - 下溢: 对已经达到容量上限的栈继续执行
push(item)操作。
Python代码的简单实现如下:
#!python
class Stack:
def __init__(self):
self.stack = []
def isEmpty(self):
return len(self.stack) <= 0:
def top(self):
if self.isEmpty() == True:
raise Exception('StackIsEmpty')
else:
x = self.stack[-1]
return x
def push(self,data):
self.stack.append(data)
def pop(self):
if self.isEmpty() == True:
raise Exception('StackIsEmpty')
else:
x = self.stack[-1]
self.stack = self.stack[:-1]
return x
def show(self):
'''
打印出栈中的数据
'''
print(self.stack)
def clear(self):
self.stack=[]
def __len__(self):
return len(self.stack)
队列
和栈结构对应的另外一种数据结构就是队列，它是一种先进先出的结构，这也是一种在实际编程过程中非常常用的数据结构。 它主要有三个操作:
isEmpty(): 判断当前队列中是否有元素.enqueue(item): 将元素item推入队列.dequeue(): 返回队首元素，并且删除队首元素.
同样的，一个队列至少应该有两种异常情况:
- 上溢: 对已经达到容量上限的队列继续执行
push(item)操作。 - 下溢: 对一个空队列执行
dequeue()操作。
Python代码的简单实现:
#!python
class Queue:
def __init__(self):
self.queue = []
def __len__(self):
return len(self.queue)
def isEmpty(self):
if len(self.queue) <= 0:
return True
else:
return False
def enqueue(self,data):
self.queue.append(data)
def dequeue(self):
if self.isEmpty() == True:
raise Exception('QueueIsEmpty')
else:
x = self.queue[0]
self.queue = self.queue[1:]
return x
def show(self):
'''
打印出队列中的信息
'''
print(self.queue)
def clear(self):
self.queue=[]
链表
链表其实和数组是比较相似的，都是将元素进行顺序存储，唯一的不同点在于链表是不能随机访问的，要想访问某个元素，必须从链表头开始向后扫描，直到找到需要的元素。
它的优点在于删除和插入操作是可以在常数时间内完成的，而对于数组来说，它的删除和插入操作在最坏情况下是\(O(n)\)代价的。
另外，需要注意的是，程序员面试过程中经常会问关于链表的题目，常见的问题有如下三个:
- 如何判断一个链表中是否存在环
- 计算链表中环的长度
- 找到环的起始位置
这三个问题连续的，其具体的分析和解答已经在我另外一篇博文中有所论述，此处就不再多言了。
树
树也是一种非常基本的数据结构，在整个计算机领域中有着广泛的应用，而且它的变种有很多，可以变得的非常复杂同时拥有非常好的性能，Linux系统的文件系统就是基于B+树这种数据结构的。
树结构其实可以讲的内容非常多，但是这里只是一个简单的笔记，我就不再深入了，相信随着阅读的深入，CLRS后面会有专门的讲解一些典型的树结构。
后记
曾今看到过一些牛人写的代码，他们把一些很复杂的算法寓于数据结构之中，一个复杂的算法被分解成一个又一个小对象，非常的优雅，可惜我的功力还不够，不能做到如此的游刃有余，只能继续默默努力了。