作者文章归档：wangxiuwen
队列跟栈一样，也是一种操作受限的线性表数据结构
用数组实现的队列叫作 顺序队列，用链表实现的队列叫作 链式队列
最基本的操作有两个：入队enqueue()，放一个数据到队列尾部；出队dequeue()，从队列头部取一个元素
高性能队列Disruptor、Linux环形缓存，都用到了循环并发队列；Java concurrent并发包利用ArrayBlockingQueue来实现公平锁
数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据 数组是线性表（Linear List）。顾名思义，线性表就是数据排成像一条线一样的结构。 每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构 而与它相对立的概念是非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。
| 操作 | 复杂度 | 备注 |
|---|---|---|
| Access | O(1) | |
| 插入 insert | O(n) | 头O(n), 尾O(1), 平均O(n/2) 即 O(n) |
| 删除 delete | O(n) | 头O(n), |
复杂度描述的是算法执行时间（或占用空间）与数据规模的增长关系
和性能测试相比，复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点
复杂度量级，我们可以粗略地分为两类，多项式量级 和 非多项式量级。其中，非多项式量级只有两个：O(2n)和O(n!)
我们把时间复杂度为非多项式量级的算法问题叫作NP（Non-Deterministic Polynomial，非确定多项式）问题
当数据规模n越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法
算
需要掌握常见的10个数据结构与10个算法：
10个数据结构：
数组(Array)、链表(LinkedList)、栈(Stack)、队列(Queue, 优先队列 PriorityQueue)、散列表(HashTable)、二叉树(tree/Binary Search Tree)、堆、跳表、图(graph)、Trie树；
10个算法：
递归(Recursion)、排序、二分查找、搜索(BST(breadth-first)，DST(Depth-first))、哈希算法、贪心算法(Greedy)、分治算法(Divide and Conquer)、回溯算法(backtrace)、动态规划(D
https://leetcode-cn.com/problems/plus-one/
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1:
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。示例 2:
输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。class Solution {
public int[] plusOne(int[] digits)互斥
无锁
互斥锁
Lock
优化读多写少
读写锁
协作
管程（Monitor）
CountDownLatch
分工
连接器
| OSI七层网络模型 | 各层的解释 | TCP/IP四层概念模型 | 对应网络协议 |
|---|---|---|---|
| 应用层（Application） | 为应用程序提供服务 | 应用层 | HTTP、TFTP, FTP, NFS, WAIS、SMTP |
| 表示层（Presentation） | 数据格式化、数据加密 | Telnet, Rlogin, SNMP, Gopher | |
| 会话层（Session） | 建立、管理和维护会话 | SMTP, DNS | |
| 传输层（Transport） | 建立、管理和维护端到端的连接 | 传输层 | TCP, UDP |
| 网络层（Network） | IP选址及路由选择 |