1.常用的数据结构

  • 1.数组（Array）
    数组可以说是最基本的数据结构。它是将相同类型的一些数据有序的集合在一起。
    一个数组可以包含多个同类型的数据元素。
    可以按照数据类型分为整型数组、字符型数组、浮点型数组、对象数组等。
    可以按照维度分为一维数组、二维数组、多维数组等。
  • 2.队列（Queue）
    队列也是一种特殊的线性表。只允许在一端（队尾）进行插入，在另一端（队头）进行删除。
    线性表就是各个数据元素之间具有线性关系。就像一条线一样。有头有尾，中间一个结点连着一个结点，不可间断。
    队列就像水管一样，水只能从一端流入，从另一端流出。
  • 3.链表（Linked List）
    链表的元素是按照链式存储的。也是线性结构中的一种。线性结构包括顺序结构和链表结构两种。
    这种存储在物理上并非连续的，而是每个元素包括两个部分，一部分是自己的数据，另一部分是引用域，指向下一个元素所在的地址。
    链表的逻辑关系是通过引用域串联起来的。
    线性结构中的顺序表结构在进行插入或者删除的时候，需要移动大量的数据。而链表结构最多只需要修改关联的前后两个结点的引用域即可。
    链表包含单向链表和双向链表，单向链的引用域只指向下一个元素的地址，双向链表的引用域既包含指向下一个的地址，也有指向上一个的地址。
  • 4.树（Tree）
    典型的非线性结构，有且仅有一个根结点，根结点会有一个或多个子结点。
    然后子结点也可能会有一个或多个子结点。但是，每个子结点都只会有一个父结点。
    终结点没有子结点。
    每个节点后面的所有节点组成的树称为这个结点的子树。
    二叉树是一种比较特殊的树，每一个结点最多都只有两个子结点。称为左结点和右结点。
    二叉树又包括完全二叉树（有子结点的结点都有两个子结点），和非完全二叉树（有些结点只有一个子结点）。
  • 5.堆（Heap）
    堆是一种特殊的树形结构，我们一般讨论的堆都是二叉堆。
    堆的特点是根结点的值是所有结点中最小的或者最大的。并且根结点的子树也是一个堆结构。
  • 6.栈（Stack）
    栈是一种特殊的线性表，只能在表的一端（栈顶）进行插入（入栈）和删除（出栈）操作。
    第一个插入的数据会被后面插入的不断的压入栈底。要想操作栈底的数据，只能先将其推到栈顶。
  • 7.图（Graph）
    图是另外一种非线性结构，例如通信网络、交通网络、人机关系网络，都可以归为图结构
    图可以分为无向图和有向图，
    无向图没有方向，从A到B和从B到A一样，
    有向图具有方向，就像单行道，只能从A到B，不可以逆向从B到A
    连接图的某个定点到其他所有定点的边的数量称为该顶点的度。
  • 8.散列表（Hash）
    源自散列函数（Hash function），其思想是如果在结构中存在关键字和T相等的记录，那么必定在F(T)的存储位置可以找到该记录，这样就可以不用进行比较而直接取得所查记录

2.链表结构

