黑客：什么是图的拓扑排序？什么是关键线路？什么是栈、队列？

一、拓扑排序

一、拓扑排序

对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

二、关键线路

指设计中从输入到输出经过的延时最长的逻辑路径。比如工程施工经常就会用到这种原理，来绘制施工进度计划表。

三、栈

通俗地讲，栈就像一个箱子，后放上去的数据，可以先出来，不让操作的叫栈底，进行操作的是栈顶。它的存储结构：最常采用的是顺序存储和链式存储，其中顺序存储用数组，链式存储用链表。

栈的顺序操作：初始化，判空，进栈，出栈，得到栈顶元素，销毁栈…….

链式存储结构最大的好处就是没有空间的限制，通过指针指向将结点像一个链子一样把结点链接，那么栈的同样可以用于链式存储结构。由于栈只是栈顶在做插入和删除操作，所以栈顶应该放在单链表的头部。另外，都有了栈顶在头部了，单链表中的头结点也就失去了意义，通常对于链栈来说，是不需要头结点的。

顺序栈和链栈的时间复杂度都为O(1). 如果栈的使用过程中元素变化不可预期，有时会很大，有时会很小，则选择使用链栈。反之，如果它的变化在可控范围内，选择使用顺序栈比较好。

四、队列

队列就像是箱子底下破了，是先进先出，有出口和入口，先进去可以先出来。允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。存储结构可以分为顺序队列和循环队列。

建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front，它指向队头元素；另一个是队尾指针rear，它指向下一个入队元素的存储位置，如图所示

循环队列，在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦rear指针增1或front指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。自己真从MaxSize-1增1变到0，可用取余运算rear%MaxSize和front%MaxSize来实现。这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。除了一些简单应用之外，真正实用的队列是循环队列。