栈(stack), 堆(heap), 队列(queue) 是什么?

Page content

我们平时经常遇到栈(stack), 队列(queue), 堆(heap)这些词语。
像我这样不是计算机专业毕业的程序原来说,为了更好的理解这些内容,
我自己简单的整理了一下栈(stack), 堆(heap)和队列(queue)的概念。
希望有些帮助。

栈(stack), 队列(queue), 堆(heap)都是一个数据结构。

一. 栈(stack)

是计算机科学里最重要且最基础的数据结构之一。 (直接看下图更容易理解)

1.常用的几个名词

栈顶(top), 栈底(bottom), 进栈(push), 出栈(pop)。  
栈中的每个元素称为一个frame。 

2.一个很重要的特点

先进后出: FILO(First In Last Out)的原则存储数据。

它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,
需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。

图片备用地址
stack

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)。

完全二叉树比较适合用数组来存储。
用数组来存储完全二叉树是非常节省存储空间的。
因为不需要存储左右子节点的指针,单纯地通过数组的下标,就可以找到一个节点的左右子节点和父节点。

图片备用地址
heap

元素42的索引(2 = i)   
元素31的索引(4 = 2i)   
元素19的索引(5 = 2i + 1)

从图中可以看到,数组中下标为i的节点的左子节点,就是下标为2i的节点,右子节点就是下标为2i+1的节点,父节点就是下标为i/2的节点。

图片备用地址
heap

2.堆的常用方法

1.构建优先队列
2.支持堆排序
3.快速找出一个集合中的最小值(或者最大值)

堆一般用于优先级的处理和排序的时候会用到。
在这里只整理了结构性的内容,排序需要单独拿出来说明。

三. 队列(queue)

队列(Queue)与栈一样,是一种线性存储结构

1.常用的几个名词

队头(front), 队尾(rear), 入队(EnQueue), 出队(DeQueue)。  
队列中的每个元素称为一个frame。 

2.一个很重要的特点

先进先出: (FIFO, First-In-First-Out) 的原则存储数据。  

和栈一样,队列也有数组实现和链表实现两种。
两种实现都能给出快速的O(1)运行时间, 区别在于链表实现指针域要占用空间, 频繁的new和delete会消耗不少的时间开销。
数组实现的缺点是建立时要确定空间大小。

3.基于数组的队列

图片备用地址
queue

4.基于链表的队列

图片备用地址
queue

除了上面2种简单队列,还可以演化出下面的稍微复杂的循环队列,双端队列,优先队列。

5.循环队列

因为最基本的数组队列, 为了给后面进来的元素腾出空间。  
需要往前做数据迁移, 这时消耗一些不必要的资源。  
如果是环式结构,标好队头和队尾,就没必要做数据迁移了。  
但因为是固定大小的数组,可能会出现数组被填满的情况。  

6.双端队列(deque,全名double-ended queue)

一种具有队列和栈性质的抽象数据类型。  
双端队列中的元素可以从两端弹出,插入和删除操作限定在队列的两边进行。

7.优先队列

优先队列是每次入队时, 都会按照入队数据项的关键值进行排序(从大到小、从小到大),   
这样保证了关键字最小的或者最大的项始终在队头, 出队的时候优先级最高的最先出队,

最后想说一下我们常说的栈存储,堆存储是和数据结构是完全两码事。
这些内容可以继续看以下内容

java中的栈内存, 堆内存


欢迎大家的意见和交流

email: li_mingxie@163.com