常用的数据结构 - 图1

  1.     /**
  2.      * 定义数据结构中的元素
  3.      */
  4.     static class DataElement {
  5.         String key;
  6.         String other_messages;
  8.         public DataElement(String key, String other_messages) {
  9.             this.key = key;
  10.             this.other_messages = other_messages;
  11.         }
  12.     }
  14.     /**
  15.      * 定义链表结构
  16.      * 链表包含单向链表和双向链表，单向链的引用域只指向下一个元素的地址，双向链表的引用域既有指向下一个的，也有指向上一个的
  17.      */
  18.     static class DataLinkedList {
  19.         DataElement dataElement;
  20.         DataLinkedList nextNode;
  21.         //我们这里只做查找算法的示例，省去添加节点，删除节点等其他方法，只做查找
  23.         /**
  24.          * 在链表的尾部追加数据
  25.          *
  26.          * @param head 链表的表头
  27.          * @param data 要添加的数据
  28.          * @return 添加后的链表元素（数据+引用域）
  29.          */
  30.         static DataLinkedList addData(DataLinkedList head, DataElement data) {
  31.             DataLinkedList node = new DataLinkedList();//新追加的结点是在结尾追加
  32.             node.dataElement = data;//保存数据
  33.             node.nextNode = null;//表尾引用域为null，
  35.             DataLinkedList element = head;
  36.             if (element == null) {//链表的表头为null，是个空链表，直接将head指向新节点
  37.                 head = node;
  38.                 return head;
  39.             }
  40.             while (element.nextNode != null) {//找到链表的尾部，如果已知链表尾部，则可以直接用，不用再从表头查找
  41.                 element = element.nextNode;
  42.             }
  43.             element.nextNode = node;//将链表的尾部指向新追加的结点
  44.             return node;
  45.         }
  47.         /**
  48.          * 在表头追加数据
  49.          *
  50.          * @param head 表头
  51.          * @param data 要添加的数据
  52.          * @return 添加后的链表元素（数据+引用域）
  53.          */
  54.         static DataLinkedList addHeadData(DataLinkedList head, DataElement data) {
  55.             DataLinkedList node = new DataLinkedList();//新追加的结点是在链表头部追加
  56.             node.dataElement = data;//保存数据
  57.             node.nextNode = head;//指向下一个元素是之前的表头
  58.             head = node;//表头变成新增的这个元素
  59.             return head;
  60.         }
  62.         /**
  63.          * 在指定的key后面追加数据
  64.          *
  65.          * @param head 表头
  66.          * @param key  元素数据的key
  67.          * @param data 要插入的新数据
  68.          * @return 插入的新元素（数据+引用）
  69.          */
  70.         static DataLinkedList insertData(DataLinkedList head, String key, DataElement data) {
  71.             DataLinkedList keyData = null;
  72.             //查找key所在的位置
  73.             DataLinkedList temp = head;
  74.             while (temp != null) {
  75.                 DataElement date = temp.dataElement;
  76.                 if (date.key.equals(key)) {//节点的关键字与传入的关键字相同
  77.                     keyData = temp;//找到key的位置
  78.                     break;
  79.                 }
  80.                 temp = temp.nextNode;//处理下一节点
  81.             }
  82.             if (keyData != null) {
  83.                 DataLinkedList node = new DataLinkedList();//新追加的结点是在链表头部追加
  84.                 node.dataElement = data;//保存数据
  85.                 node.nextNode = keyData.nextNode;//新元素指向key所指向的下一个元素
  86.                 //如果是双向链表，keyData.nextNode的元素的previousNode也要指向新添加的元素node，
  87.                 //而新添加的node的previousNode也要指向keyData
  88.                 keyData.nextNode = node;//key指向新添加的元素
  89.                 return node;
  90.             }
  91.             return null;//未找到指定key所在的位置
  92.         }
  94.         /**
  95.          * 链表结构中的查找算法
  96.          * 一般来说可以通过关键字查询，从表头依次查找
  97.          *
  98.          * @param head 链表表头
  99.          * @param key  查找的关键字
  100.          */
  101.         static DataLinkedList findData(DataLinkedList head, String key) {
  102.             DataLinkedList temp = head;//保存表头指针
  103.             while (temp != null) {//节点有效，进行查找
  104.                 DataElement date = temp.dataElement;
  105.                 if (date != null && date.key != null) {
  106.                     if (date.key.equals(key)) {//节点的关键字与传入的关键字相同
  107.                         return temp;//返回该节点指针
  108.                     }
  109.                 }
  110.                 temp = temp.nextNode;//处理下一节点
  111.             }
  112.             return null;//未找到，返回空指针
  113.         }
  115.         /**
  116.          * 删除key对应的元素
  117.          *
  118.          * @param head 表头
  119.          * @param key  数据的关键字
  120.          * @return 删除成功还是失败
  121.          */
  122.         static boolean deleteNode(DataLinkedList head, String key) {
  123.             DataLinkedList previousData = null;
  124.             DataLinkedList temp = head;
  125.             while (temp != null) {//节点有效，进行查找
  126.                 DataElement date = temp.dataElement;
  127.                 if (date != null && date.key != null) {
  128.                     if (date.key.equals(key)) {//节点的关键字与传入的关键字相同
  129.                         if (previousData != null) {
  130.                             previousData.nextNode = temp.nextNode;//将上一个节点的nextNode指向当前节点的下一个结点
  131.                             temp = null;//删除当前节点释放内存
  132.                             return true;
  133.                         }
  134.                     }
  135.                 }
  136.                 previousData = temp;
  137.                 temp = temp.nextNode;//处理下一节点
  138.             }
  139.             return false;//没有找到key对应的结点
  140.         }
  142.         /**
  143.          * 获取链表长度
  144.          *
  145.          * @param head 表头
  146.          * @return 链表长度
  147.          */
  148.         static int size(DataLinkedList head) {
  149.             DataLinkedList temp = head;
  150.             int size = 0;
  151.             while (temp != null) {
  152.                 size++;//当前结点非空，数量+1
  153.                 temp = temp.nextNode;//处理下一节点
  154.             }
  155.             return size;
  156.         }
  158.         /**
  159.          * 输出所有结点数据
  160.          *
  161.          * @param head 表头
  162.          */
  163.         static void showAllNode(DataLinkedList head) {
  164.             DataLinkedList temp = head;
  165.             while (temp != null) {
  166.                 //输出当前结点的数据
  167.                 DataElement date = temp.dataElement;
  168.                 if (date != null && date.key != null) {
  169.                     System.out.printf("data:{key:%s,otherMessage:%s}%n",
  170.                             date.key, date.other_messages);
  171.                 }
  173.                 temp = temp.nextNode;//处理下一节点
  174.             }
  175.         }
  177.     }

