Java进阶-我的算法学习之路——《我的Java打怪日记》

链表

  1. 基础数据类型 背包、队列、栈

    1. 背包:是一种不支持从中删除元素的集合数据类型,它的目的就是帮助用例收集元素并迭代遍历所有收集到的元素(用例也可以检查是否为空或者获取背包中元素的数量)。迭代的顺序不确定且与用例无关;
    2. 队列:队列是一种特殊的线性表,它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。

在队列这种数据结构中,最先插入的元素将是最先被删除的元素;反之最后插入的元素将最后被删除的元素,因此队列又称为“先进先出”(FIFO—first in first out)的线性表。;

  1. 栈:主要作用表现为一种数据结构,是只能在某一端插入和删除的特殊线性表。它按照后进先出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。
  1. 链表

    1. 定义:是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。

  1. 下压堆栈代码实现

    public class StackDemo<Item> implements Iterable<Item> {
        private int N;
        private Node first;
        private class Node {
            Item item;
            Node next;
        }
        /**
         * 链表是否为空
         *
         * @return
         */
        public boolean isEmpty() {
            return N == 0;
        }
        /**
         * 链表大小
         * @return
         */
        public int size() {
            return N;
        }
        /**
         * 添加
         * @param item
         */
        public void push(Item item) {
            Node old = first;
            first = new Node();
            first.item = item;
            first.next = old;
            N++;
        }
        /**
         * 删除最上面的节点
         * @return
         */
        public Item pop() {
            Item t = first.item;
            first = first.next;
            N--;
            return t;
        }
        @Override
        public Iterator<Item> iterator() {
            return new StackDemoIterator();
        }
        private class StackDemoIterator implements Iterator<Item> {
            private Node current = first;
            @Override
            public boolean hasNext() {
                return current != null;
            }
            @Override
            public Item next() {
                Item t = current.item;
                current = current.next;
                return t;
            }
        }
    }

  2. 队列实现

    public class QueueDemo<Item> implements Iterable<Item> {
        private Node first;
        private Node last;
        private int N;
        private class Node {
            Item item;
            Node next;
        }
        /**
         * 队列事否为空
         * @return
         */
        public boolean isEntity() {
            return first == null;
        }
        /**
         * 队列的大小
         * @return
         */
        public int size() {
            return N;
        }
         /**
           * 向队列中添加元数
           * @param item
           */
          public void enqueue(Item item) {
              Node oldLast = last;
              last = new Node();
              last.item = item;
              last.next = null;
              if (isEntity()) first = last;
              else oldLast.next = last;
              N++;
          }
    
          /**
           * 取出最先进入队列的元数,并从队列中删除
           * @return
           */
          public Item dequeue() {
              Item item = first.item;
              first = first.next;
              if (isEntity()) last = null;
              N--;
              return item;
          }
    
          @Override
          public Iterator<Item> iterator() {
              return new QueueDemoIterator();
          }
          private class QueueDemoIterator implements Iterator<Item> {
              private Node current = first;
              @Override
              public boolean hasNext() {
                  return current != null;
              }
              @Override
              public Item next() {
                  Item item = current.item;
                  current = current.next;
                  return item;
              }
          }
      }
  3. 背包实现

    ​ 背包的实现同栈的一样,仅是把pop()实现既可,push()改为add()

上一篇:CSS中一个font缩写的实例


下一篇:CSS中通过import方式导入的方法