本章的内容非常简单，数据结构是程序员基础中的基础，虽然简单但一定要好好掌握。鉴于我已经在编程世界中摸爬滚打多年，此处的笔记不会做得太详细，只是讲之前自己遗漏的内容进行一下补全，详细的内容可以参看专门的数据结构书籍。

栈

先进后出的结构，是最常用的一种数据结构,递归过程、函数调用等操作，全都依赖于这种栈结构。一个最简单的栈结构应该有如下四个操作:

• 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)\)代价的。

另外，需要注意的是，程序员面试过程中经常会问关于链表的题目，常见的问题有如下三个:

1. 如何判断一个链表中是否存在环
2. 计算链表中环的长度
3. 找到环的起始位置

这三个问题连续的，其具体的分析和解答已经在我另外一篇博文中有所论述，此处就不再多言了。

树

树也是一种非常基本的数据结构，在整个计算机领域中有着广泛的应用，而且它的变种有很多，可以变得的非常复杂同时拥有非常好的性能，Linux系统的文件系统就是基于B+树这种数据结构的。

树结构其实可以讲的内容非常多，但是这里只是一个简单的笔记，我就不再深入了，相信随着阅读的深入，CLRS后面会有专门的讲解一些典型的树结构。

后记

曾今看到过一些牛人写的代码，他们把一些很复杂的算法寓于数据结构之中，一个复杂的算法被分解成一个又一个小对象，非常的优雅，可惜我的功力还不够，不能做到如此的游刃有余，只能继续默默努力了。

Share on: Twitter ❄ Facebook ❄ Email

---

Comments

So what do you think? Did I miss something? Is any part unclear? Leave your comments below

Comments

comments powered by Disqus

---