调用：

  1.         DataLinkedList head = new DataLinkedList();
  2.         head.dataElement = new DataElement("key1", "otherMessage1");
  3.         head.nextNode = null;
  4.         System.out.printf("开始在头部追加结点keyHead.%n");
  5.         head = DataLinkedList.addHeadData(head, new DataElement("keyHead", "otherMessageHead"));
  6.         if (head != null) {
  7.             System.out.printf("链表头部追加结点成功！%n");
  8.         }
  9.         System.out.printf("开始在尾部追加结点key2.%n");
  10.         DataLinkedList node = DataLinkedList.addData(head, new DataElement("key2", "otherMessage2"));
  11.         if (node != null) {
  12.             System.out.printf("链表尾部追加结点成功！%n");
  13.         }
  14.         System.out.printf("开始在key1后插入结点key3.%n");
  15.         node = DataLinkedList.insertData(head, "key1", new DataElement("key3", "otherMessage3"));
  16.         if (node != null) {
  17.             System.out.printf("在key1后插入结点成功！%n");
  18.         }
  19.         System.out.printf("开始查找key2所在的结点，%n");
  20.         node = DataLinkedList.findData(head, "key2");
  21.         if (node != null) {
  22.             System.out.printf("key2所在的结点:data:{key:%s,otherMessage:%s},nextNodeAddress:{%s}%n",
  23.                     node.dataElement.key, node.dataElement.other_messages, node.nextNode);
  24.         }
  25.         int size = DataLinkedList.size(head);
  26.         System.out.printf("链表中总长度为：%d%n", size);
  27.         System.out.printf("链表中的所有元素:%n");
  28.         DataLinkedList.showAllNode(head);
  29.         boolean delete = DataLinkedList.deleteNode(head, "key2");
  30.         System.out.printf("链表中删除key2元素的结果：%b%n", delete);

输出：

  1. 开始在头部追加结点keyHead.
  2. 链表头部追加结点成功！
  3. 开始在尾部追加结点key2.
  4. 链表尾部追加结点成功！
  5. 开始在key1后插入结点key3.
  6. 在key1后插入结点成功！
  7. 开始查找key2所在的结点，
  8. key2所在的结点:data:{key:key2,otherMessage:otherMessage2},nextNodeAddress:{null} 
  9. 链表中总长度为：4
  10. 链表中的所有元素:
  11. data:{key:keyHead,otherMessage:otherMessageHead}
  12. data:{key:key1,otherMessage:otherMessage1}
  13. data:{key:key3,otherMessage:otherMessage3}
  14. data:{key:key2,otherMessage:otherMessage2}
  15. 链表中删除key2元素的结果：true

3.队列结构

常用的数据结构 - 图2

由于队列结构比较简单，就不做详细的示例，代码可以参考下面的栈结构，将栈顶作为队头，并增加队尾标记，以及对队头、队尾的相关操作即可。

4.树结构

常用的数据结构 - 图3

常用的数据结构 - 图4

常用的数据结构 - 图5

