1. Algorithm: 每周至少做一个 LeetCode 的算法题

225. Implement Stack using Queues

Implement the following operations of a stack using queues.



• push(x) -- Push element x onto stack.

• pop() -- Removes the element on top of the stack.

• top() -- Get the top element.

• empty() -- Return whether the stack is empty.



Example:



MyStack stack = new MyStack();
stack.push(1);
stack.push(2);  
stack.top();   // returns 2
stack.pop();   // returns 2
stack.empty(); // returns false



Notes:



• You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.

• Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.

• You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).



Stack解法

双链表解法，push时间复杂度为O(1), pop时间复杂度为O(n)。

class MyStack {
  private Queue<Integer> q1 = new LinkedList<>();
  private Queue<Integer> q2 = new LinkedList<>();
  private int top;
  /** Initialize your data structure here. */
  public MyStack() {
  }
  /** Push element x onto stack. */
  public void push(int x) {
    q1.add(x);
    top = x;
  }
  /** Removes the element on top of the stack and returns that element. */
  public int pop() {
    while (q1.size() > 1) {
      top = q1.remove();
      q2.add(top);
    }
    int i = q1.remove();
    Queue<Integer> temp = q1;
    q1 = q2;
    q2 = temp;
    return i;
  }
  /** Get the top element. */
  public int top() {
    return top;
  }
  /** Returns whether the stack is empty. */
  public boolean empty() {
    return q1.isEmpty();
  }
}
/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */



2. Review: 阅读并点评至少一篇英文技术文章

Moya Tutorial for iOS: Getting Started

https://www.raywenderlich.com/5121-moya-tutorial-for-ios-getting-started



Moya 框架对Alamofire进行封装，使得用法更简洁，比如相同的url，header进行统一管理。



笔者学习了整个教程，并翻译成中文。

【翻译】iOS Swift Moya从入门到精通，优雅、安全的Alamofire

https://blog.csdn.net/zgpeace/article/details/107747785



3. Tips: 学习至少一个技术技巧

笔者写的博客：

mac sublime text 3 列操作，替换相同内容, 用动态输入的方式



说明

有时候需要去掉获取替换掉相同的列，那么有如下方法。



列操作

按住 option 键，然后选择需要选择的列，比如笔者选择第一列。从上到下，从下到上，从左到右，或者从右到左都可以。

比如笔者输入666在前面，就变成如下所示：

搜索全部替换

如果想替换掉 <String>,

1. command + f, 输入<String>

2. 点击右下角的Find All 按钮

比如笔者想换成have a good day. 如下所示



4. Share: 分享一篇有观点和思考的技术文章

笔者写的博客链接

极客大学架构师训练营 网络通信协议 非阻塞网络I/O NIO 数据库架构原理 第16课 听课总结



说明

讲师：李智慧



网络通信协议



Web 请求的一次网络通信历程

客户端 > 域名访问 > DNS 解析为 IP地址 >

• 获取静态资源 jpg, css, javascript, 通过CDN

• 获取动态资源，基于TCP访问到负载均衡服务器 （比如订单、商品详情等）

反向代理服务器 > 负载均衡服务 > 网关服务器 > 微服务服务器 >

• 数据库服务器 （基于TCP协议访问 ）

• 缓存服务器（基于TCP协议访问 ）



OSI 七层模型和TCP/IP四层模型

1. 链路层（Mac地址），互联网有很多种媒介，比如光纤，网线等，要定义好什么是0，什么是1. 比如大于多少电压是1。

2. 网络互联层，根据Router路由选择找到目标服务器，根据迪杰斯特拉算法得到最短路径。

3. 传输层，主要看监听的端口，socket。

4. 应用层，把二进制返回给应用，应用需要反序列化为程序可识别的数据。HTTP协议。



• 应用层 HTTP

• 传承层 TCP/IP 协议

• 互联网 IP 数据

• 网络接口 Mac地址



每一层都包了一个头和数据，传到下一层。

解析的话，就是把头都脱掉，剩下的就是下一层的数据。



网络数据包格式

1. HTTP协议头，方法(POST), path, 编码(utf-8)

2. TCP 协议头，HTTP进程监听端口

3. IP协议头，服务器IP

4. 链路层协议头，服务器Mac地址



物理层

物理层负责数据的物理传输，计算机输入输出的只能是0 1 这样的二进制数据，但是在真正的通信线路里有光纤、电缆、无线各种设备。光信号和电信号，以及无线电磁信号在物理上是完全不同的，如何让这些不同的设备能够理解、处理相同的二进制数据，这就是物理层要解决的问题。

链路层

链路层就是将数据进行封装后交给物理层进行传输，主要是将数据封装成数据帧，以帧为单位通过物理层进行通信，有了帧，就可以在帧上进行数据校验，进行流量控制。



链路层会定义帧的大小，这个大小也被称为最大传输单元。像HTTP要在传输的数据上添加一个HTTP头一样，数据链路层也会将封装好的帧添加一个帧头，帧头里记录的一个重要信息就是发送者和接收者的 MAC地址。MAC地址是网卡的设备标识符，是唯一的，数据帧通过这个信息确保数据送达到正确的目标机器。



数据链路层负载均衡

负载均衡服务器直接改Mac地址，达到负载均衡。



网络层

网络层 IP 协议使得互联网应用根据 IP 地址就能访问到目标服务器，请求离开 App 后，到达运营服务商的交换机，交换机会根据这个 IP 地址进行路由转发，可能中间会经过很多个转发节点，最后数据到达目标服务器。



