链表
-
基础数据类型 背包、队列、栈
- 背包:是一种不支持从中删除元素的集合数据类型,它的目的就是帮助用例收集元素并迭代遍历所有收集到的元素(用例也可以检查是否为空或者获取背包中元素的数量)。迭代的顺序不确定且与用例无关;
- 队列:队列是一种特殊的线性表,它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。
在队列这种数据结构中,最先插入的元素将是最先被删除的元素;反之最后插入的元素将最后被删除的元素,因此队列又称为“先进先出”(FIFO—first in first out)的线性表。;
- 栈:主要作用表现为一种数据结构,是只能在某一端插入和删除的特殊线性表。它按照后进先出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。
-
链表
- 定义:是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(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; } } }
-
队列实现
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; } } }
- 背包实现
背包的实现同栈的一样,仅是把pop()实现既可,push()改为add()