堆栈

堆(heap)

堆是先进先出

性质

堆的实现通过构造二叉堆（binary heap），实为二叉树的一种；由于其应用的普遍性，当不加限定时，均指该数据结构的这种实现。这种数据结构具有以下性质。

• 任意节点小于（或大于）它的所有后裔，最小元（或最大元）在堆的根上（堆序性）。
• 堆总是一棵完全树。即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入。

实现

• 堆的主要操作是插入和删除最小元素(元素值本身为优先级键值，小元素享有高优先级)
• 在插入或者删除操作之后，我们必须保持该实现应有的性质: 1. 完全二叉树 2. 每个节点值都小于或等于它的子节点

栈(Stack)

栈：先进后出的数据结构。先进去的数据在底部，最后取出，后进去的数据在顶部，最先被取出。

栈常用操作：

Stack()         创建栈
push(item)      将数据item放在栈的顶部
pop()             返回栈顶部数据，并从栈中移除该数据
peek()           返回栈顶部数据，但不移除
size()            返回栈的大小
is_empty()       返回栈是否为空

堆和栈的区别

• 堆栈空间分配区别：

1.栈（操作系统）：由操作系统自du动分配释放 ，存放函zhi数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈；

2.堆（操作系统）： 一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收，分配方式倒是类似于链表。

• 堆栈缓存方式区别：

1.栈使用的是一级缓存， 他们通常都是被调用时处于存储空间中，调用完毕立即释放；

2.堆是存放在二级缓存中，生命周期由虚拟机的垃圾回收算法来决定（并不是一旦成为孤儿对象就能被回收）。所以调用这些对象的速度要相对来得低一些。

• 堆栈数据结构区别：

堆（数据结构）：堆可以被看成是一棵树，如：堆排序；

栈（数据结构）：一种先进后出的数据结构。

队列的实现

在这里，我们用顺序表来实现队列

相关操作：

Queue() 创建一个空的队列
enqueue(item) 往队列中添加一个item
dequeue() 从队列头部删除一个元素
is_empty() 判断一个队列是否为空
size() 返回队列的大小

程序实现：

class Queue:
    def __init__(self):
        self.items = []

    def is_empty():
        return self.items == []

    def enqueue(self,item):
        self.items.insert(0,item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

if __name__ == '__main__':
    queue = Queue()