网络层的数据需要交给链路层进行处理，而链路层帧的大小定义了最大传输单元，网络层的 IP 数据包必须要小于最大传输单元才能进行网络传输，这个数据包也有一个 IP 头，主要包括的就是发送者和接收者的 IP 地址。



IP负载均衡

负载均衡服务器通过修改IP地址，到达内网的应用服务器。



传输层(TCP协议)

IP 协议不是一个可靠的通信协议，不会建立稳定的通信链路，并不会确保数据一定送达。要保证通信的稳定可靠，需要传输层协议 TCP。



TCP协议是一种面向连接的、可靠的、基于字节流的传输层协议。TCP作为一个比较基础的通讯协议，有很多重要的机制保证了 TCP 协议的可靠性和健壮性：

1. 使用序号，对收到的 TCP 报文段进行排序和检测重复的数据。

2. 无错传输，使用校验和检测报文段的错误。

3. 使用确认和计时器来检测和纠正丢包或者延迟。

4. 流量控制，避免主机分组发送得过快而使接收方来不及完全收下。

5. 拥塞控制，发送方根据网络承载情况控制分组的发送量，以获得高性能同时避免拥塞崩溃。

6. 丢失包的重传。



TCP 建立连接的3次握手过程

1. App 先发送 SYN=1， Seq=X 的报文，表示请求建立连接，X是一个随机数；

2. 服务器收到这个报文后，应答 SYN=1，ACK=X+1，Seq=Y 的报文，表示同意建立连接；

3. App 收到这个报文后，检查 ACK 的值为自己发送的 Seq 值 +1，确认建立连接，并发送 ACK = Y + 1 的报文给服务器；服务器收到这个报文后检查 ACK 值为自己发送的 Seq值 + 1，确认建立连接。至此，App 和服务器建立 TCP 连接，就可以进行数据传输。

TCP 关闭连接4次挥手

1. 客户端向服务器发送一个 FIN，请求关闭数据传输。

2. 当服务器收到客户端的 FIN 时，向客户端发送一个 ACK，其中 ACK 的值等于 FIN + SEQ。

3. 然后服务器向客户端发送一个 FIN，告诉客户端应用程序关闭。

4. 当客户端收到服务器的 FIN 时，回复一个 ACK 给服务器。其中 ACK 的值等于 FIN + SEQ。



注意：客户端和服务端都可以发起关闭连接。



应用层 HTTP 协议

而互联网应用需要在全球范围为用户提供服务，将全球的应用和全球的用户联系在一起，需要一个统一的应用层协议，这个协议就是HTTP协议。



HTTP请求的7种方法

1. Get： 只读请求，请求处理过程不应该产生副作用，即web应用不应该因为get请求而发生任何状态改变。

2. Head：和get方法一样，但是只返回响应头。

3. Post：提交请求。

4. Put：上传请求。

5. Delete：删除URL标识的资源。

6. Trace：回显服务器收到的请求，用以测试或者诊断。

7. Options：请求服务器返回支持的所有HTTP请求方法，测试服务器是否正常。

HTTP 响应的5种状态

• 1XX 消息 -- 请求已被服务器接收，继续处理。

• 2XX 成功 -- 请求已成功被服务器接收、理解、并接受。

• 3XX 重定向 -- 需要后续操作才能完成这一请求。

• 4XX 请求错误 -- 请求含有词法错误或者无法被执行。

• 5XX 服务器错误 -- 服务器在处理某个正确请求时发生错误。



HTTP 协议版本

HTTP 1.0

1996 年发布了 HTTP/1.0， 在HTTP/1.0中，客户端和服务端之间交换的每个请求 / 响应都会创建一个新的 TCP 连接，这意味着所有请求之前都需要进行 TCP 握手连接，因此所有请求都会产生延迟。



HTTP 1.1

HTTP/1.1 试图引入保持连接的概念来解决这些问题，它允许客户端复用 TCP 连接，从而分摊了建立初始连接和针对多个请求缓慢启动的成本。但任意时点上每个连接只能执行一次请求 / 响应交换。



随着网络的发展，网站所需资源（CSS、JavaScript和图像等）不断增长，浏览器在获取和呈现网页时需要越来越多的并发性。但由于HTTP/1.1 只允许客户端进行一次 HTTP 请求 / 响应交换，因此在网络层上获得并发能力的唯一方法是并行使用多个 TCP 连接。



HTTP/2

HTTP/2 引入了 HTTP ”流“ 的概念，允许将不同的 HTTP 并发地复用到同一个 TCP 连接上，使浏览器更高效地复用 TCP 连接。 HTTP/2解决了 TCP 连接的使用效率低的问题，现在可以通过同一个连接同时传输多个请求 / 响应。



但是，TCP并不理解 HTTP流，当多个HTTP 请求复用一个 TCP 连接，如果前面的请求/ 响应没有处理完，后面的请求/ 响应也无法处理，也就是会出现头堵塞现象。

HTTP/3

HTTP/3 不是使用 TCP 作为会话的传输层，而是使用 QUIC （一种新的互联网传输协议）。该协议在传输层将流作为一等公民引入。多个 QUIC 流共享相同的 QUIC 连接，因此不需要额外的握手和慢启动来创建新的 QUIC 流。但 QUIC 流是独立的，因此在大多数情况下，只影响一个流的丢包不会响应其它流，这是因为 QUIC 数据包封装在 UDP 数据包。