栈(stack), 堆(heap), 队列(queue) 是什么？
我们平时经常遇到栈(stack), 队列(queue), 堆(heap)这些词语。
像我这样不是计算机专业毕业的程序原来说，为了更好的理解这些内容，
我自己简单的整理了一下栈(stack), 堆(heap)和队列(queue)的概念。
希望有些帮助。
栈(stack), 队列(queue), 堆(heap)都是一个数据结构。
一. 栈(stack)
是计算机科学里最重要且最基础的数据结构之一。 (直接看下图更容易理解)
1.常用的几个名词
栈顶(top), 栈底(bottom), 进栈(push), 出栈(pop)。
栈中的每个元素称为一个frame。
2.一个很重要的特点
先进后出: FILO（First In Last Out）的原则存储数据。
它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶,
需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。
3.最经典的计算机应用是函数调用
每个进程都会有一个栈，每个frame中记录了调用函数的参数，自动变量和返回地址。
当该函数调用一个新的函数时，栈中会 push一个frame。
当函数执行完毕返回时，该frame会pop，从而进入调用该函数的原函数，继续执行。
4.比较常用的应用场景
1) 子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，
直到子程序执行完后再将地址取出，以回到原来的程序中。
2) 递归的调用：可以用来在函数调用的时候存储断点，
储存下一个指令的地址外，也将参数、区域变量等数据存入栈中。
3) 表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。
4) 二叉树的遍历。
5) 图形的深度优先(depth一first)搜索法。
二. 堆(heap)
堆(Heap)是计算机科学中的一种特别的完全二叉树。(直接看下图更容易理解)
维基百科是这么解释的:
若是满足以下特性，即可称为堆：
“给定堆中任意节点P和C，若P是C的父节点，那么P的值会小于等于（或大于等于）C的值”。
若父节点的值恒小于等于子节点的值，此堆称为最小堆(min heap);
反之，若父节点的值恒大于等于子节点的值，此堆称为最大堆(max heap)。
在堆中最顶端的那一个节点，称作根节点（root node），根节点本身没有父节点(parent node)
堆总是满足下列性质：
堆中某个节点的值总是不大于或不小于其父节点的值
1.常用的几个名词
插入insert: 向堆中插入一个新元素
删除(取顶)delete: 删除堆顶元素
上浮swim: 子节点优先级比父节点高时，子节点需要由下而上。
下沉sink: 子节点优先级比父节点高时，父节点需要由上而下。
数组建堆heapify: 使打乱的堆再次成为有序堆的一种算法过程。
2.堆结构的简单说明
堆的一个经典的实现是完全二叉树(complete binary tree)。
这样实现的堆成为二叉堆(binary heap)。
完全二叉树比较适合用数组来存储。
用数组来存储完全二叉树是非常节省存储空间的。
因为不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点。
元素42的索引(2 = i)
元素31的索引(4 = 2i)
元素19的索引(5 = 2i + 1)
从图中可以看到，数组中下标为i的节点的左子节点，就是下标为2i的节点，右子节点就是下标为2i+1的节点，父节点就是下标为i/2的节点。
2.堆的常用方法
1.构建优先队列
2.支持堆排序
3.快速找出一个集合中的最小值（或者最大值）
堆一般用于优先级的处理和排序的时候会用到。
在这里只整理了结构性的内容，排序需要单独拿出来说明。
三. 队列(queue)
队列（Queue）与栈一样，是一种线性存储结构
1.常用的几个名词
队头(front), 队尾(rear), 入队(EnQueue), 出队(DeQueue)。
队列中的每个元素称为一个frame。
2.一个很重要的特点
先进先出: (FIFO, First-In-First-Out) 的原则存储数据。
和栈一样，队列也有数组实现和链表实现两种。
两种实现都能给出快速的O(1)运行时间, 区别在于链表实现指针域要占用空间, 频繁的new和delete会消耗不少的时间开销。
数组实现的缺点是建立时要确定空间大小。
3.基于数组的队列
4.基于链表的队列
除了上面2种简单队列，还可以演化出下面的稍微复杂的循环队列，双端队列，优先队列。
5.循环队列
因为最基本的数组队列, 为了给后面进来的元素腾出空间。
需要往前做数据迁移, 这时消耗一些不必要的资源。
如果是环式结构，标好队头和队尾，就没必要做数据迁移了。
但因为是固定大小的数组，可能会出现数组被填满的情况。
6.双端队列(deque，全名double-ended queue)
一种具有队列和栈性质的抽象数据类型。
双端队列中的元素可以从两端弹出，插入和删除操作限定在队列的两边进行。
7.优先队列
优先队列是每次入队时, 都会按照入队数据项的关键值进行排序(从大到小、从小到大),
这样保证了关键字最小的或者最大的项始终在队头, 出队的时候优先级最高的最先出队，
最后想说一下我们常说的栈存储，堆存储是和数据结构是完全两码事。
这些内容可以继续看以下内容
欢迎大家的意见和交流
email: li_mingxie@163.com