常用的数据结构 - 图6

  1.     /**
  2.      * 定义二叉树结构
  3.      */
  4.     static class TreeDate {
  5.         String data;
  6.         TreeDate leftData;
  7.         TreeDate rightData;
  9.         /**
  10.          * 初始化二叉树
  11.          *
  12.          * @param rootData 根结点的数据
  13.          * @return TreeDate二叉树的树根
  14.          */
  15.         static TreeDate initTree(String rootData) {
  16.             TreeDate treeRoot = new TreeDate();
  17.             treeRoot.data = rootData;
  18.             treeRoot.leftData = null;
  19.             treeRoot.rightData = null;
  20.             return treeRoot;
  21.         }
  23.         /**
  24.          * 添加树结点
  25.          *
  26.          * @param treeRoot    树的跟结点
  27.          * @param parentData  要添加的结点位于哪个父结点下
  28.          * @param leftOrRight 作为父结点的左子树（1）还是右子树（2）
  29.          * @param nodeData    要添加的结点数据
  30.          */
  31.         static void addNode(TreeDate treeRoot, String parentData, int leftOrRight, String nodeData) {
  32.             TreeDate parentNode = findData(treeRoot, parentData);//根据key找到父结点
  33.             if (parentNode != null) {
  34.                 TreeDate node = new TreeDate();
  35.                 node.data = nodeData;
  36.                 node.leftData = null;
  37.                 node.rightData = null;
  38.                 switch (leftOrRight) {
  39.                     case 1:
  40.                         if (parentNode.leftData != null) {
  41.                             System.out.printf("父节点的左子树不为空！");
  42.                         } else {
  43.                             parentNode.leftData = node;
  44.                         }
  45.                         break;
  46.                     case 2:
  47.                         if (parentNode.rightData != null) {
  48.                             System.out.printf("父节点的右子树不为空！");
  49.                         } else {
  50.                             parentNode.rightData = node;
  51.                         }
  52.                         break;
  53.                 }
  54.             } else {
  55.                 System.out.printf("父节点[%s]未找到！", parentData);
  56.             }
  58.         }
  60.         /**
  61.          * 二叉树查找算法
  62.          * 遍历二叉树中的每一个结点，逐个比较数据。
  63.          *
  64.          * @param treeNode 树结点,首次调用传入树的根结点
  65.          * @param data     要查找的结点
  66.          * @return TreeDate 查找结果
  67.          */
  68.         static TreeDate findData(TreeDate treeNode, String data) {
  69.             if (treeNode == null) {
  70.                 return null;
  71.             } else {
  72.                 if (treeNode.data.equals(data)) {
  73.                     return treeNode;
  74.                 }
  75.                 if (findData(treeNode.leftData, data) != null) {//递归查找左结点
  76.                     return findData(treeNode.leftData, data);
  77.                 }
  78.                 if (findData(treeNode.rightData, data) != null) {//递归查找右结点
  79.                     return findData(treeNode.rightData, data);
  80.                 }
  81.             }
  82.             return null;
  83.         }
  85.         /**
  86.          * 获取左子树
  87.          *
  88.          * @param treeNode 树的一个结点
  89.          * @return 左子树
  90.          */
  91.         static TreeDate leftNode(TreeDate treeNode) {
  92.             if (treeNode != null) {
  93.                 return treeNode.leftData;
  94.             }
  95.             return null;
  96.         }
  98.         /**
  99.          * 获取右子树
  100.          *
  101.          * @param treeNode 树的一个结点
  102.          * @return 右子树
  103.          */
  104.         static TreeDate rightNode(TreeDate treeNode) {
  105.             if (treeNode != null) {
  106.                 return treeNode.rightData;
  107.             }
  108.             return null;
  109.         }
  111.         /**
  112.          * 判断空树
  113.          *
  114.          * @param treeRoot 根结点
  115.          * @return true空树，false不是空树
  116.          */
  117.         static boolean isEmpty(TreeDate treeRoot) {
  118.             return treeRoot == null;
  119.         }
  121.         /**
  122.          * 计算二叉树的深度，计算二叉树的最大层数
  123.          *
  124.          * @param treeNode 从根结点开始
  125.          * @return 二叉树的最大层数int
  126.          */
  127.         static int depth(TreeDate treeNode) {
  128.             int depthLeft = 0, depthRight = 0;
  129.             if (treeNode == null) {
  130.                 return 0;
  131.             }
  132.             if (treeNode.leftData != null) {
  133.                 depthLeft = depth(treeNode.leftData);
  134.             }
  135.             if (treeNode.rightData != null) {
  136.                 depthRight = depth(treeNode.rightData);
  137.             }
  139.             if (depthLeft > depthRight) {
  140.                 return depthLeft + 1;
  141.             }
  142.             return depthRight + 1;
  143.         }
  145.         /**
  146.          * 清空二叉树
  147.          * 对于JVM，这个clearTree,是unnecessary的，不必要的
  148.          *
  149.          * @param treeNode 根结点
  150.          */
  151.         static void clearTree(TreeDate treeNode) {
  152.             if (treeNode != null) {
  153.                 clearTree(treeNode.leftData);
  154.                 clearTree(treeNode.rightData);
  155.                 treeNode = null;//释放内存
  156.             }
  157.         }
  159.         /**
  160.          * 显示当前结点的数据
  161.          *
  162.          * @param treeNode 当前结点
  163.          */
  164.         static void nodeData(TreeDate treeNode) {
  165.             System.out.printf(" %s->", treeNode.data);
  166.         }
  168.         /**
  169.          * 遍历二叉树（按层遍历）
  170.          *
  171.          * @param treeRoot 根结点
  172.          */
  173.         static void traverseTreeAccordingToLevel(TreeDate treeRoot) {
  174.             int head = 0, tail = 0;
  175.             final int MAX_LENGTH = 100;//树的最大结点数
  176.             TreeDate p;
  177.             TreeDate[] q = new TreeDate[MAX_LENGTH];//定义一个顺序栈
  178.             if (treeRoot != null) {//如果队首引用不为空
  179.                 tail = (tail + 1) % MAX_LENGTH;//计算循环队列队尾序号
  180.                 q[tail] = treeRoot;//将二叉树根引用进队
  181.             }
  182.             while (head != tail) {//队列不为空，进行循环
  183.                 head = (head + 1) % MAX_LENGTH;//计算循环队列的队首序号
  184.                 p = q[head];//获取队首元素
  185.                 nodeData(p);//处理队首元素
  186.                 if (p.leftData != null) {//存在左子树
  187.                     tail = (tail + 1) % MAX_LENGTH;//计算循环队列的队尾序号
  188.                     q[tail] = p.leftData;//将左子树引用进队
  189.                 }
  190.                 if (p.rightData != null) {
  191.                     tail = (tail + 1) % MAX_LENGTH;
  192.                     q[tail] = p.rightData;
  193.                 }
  194.             }
  195.         }
  197.         /**
  198.          * 遍历二叉树（先序遍历算法）
  199.          * 先按照中序遍历左子树，再访问根结点，最后按中序遍历右子树
  200.          *
  201.          * @param treeRoot 根结点
  202.          */
  203.         static void traverseTreeAccordingToPerorder(TreeDate treeRoot) {
  204.             if (treeRoot != null) {
  205.                 nodeData(treeRoot);//显示结点数据
  206.                 traverseTreeAccordingToPerorder(treeRoot.leftData);
  207.                 traverseTreeAccordingToPerorder(treeRoot.rightData);
  208.             }
  209.         }
  211.         /**
  212.          * 遍历二叉树（中序遍历算法）
  213.          * 先访问根结点，再按照先序遍历左子树，最后按先序遍历右子树
  214.          *
  215.          * @param treeRoot 根结点
  216.          */
  217.         static void traverseTreeAccordingToInorder(TreeDate treeRoot) {
  218.             if (treeRoot != null) {
  219.                 traverseTreeAccordingToInorder(treeRoot.leftData);
  220.                 nodeData(treeRoot);//显示结点数据
  221.                 traverseTreeAccordingToInorder(treeRoot.rightData);
  222.             }
  223.         }
  225.         /**
  226.          * 遍历二叉树（后序遍历算法）
  227.          * 先按照后序遍历左子树，再按后序遍历右子树，最后访问根结点
  228.          *
  229.          * @param treeRoot 根结点
  230.          */
  231.         static void traverseTreeAccordingToPostorder(TreeDate treeRoot) {
  232.             if (treeRoot != null) {
  233.                 traverseTreeAccordingToPostorder(treeRoot.leftData);
  234.                 traverseTreeAccordingToPostorder(treeRoot.rightData);
  235.                 nodeData(treeRoot);//显示结点数据
  236.             }
  237.         }
  238.     }

