线性表示最常⽤⽽且最为简单的⼀种数据结构，⼀个线性表示 n 个数据元素的有限序列，有以下特点：
线性表包括下⾯⼏种：
数组（Array） 是一种很常见的数据结构。它由相同类型的元素（element）组成，并且是使用一块连续的内存来存储。
在Java 中表示为：
int[] nums = new int[100];
int[] nums = {1,2,3,4,5};
Object[] Objects = new Object[100];
数组是⼀种线性的结构，⼀般在底层是连续的空间，存储相同类型的数据，由于连续紧凑结构以及天然索引⽀持，查询数据效率⾼。
假设我们知道数组a 的第 1 个值是 地址是 296，⾥⾯的数据类型占 2 个 单位，那么我们如果期望得到第 5 个： 296+（5-1）*2 = 304 , O(1) 的时间复杂度就可以获取到。更新的本质也是查找，先查找到该元素，就可以动⼿更新了：
但是如果期望插⼊数据的话，需要移动后⾯的数据，⽐如下⾯的数组，插⼊元素6 ，最差的是移动所有的元素，时间复杂度为O(n)
⽽删除元素则需要把后⾯的数据移动到前⾯，最差的时间复杂度同样为O(n)
总结：数组的特点是：提供随机访问 并且容量有限。
假如数组的长度为 n。
import java.util.Arrays;
public class MyArray {
private int[] data;
private int elementCount;
private int length;
public MyArray(int max) {
length = max;
data = new int[max];
elementCount = 0;
}
public void add(int value) {
if (elementCount == length) {
length = 2 * length;
data = Arrays.copyOf(data, length);
}
data[elementCount] = value;
elementCount++;
}
public int find(int searchKey) {
int i;
for (i = 0; i 链表（LinkedList） 虽然是一种线性表，但是并不会按线性的顺序存储数据，使用的不是连续的内存空间来存储数据。
我们可以看到数组是需要连续的空间，这⾥⾯如果空间⼤⼩只有 2 ，放到第 3 个元素的时候，就不得不扩容，不仅如此，还得拷⻉元素。⼀些删除，插⼊操作会引起较多的数据移动的操作。
链表，也就是链式数据结构，由于它不要求逻辑上相邻的数据元素在物理位置上也相邻，所以它没有顺序存储结构所具有的缺点，但是同时也失去了通过索引下标直接查找元素的优点。
链表的插入和删除操作的复杂度为 O(1) ，只需要知道目标位置元素的上一个元素即可。但是，在查找一个节点或者访问特定位置的节点的时候复杂度为 O(n) 。
使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但链表不会节省空间，相比于数组会占用更多的空间，因为链表中每个节点存放的还有指向其他节点的指针。除此之外，链表不具有数组随机读取的优点。
常见链表分类：
单链表 单向链表只有一个方向，结点只有一个后继指针 next 指向后面的节点。因此，链表这种数据结构通常在物理内存上是不连续的。我们习惯性地把第一个结点叫作头结点，链表通常有一个不保存任何值的 head 节点(头结点)，通过头结点我们可以遍历整个链表。尾结点通常指向 null。
单向链表的查找更新⽐较简单，我们看看插⼊新节点的具体过程（这⾥只展示中间位置的插⼊，头尾插⼊⽐较简单）：
那如何删除⼀个中间的节点呢？下⾯是具体的过程：
或许你会好奇， a5 节点只是指针没有了，那它去哪⾥了？
如果是Java 程序，垃圾回收器会收集这种没有被引⽤的节点，帮我们回收掉了这部分内存，但是为了加快垃圾回收的速度，⼀般不需要的节点我们会置空，⽐如 node = null , 如果在C++ 程序中，那么就需要⼿动回收了，否则容易造成内存泄漏等问题。
循环链表 其实是一种特殊的单链表，和单链表不同的是循环链表的尾结点不是指向 null，而是指向链表的头结点。
双向链表 包含两个指针，一个 prev 指向前一个节点，一个 next 指向后一个节点。
双向循环链表 最后一个节点的 next 指向 head，而 head 的 prev 指向最后一个节点，构成一个环。
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
public class MyList {
private ListNode head;
private ListNode tail;
private int size;
public MyList() {
this.head = null;
this.tail = null;
this.size = 0;
}
public void add(T element) {
add(size, element);
}
public void add(int index, T element) {
if (index size) {
throw new IndexOutOfBoundsException("超出链表⻓度范围");
}
ListNode current = new ListNode(element);
if (index == 0) {
if (head == null) {
head = current;
tail = current;
} else {
current.next = head;
head = current;
}
} else if (index == size) {
tail.next = current;
tail = current;
} else {
ListNode preNode = get(index - 1);
current.next = preNode.next;
preNode.next = current;
}
size++;
}
public ListNode get(int index) {
if (index = size) {
throw new IndexOutOfBoundsException("超出链表⻓度");
}
ListNode temp = head;
for (int i = 0; i = size) {
throw new IndexOutOfBoundsException("超出链表节点范围");
}
ListNode node = null;
if (index == 0) {
node = head;
head = head.next;
} else if (index == size - 1) {
ListNode preNode = get(index - 1);
node = tail;
preNode.next = null;
tail = preNode;
} else {
ListNode pre = get(index - 1);
pre.next = pre.next.next;
node = pre.next;
}
size--;
return node;
}
public void update(int index, T element) {
if (index = size) {
throw new IndexOutOfBoundsException("超出链表节点范围");
}
ListNode node = get(index);
node.val = element;
}
public void display() {
ListNode temp = head;
while (temp != null) {
System.out.print(temp.val + " -> ");
temp = temp.next;
}
System.out.println("");
}
}
链表如果搜索，是很麻烦的，如果这个节点在最后，需要遍历所有的节点，才能找到，查找效率实在太低，有没有什么好的办法呢？
办法总⽐问题多，但是想要绝对的” 多快好省“是不存在的，有舍有得，计算机的世界⾥，充满哲学的味道。既然搜索效率有问题，那么我们不如给链表排个序。排序后的链表，还是只能知道头尾节点，知道中间的范围，但是要找到中间的节点，还是得⾛遍历的⽼路。如果我们把中间节点存储起来呢？存起来，确实我们就知道数据在前⼀半，还是在后⼀半。⽐如找7 ，肯定就从中间节点开始找。如果查找4 ,就得从头开始找，最差到中间节点，就停⽌查找。
但是如此，还是没有彻底解决问题，因为链表很⻓的情况，只能通过前后两部分查找。不如回到原则：空间和时间，我们选择时间，那就要舍弃⼀部分空间,我们每个节点再加⼀个指针，现在有 2 层指针（注意：节点只有⼀份，都是同⼀个节点，只是为了好看，弄了两份，实际上是同⼀个节点，有两个指针，⽐如 1 ，既指向2，也指向5）：
两层指针，问题依然存在，那就不断加层，⽐如每两个节点，就加⼀层：
这就是跳表了，跳表的定义如下：
跳表(SkipList，全称跳跃表)是⽤于有序元素序列快速搜索查找的⼀个数据结构，跳表是⼀个随机化的数据结构，实质就是⼀种可以进⾏⼆分查找的有序链表。跳表在原有的有序链表上⾯增加了多级索引，通过索引来实现快速查找。跳表不仅能提⾼搜索性能，同时也可以提⾼插⼊和删除操作的性能。它在性能上和红⿊树，AVL树不相上下，但是跳表的原理⾮常简单，实现也⽐红⿊树简单很多。
主要的原理是⽤空间换时间，可以实现近乎⼆分查找的效率，实际上消耗的空间，假设每两个加⼀层，1 + 2 + 4 + ... + n = 2n-1 ,多出了差不多⼀倍的空间。你看它像不像书的⽬录，⼀级⽬录，⼆级，三级 ...
如果我们不断往跳表中插⼊数据，可能出现某⼀段节点会特别多的情况，这个时候就需要动态更新索引，除了插⼊数据，还要插⼊到上⼀层的链表中，保证查询效率。redis 中使⽤了跳表来实现zset , redis 中使⽤⼀个随机算法来计算层级，计算出每个节点到底多少层索引，虽然不能绝对保证⽐较平衡，但是基本保证了效率，实现起来⽐那些平衡树，红⿊树的算法简单⼀点。
在跳表中，每个节点包含以下几个组成部分：
跳表核心特性：
查找（Search）：查找过程从最高层开始，沿着当前层前进，直到遇到大于或等于目标值的节点：
插入（Insert）
删除（Delete）
import java.util.Random;
public class SkipList> {
private static final int MAX_LEVEL = 16; // 最大层数
private static final double P = 0.5; // 提升层级的概率
private int level; // 当前跳表的最大层数
private final Node header; // 头节点
private final Random random; // 用于随机层数的生成
// 节点定义
private static class Node> {
T value; // 节点值
Node[] forward; // 前进指针数组
@SuppressWarnings("unchecked")
Node(T value, int level) {
this.value = value;
this.forward = new Node[level + 1];
}
}
// 构造函数
public SkipList() {
this.level = 0;
this.header = new Node(null, MAX_LEVEL);
this.random = new Random();
}
// 随机生成层数
private int randomLevel() {
int lvl = 0;
while (lvl search(T value) {
Node current = header;
// 从最高层开始查找
for (int i = level; i >= 0; i--) {
// 在当前层向前移动，直到找到大于等于目标值的节点
while (current.forward[i] != null &&
current.forward[i].value.compareTo(value) [] update = new Node[MAX_LEVEL + 1];
Node current = header;
// 查找插入位置并记录每层的前驱节点
for (int i = level; i >= 0; i--) {
while (current.forward[i] != null &&
current.forward[i].value.compareTo(value) level) {
for (int i = level + 1; i newNode = new Node(value, newLevel);
// 插入节点到各层链表中
for (int i = 0; i [] update = new Node[MAX_LEVEL + 1];
Node current = header;
// 查找删除位置并记录每层的前驱节点
for (int i = level; i >= 0; i--) {
while (current.forward[i] != null &&
current.forward[i].value.compareTo(value) 0 && header.forward[level] == null) {
level--;
}
}
}
// 打印跳表内容（用于调试）
public void printSkipList() {
System.out.println("Skip List Structure:");
for (int i = level; i >= 0; i--) {
System.out.print("Level " + i + ": ");
Node node = header.forward[i];
while (node != null) {
System.out.print(node.value + " ");
node = node.forward[i];
}
System.out.println();
}
}
}
// 跳表节点
class SkipListNode {
constructor(value, level) {
this.value = value;
this.forward = new Array(level + 1).fill(null);
}
}
// 使用示例
SkipList skipList = new SkipList();
skipList.insert(3);
skipList.insert(6);
skipList.insert(7);
console.log(skipList.search(6)); // true
skipList.insert(9);
skipList.delete(6);
console.log(skipList.search(6)); // false
栈 (Stack) 只允许在有序的线性数据集合的一端（称为栈顶 top）进行加入数据（push）和移除数据（pop）。因而按照 后进先出（LIFO, Last In First Out） 的原理运作。在栈中，push 和 pop 的操作都发生在栈顶。就像是⼀个桶，只能不断的放在上⾯，取出来的时候，也只能不断的取出最上⾯的数据。要想取出底层的数据，只有等到上⾯的数据都取出来，才能做到。当然，如果有这种需求，我们⼀般会使⽤双向队列。
栈常用一维数组或链表来实现，用数组实现的栈叫作 顺序栈 ，用链表实现的栈叫作 链式栈 。JDK 底层的栈，是⽤数组实现的，封装之后，通过API 操作的永远都只能是最后⼀个元素，栈经常⽤来实现递归的功能。
元素加⼊称之为⼊栈（压栈），取出元素，称之为出栈，栈顶元素则是最后⼀次放进去的元素。使⽤数组实现简单的栈(注意仅供参考测试，实际会有线程安全等问题)
假设堆栈中有n个元素。
当我们我们要处理的数据只涉及在一端插入和删除数据，并且满足 后进先出（LIFO, Last In First Out） 的特性时，我们就可以使用栈这个数据结构。
我们只需要使用两个栈(Stack1 和 Stack2)和就能实现这个功能。比如你按顺序查看了 1,2,3,4 这四个页面，我们依次把 1,2,3,4 这四个页面压入 Stack1 中。当你想回头看 2 这个页面的时候，你点击回退按钮，我们依次把 4,3 这两个页面从 Stack1 弹出，然后压入 Stack2 中。假如你又想回到页面 3，你点击前进按钮，我们将 3 页面从 Stack2 弹出，然后压入到 Stack1 中。
给定一个只包括
'('，')'，'{'，'}'，'['，']'的字符串，判断该字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
比如 "()"、"()[]{}"、"{[]}" 都是有效字符串，而 "(]"、"([)]" 则不是。
这个问题实际是 Leetcode 的一道题目，我们可以利用栈 Stack 来解决这个问题。
Map 中，这一点应该毋容置疑；stack中，否则将stack 的栈顶元素与这个括号做比较，如果不相等就直接返回 false。遍历结束，如果stack为空，返回 true。public boolean isValid(String s){
// 括号之间的对应规则
HashMap mappings = new HashMap();
mappings.put(')', '(');
mappings.put('}', '{');
mappings.put(']', '[');
Stack stack = new Stack();
char[] chars = s.toCharArray();
for (int i = 0; i 将字符串中的每个字符先入栈再出栈就可以了。
最后一个被调用的函数必须先完成执行，符合栈的 后进先出（LIFO, Last In First Out） 特性。
例如递归函数调用可以通过栈来实现，每次递归调用都会将参数和返回地址压栈。
在深度优先搜索过程中，栈被用来保存搜索路径，以便回溯到上一层。
栈既可以通过数组实现，也可以通过链表来实现。不管基于数组还是链表，入栈、出栈的时间复杂度都为 O(1)。
下面我们使用数组来实现一个栈，并且这个栈具有push()、pop()（返回栈顶元素并出栈）、peek() （返回栈顶元素不出栈）、isEmpty()、size()这些基本的方法。
提示：每次入栈之前先判断栈的容量是否够用，如果不够用就用
Arrays.copyOf()进行扩容；
public class MyStack {
private int[] storage;//存放栈中元素的数组
private int capacity;//栈的容量
private int count;//栈中元素数量
private static final int GROW_FACTOR = 2;
//不带初始容量的构造方法。默认容量为8
public MyStack() {
this.capacity = 8;
this.storage=new int[8];
this.count = 0;
}
//带初始容量的构造方法
public MyStack(int initialCapacity) {
if (initialCapacity 验证
MyStack myStack = new MyStack(3);
myStack.push(1);
myStack.push(2);
myStack.push(3);
myStack.push(4);
myStack.push(5);
myStack.push(6);
myStack.push(7);
myStack.push(8);
System.out.println(myStack.peek());//8
System.out.println(myStack.size());//8
for (int i = 0; i 队列（Queue） 是 先进先出 (FIFO，First In, First Out) 的线性表。在具体应用中通常用链表或者数组来实现，用数组实现的队列叫作 顺序队列 ，用链表实现的队列叫作 链式队列 。队列只允许在后端（rear）进行插入操作也就是入队 enqueue，在前端（front）进行删除操作也就是出队 dequeue
队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。
⼀般只要说到先进先出（ FIFO ）,全称First In First Out ,就会想到队列，但是如果你想拥有队列即可以从队头取出元素，⼜可以从队尾取出元素，那就需要⽤到特殊的队列（双向队列），双向队列⼀般使⽤双向链表实现会简单⼀点。
假设队列中有n个元素。
单队列就是常见的队列, 每次添加元素时，都是添加到队尾。单队列又分为 顺序队列（数组实现） 和 链式队列（链表实现）。
顺序队列存在“假溢出”的问题也就是明明有位置却不能添加的情况。
假设下图是一个顺序队列，我们将前两个元素 1,2 出队，并入队两个元素 7,8。当进行入队、出队操作的时候，front 和 rear 都会持续往后移动，当 rear 移动到最后的时候,我们无法再往队列中添加数据，即使数组中还有空余空间，这种现象就是 ”假溢出“ 。除了假溢出问题之外，如下图所示，当添加元素 8 的时候，rear 指针移动到数组之外（越界）。
为了避免当只有一个元素的时候，队头和队尾重合使处理变得麻烦，所以引入两个指针，front 指针指向对头元素，rear 指针指向队列最后一个元素的下一个位置，这样当 front 等于 rear 时，此队列不是还剩一个元素，而是空队列。——From 《大话数据结构》
循环队列可以解决顺序队列的假溢出和越界问题。解决办法就是：从头开始，这样也就会形成头尾相接的循环，这也就是循环队列名字的由来。
顺序队列中，我们说 front==rear 的时候队列为空，循环队列中则不一样，也可能为满，如上图所示。解决办法有两种：
flag,当 front==rear 并且 flag=0 的时候队列为空，当front==rear 并且 flag=1 的时候队列为满。front==rear ，队列满的时候，我们保证数组还有一个空闲的位置，rear 就指向这个空闲位置，如下图所示，那么现在判断队列是否为满的条件就是：(rear+1) % QueueSize==front 。双端队列 (Deque) 是一种在队列的两端都可以进行插入和删除操作的队列，相比单队列来说更加灵活。
一般来说，我们可以对双端队列进行 addFirst、addLast、removeFirst 和 removeLast 操作。
优先队列 (Priority Queue) 从底层结构上来讲并非线性的数据结构，它一般是由堆来实现的。
关于堆的具体实现可以看堆这一节。
总而言之，不论我们进行什么操作，优先队列都能按照某种排序方式进行一系列堆的相关操作，从而保证整个集合的有序性。
虽然优先队列的底层并非严格的线性结构，但是在我们使用的过程中，我们是感知不到堆的，从使用者的眼中优先队列可以被认为是一种线性的数据结构：一种会自动排序的线性队列。
当我们需要按照一定顺序来处理数据的时候可以考虑使用队列这个数据结构。
FixedThreadPool 使用无界队列 LinkedBlockingQueue。但是有界队列就不一样了，当队列满的话后面再有任务/请求就会拒绝，在 Java 中的体现就是会抛出java.util.concurrent.RejectedExecutionException 异常。push、pop 和 peek），并且在 Deque 接口中已经实现了相关方法。Stack 类已经和 Vector 一样被遗弃，现在在 Java 中普遍使用双端队列（Deque）来实现栈。class Node {
public T data;
public Node next;
public Node(T data) {
this.data = data;
}
}
public class MyQueue {
private Node head;
private Node rear;
private int size;
public MyQueue() {
size = 0;
}
public void pushBack(T element) {
Node newNode = new Node(element);
if (isEmpty()) {
head = newNode;
} else {
rear.next = newNode;
}
rear = newNode;
size++;
}
public boolean isEmpty() {
return head == null;
}
public T popFront() {
if (isEmpty()) {
throw new NullPointerException("队列没有数据");
} else {
Node node = head;
head = head.next;
size--;
return node.data;
}
}
public void dispaly() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data +" -> ");
temp = temp.next;
}
System.out.println("");
}
}
有两个栈 stack1 , stack2 ；
例如：
算法实现如下：
class MyQueue {
Stack stackIn;
Stack stackOut;
/** Initialize your data structure here. */
public MyQueue() {
stackIn = new Stack(); // 负责进栈
stackOut = new Stack(); // 负责出栈
}
/** Push element x to the back of queue. */
public void push(int x) {
stackIn.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
dumpstackIn();
return stackOut.pop();
}
/** Get the front element. */
public int peek() {
dumpstackIn();
return stackOut.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
return stackIn.isEmpty() && stackOut.isEmpty();
}
// 如果stackOut为空，那么将stackIn中的元素全部放到stackOut中
private void dumpstackIn(){
if (!stackOut.isEmpty()) return;
while (!stackIn.isEmpty()){
stackOut.push(stackIn.pop());
}
}
}
队列是先进先出的规则，把一个队列中的数据导入另一个队列中，数据的顺序并没有变，并没有变成先进后出的顺序。
所以用栈实现队列， 和用队列实现栈的思路还是不一样的，这取决于这两个数据结构的性质。
但是依然还是要用两个队列来模拟栈，只不过没有输入和输出的关系，而是另一个队列完全用来备份的！
class MyStack {
Queue queue1; // 和栈中保持一样元素的队列
Queue queue2; // 辅助队列
/** Initialize your data structure here. */
public MyStack() {
queue1 = new LinkedList();
queue2 = new LinkedList();
}
/** Push element x onto stack. */
public void push(int x) {
queue2.offer(x); // 先放在辅助队列中
while (!queue1.isEmpty()){
queue2.offer(queue1.poll());
}
Queue queueTemp;
queueTemp = queue1;
queue1 = queue2;
queue2 = queueTemp; // 最后交换queue1和queue2，将元素都放到queue1中
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue1.poll(); // 因为queue1中的元素和栈中的保持一致，所以这个和下面两个的操作只看queue1即可
}
/** Get the top element. */
public int top() {
return queue1.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue1.isEmpty();
}
}
优化：
其实这道题目就是用一个队列就够了。
一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时再去弹出元素就是栈的顺序了。
class MyStack {
Queue queue;
public MyStack() {
queue = new LinkedList();
}
public void push(int x) {
queue.add(x);
}
public int pop() {
rePosition();
return queue.poll();
}
public int top() {
rePosition();
int result = queue.poll();
queue.add(result);
return result;
}
public boolean empty() {
return queue.isEmpty();
}
public void rePosition(){
int size = queue.size();
size--;
while(size-->0)
queue.add(queue.poll());
}
}
本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top
登录查看全部
参与评论
手机查看
返回顶部