|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
栈是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。换句话说，栈的修改是按先进后出的原则进行的。因此，栈又称为先进后出（FILO，或后进先出）的线性表。在栈中，进行插入和删除操作的一端称为栈顶（top），相应地，另一端称为栈底（bottom）。不含数据元素的栈称为空栈。
|
|
|
|
|
|
（1）初始化栈initStack（S）：创建一个空栈S。
|
|
|
|
（2）判栈空isEmpty（S）：当栈S为空栈时返回“真”，否则返回“假”。
|
|
|
|
（3）入栈push（S，x）：将元素x加入栈顶，并更新栈顶指针。
|
|
|
|
（4）出栈pop（S）：将栈顶元素从栈中删除，并更新栈顶指针。
|
|
|
|
（5）读栈顶元素top（S）：返回栈顶元素的值，但不修改栈顶指针。
|
|
|
|
可以用一维数组作为栈的存储空间，同时设置指针top指示栈顶元素的位置。在这种存储方式下，需要预先定义或申请栈的存储空间，也就是说栈空间的容量是有限的。因此一个元素入栈时，需要判断是否栈满，若栈满（即栈空间中没有空闲单元），则元素入栈会发生上溢现象。
|
|
|
|
用链表作为存储结构的栈称为链栈。由于栈中元素的插入和删除仅在栈顶一端进行，因此不必另外设置头指针，链表的头指针就是栈顶指针。链栈的表示如下图所示，其类型定义如下：
|
|
|
|
|
|
|
|
|
|
以栈中元素类型为整型为例，实现栈基本运算的函数定义如下。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Java语言起源于Oak语言，Oak语言被设计成能运行在设备的嵌入式芯片上。
|
|
|
|
Java编译成伪代码，这需要一个虚拟机来对其进行解释，Java的虚拟机在几乎每一种平台上都可以运行。这实质上使得开发是与机器独立无关的，并且提供了通用的可移植性。
|
|
|
|
Java把类的概念和接口的概念区分开来，并试图通过只允许接口的多继承来克服多继承的危险。
|
|
|
|
Java的异常处理机制与C++的try/throw/catch相类似，但更加严密。在Java中，通过声明轻型线程来处理并发性，这些线程通过副作用和同步协议进行通信。
|
|
|
|
Java Beans是组件，即类及其所需资源的集合，它们主要被设计用来提供定制的GUI小配件。
|
|
|
|
Java中关于面向对象概念的术语有对象、类、方法、实例变量、消息、子类和继承。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n个元素的序列{k1, k2, …, kn｝当且仅当满足以下的关系式时才称之为堆： 或 ，并相应地称为小顶堆或大顶堆。
|
|
|
|
|
|
判断堆的办法是把序列看成一棵完全二叉树，若树中所有非终端节点的值均不大于（或不小于）其左右孩子的节点的值，则该序列为堆。
|
|
|
|
|
|
堆的典型应用是堆排序。堆排序首先要根据待排序记录的关键字建立初始堆，其方法是：将待排序的关键字按层序遍历方式分放到一棵完全二叉树的各个节点中，显然所有i>［n/2］的节点ki都没有子节点，以这样的ki为根的子树已经是堆，因此初始堆可从完全二叉树的第（i=［n/2］）个节点开始，通过调整，逐步使以k[n/2]， k［n/2]-1, …, k2, k1为根的子树满足堆的定义。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