调用：

  1.         TreeDate rootNode = TreeDate.initTree("根结点");
  2.         TreeDate.addNode(rootNode, "根结点", 1, "左结点1");
  3.         TreeDate.addNode(rootNode, "根结点", 2, "右结点2");
  4.         TreeDate.addNode(rootNode, "左结点1", 1, "左结点1.1");
  5.         TreeDate.addNode(rootNode, "左结点1", 2, "右结点1.2");
  6.         TreeDate.addNode(rootNode, "右结点2", 1, "左结点2.1");
  7.         TreeDate.addNode(rootNode, "左结点2.1", 1, "左结点2.1.1");
  8.         TreeDate node = TreeDate.findData(rootNode, "右结点2");
  9.         if (node != null) {
  10.             System.out.printf("找到右结点2，");
  11.             TreeDate leftNode = TreeDate.leftNode(node);
  12.             TreeDate rightNode = TreeDate.rightNode(node);
  13.             if (leftNode != null) {
  14.                 System.out.printf("其左子树为:%s\t", leftNode.data);
  15.             }
  16.             if (rightNode != null) {
  17.                 System.out.printf("右子树为:%s", rightNode.data);
  18.             }
  19.             System.out.printf("%n");
  20.         }
  21.         int depth = TreeDate.depth(rootNode);
  22.         System.out.printf("树深度:%d%n", depth);
  23.         System.out.printf("按层遍历算法:%n");
  24.         TreeDate.traverseTreeAccordingToLevel(rootNode);
  25.         System.out.printf("%n先序遍历算法:%n");
  26.         TreeDate.traverseTreeAccordingToPerorder(rootNode);
  27.         System.out.printf("%n中序遍历算法:%n");
  28.         TreeDate.traverseTreeAccordingToInorder(rootNode);
  29.         System.out.printf("%n后序遍历算法:%n");
  30.         TreeDate.traverseTreeAccordingToPostorder(rootNode);
  31.         System.out.printf("%n");
  32.         boolean isEmpty = TreeDate.isEmpty(rootNode);
  33.         System.out.printf("是否是空树：%b%n", isEmpty);
  34.         System.out.printf("清空树%n");
  35.         TreeDate.clearTree(rootNode);

