以“栈”为底（一）

一时失言乱红尘 2022-08-21 01:08 105阅读 0赞

以“栈”为底

写在前面：

作为年轻人中的亿万分之一，“好高骛远”在骨子里根生蒂固。谨以此文勉励自己，戒“骄”戒“躁”，尽力做到务实求真。

“栈”作为常用的数据结构，为大家所熟知。现以栈为例，谈谈自己的学习心得。

汇点成线

“栈”者，以序存物之地。物之所入，是为入栈；物之所出，是为出栈。

栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表。

基本算法：

1．进栈（PUSH）算法

①若TOP≥n时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）；

②置TOP=TOP+1（栈指针加1，指向进栈地址）；

③S(TOP)=X，结束（X为新进栈的元素）；

2．退栈（POP）算法

①若TOP≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作②)；

②X=S(TOP)，（退栈后的元素赋给X）：

③TOP=TOP-1，结束（栈指针减1，指向栈顶）。

我们都知道，程序运行离不开存储硬件。一般的，将程序内存分为两部分，静态内存区与动态内存区。静态内存区以栈为数据结构，动态内存区以堆为数据结构。静态内存区主要存储静态量，常量，函数入口（严格意义上讲，函数也是变量）等等。而程序的动态内存分配，则在堆上进行。为什么要用栈呢？我们都知道，常量在程序运行中频繁使用，而且是随机的，无序的。而栈只能对其栈顶（底）元素操作，相对于数组而言，其随机访问性几乎为零。在粗略学习过“编译原理”之后，我们就会知道，数组在访问过程中也是要按照首地址来计算目标地址。但相对于栈而言，它能一步到位。这里我们主要强调数组与栈在寻址过程的差异。在学习过“计算机组成原理”之后，我们会知道，程序在运行过程中，总是在某一时刻，随机的，高频的访问某一地址块。计算机在设计时，按照这个原理，设计了高速缓存块，将程序访问的某一地址所属地址块，全部从内存调入到高速缓存块中。现在的内存硬件，几乎都以逻辑运算的方式来取值，例如，y=1^x,当x为1时，y=1，当x=0时，y=0，这样就可以将存储在内存中的数据取出（当然，具体的读取是以电荷的方式读取，这里不做说明）。而高速缓存器的存取速度相当快，几乎可以忽略掉读取时间。所以数组与栈的速度差别主要在寻址，而数组地址的计算与栈的依次寻址相比，速度之慢难以言表。（计算一个数值，要经历多步的寄存器变换。）举个例子，在计算2+3的时候可以有两种算法，一是通过以2为基数，一个一个数，数三次；二是通过运算。栈是第一种，数组是第二种。由于对于数组和栈来说，地址总量是非常小的，依次遍历要比计算快很多。所以在读取速度上，栈完胜数组。这里要注意，我们常说的随机读取快，指的是代码操作便捷，而非实际的内存操作。在学习过“操作系统”之后，我们知道，现有的操作系统，在处理内存时，大多以分页式来管理内存块。导致内存块之间不总是连续的。因此，栈的扩展的灵活性就可以在此处凸显，而数组做不到这一点。综上所述，在读取速度上，容量扩展上，栈都明显的优于数组。

这就是在所谓的集点成线。汇，隐含有杂乱无章之意。将无序的知识点“汇”到一起，是第一步。

集线成面

栈、队、数组都是以线型结构存储数据。与此相对应的有树型结构，图型结构。所谓图形，即数据间的关系是多对多的。所谓树形，即数据间的关系是一对多的。所谓线性，即数据间是无关的，或是一对一的。当然，三种线性关系，都可以通过线型关系来表示。

我曾经遇到这样一个问题：现有二维数组中的一个元素，它与它周围八个元素有着某种联系。当时，我采用了标记的方式，给每个元素附加一堆标记，来标记其与周围元素的关系。然而，在后续的修改与使用中，复杂的逻辑关系，让我跪服。后来，采用了以链表为基础的八叉树的数据结构。但我在使用过程中我发现，这棵树太大了，根本不可能存储。再后来我采用了二维数组，才将这棵树存储起来。

因此，在程序设计过程中，要尽量使程序接近人的思维逻辑。学院的副院长，在上课时曾说，让代码以人的思维运作，让问题简单了一半。我曾经为别人调试过一个程序，他将程序中的bool用int来表示，导致我在阅读他的程序时，觉得莫名其妙。词不达意，遗祸非浅。除此之外，透彻的了解数据间的关系，灵活的使用实现方式，都可以使问题简单，简单，更简单。

这个过程，我称之为：集线成面。是第二步。