输出：

  1. 找到右结点2，其左子树为:左结点2.1    
  2. 树深度:4
  3. 按层遍历算法:
  4.  根结点-> 左结点1-> 右结点2-> 左结点1.1-> 右结点1.2-> 左结点2.1-> 左结点2.1.1->
  5. 先序遍历算法:
  6.  根结点-> 左结点1-> 左结点1.1-> 右结点1.2-> 右结点2-> 左结点2.1-> 左结点2.1.1->
  7. 中序遍历算法:
  8.  左结点1.1-> 左结点1-> 右结点1.2-> 根结点-> 左结点2.1.1-> 左结点2.1-> 右结点2->
  9. 后序遍历算法:
  10.  左结点1.1-> 右结点1.2-> 左结点1-> 左结点2.1.1-> 左结点2.1-> 右结点2-> 根结点->
  11. 是否是空树：false
  12. 清空树

5.栈结构

常用的数据结构 - 图7

  1.     /**
  2.      * 定义数据结构中的元素
  3.      */
  4.     static class DataElement {
  5.         String key;
  6.         String other_messages;
  8.         public DataElement(String key, String other_messages) {
  9.             this.key = key;
  10.             this.other_messages = other_messages;
  11.         }
  12.     }
  13.     /**
  14.      * 定义栈结构
  15.      */
  16.     static class Stack {
  17.         static final int MAX_LENGTH = 10;//当前栈表的最大长度
  18.         DataElement[] stackData = new DataElement[MAX_LENGTH];//栈表数据
  19.         int top;//栈顶
  21.         /**
  22.          * 初始化栈
  23.          */
  24.         static Stack initStack() {
  25.             Stack s = new Stack();
  26.             s.top = 0;
  27.             return s;
  28.         }
  30.         /**
  31.          * 判断栈是否为空
  32.          *
  33.          * @param stack Stack
  34.          * @return true是空栈，false栈不为空
  35.          */
  36.         static boolean isEmpty(Stack stack) {
  37.             return stack.top == 0;
  38.         }
  40.         /**
  41.          * 栈是不是已满
  42.          *
  43.          * @param stack Stack
  44.          * @return true栈已满，false栈未满
  45.          */
  46.         static boolean isFull(Stack stack) {
  47.             return stack.top == MAX_LENGTH;
  48.         }
  50.         /**
  51.          * 清空栈
  52.          *
  53.          * @param stack Stack
  54.          */
  55.         static void clear(Stack stack) {
  56.             stack.top = 0;
  57.         }
  59.         /**
  60.          * 释放栈所占空间
  61.          *
  62.          * @param stack Stack
  63.          */
  64.         static void free(Stack stack) {
  65.             if (stack != null) {
  66.                 stack = null;
  67.             }
  68.         }
  70.         /**
  71.          * 入栈
  72.          *
  73.          * @param stack   Stack
  74.          * @param element DataElement
  75.          * @return 0入栈失败，1入栈成功
  76.          */
  77.         static int push(Stack stack, DataElement element) {
  78.             if (stack.top + 1 > MAX_LENGTH) {
  79.                 System.out.printf("栈溢出！");
  80.                 return 0;
  81.             }
  82.             stack.stackData[++stack.top] = element;//将element入栈，入栈后栈顶（top）+1
  83.             return 1;
  84.         }
  86.         /**
  87.          * 出栈
  88.          *
  89.          * @param stack Stack
  90.          * @return 栈顶的DataElement
  91.          */
  92.         static DataElement pop(Stack stack) {
  93.             if (stack.top == 0) {
  94.                 System.out.print("栈已空！");
  95.                 return null;
  96.             }
  97.             return stack.stackData[stack.top--];//将栈顶元素出栈，出栈后栈顶（top）-1
  98.         }
  100.         /**
  101.          * 查看栈数据，由于栈只能操作栈顶数据，所以查看栈的数据只能看栈顶的元素
  102.          *
  103.          * @param stack Stack
  104.          * @return 栈顶的DataElement
  105.          */
  106.         static DataElement peek(Stack stack) {
  107.             if (stack.top == 0) {
  108.                 System.out.print("栈已空！");
  109.                 return null;
  110.             }
  111.             return stack.stackData[stack.top];
  112.         }
  114.     }

调用：

  1.         Stack stack = Stack.initStack();
  2.         System.out.printf("栈是不是空栈：%b%n", Stack.isEmpty(stack));
  3.         DataElement element = new DataElement("s1", "s1_other");
  4.         int push = Stack.push(stack, element);
  5.         System.out.printf("入栈结果：%d%n", push);
  6.         element = new DataElement("s2", "s2_other");
  7.         push = Stack.push(stack, element);
  8.         System.out.printf("入栈结果：%d%n", push);
  9.         element = new DataElement("s3", "s3_other");
  10.         push = Stack.push(stack, element);
  11.         System.out.printf("入栈结果：%d%n", push);
  12.         System.out.printf("栈是不是空栈：%b%n", Stack.isEmpty(stack));
  13.         System.out.printf("栈是不是满栈：%b%n", Stack.isFull(stack));
  14.         DataElement dataElement = Stack.peek(stack);
  15.         assert dataElement != null;
  16.         System.out.printf("查看栈：{%s,%s}%n", dataElement.key, dataElement.other_messages);
  17.         dataElement = Stack.pop(stack);
  18.         assert dataElement != null;
  19.         System.out.printf("出栈：{%s,%s}%n", dataElement.key, dataElement.other_messages);
  20.         dataElement = Stack.pop(stack);
  21.         assert dataElement != null;
  22.         System.out.printf("出栈：{%s,%s}%n", dataElement.key, dataElement.other_messages);
  23.         Stack.clear(stack);
  24.         System.out.printf("清空栈后栈是不是空栈：%b%n", Stack.isEmpty(stack));
  25.         Stack.free(stack);//释放栈空间

输出：

  1. 栈是不是空栈：true
  2. 入栈结果：1
  3. 入栈结果：1
  4. 入栈结果：1
  5. 栈是不是空栈：false
  6. 栈是不是满栈：false
  7. 查看栈：{s3,s3_other}
  8. 出栈：{s3,s3_other}
  9. 出栈：{s2,s2_other}
  10. 清空栈后栈是不是空栈：true

6.图结构

常用的数据结构 - 图8

常用的数据结构 - 图9

常用的数据结构 - 图10

图结构的代码参考 常用算法指南(三)查找算法 ：5. 图结构中的查找算法