By Long Luo

LeetCode Concurrency Problems

By Long Luo

Leetcode 232. 用栈实现队列 ，难度为Easy：

232. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（\(\texttt{push}\)、\(\texttt{pop}\)、\(\texttt{peek}\)、\(\texttt{empty}\)）：

实现\(\texttt{MyQueue}\)类：

• \(\texttt{void push(int x)}\)将元素\(x\)推到队列的末尾
• \(\texttt{int pop()}\)从队列的开头移除并返回元素
• \(\texttt{int peek()}\)返回队列开头的元素
• \(\texttt{boolean empty()}\)如果队列为空，返回\(\textit{true}\)；否则，返回\(\textit{false}\)。

说明：

你 只能 使用标准的栈操作 —— 也就是只有push to top, peek/pop from top, size, 和is empty操作是合法的。 你所使用的语言也许不支持栈。你可以使用list或者deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
13

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

提示：

• 1 <= x <= 9
• 最多调用\(100\)次\(\texttt{push}\)、\(\texttt{pop}\)、\(\texttt{peek}\)和\(\texttt{empty}\) 假设所有操作都是有效的 （例如，一个空的队列不会调用\(\texttt{pop}\)或者\(\texttt{peek}\)操作）

进阶：

你能否实现每个操作均摊时间复杂度为 \(O(1)\) 的队列？换句话说，执行 \(n\) 个操作的总时间复杂度为 \(O(n)\)，即使其中一个操作可能花费较长时间。

之前我们已经实现了 225. 用队列实现栈 ，今天我们来学习如何用队列来实现栈。

因为队列是FIFO，而栈是LIFO，所以我们需要用到两个栈，用其中一个来反转元素的入队顺序，而另一个则用来存储元素的最终顺序。

2个栈 (push - O(n), pop - O(1))

使用 \(2\) 个栈 \(\textit{stack}_1\) 和 \(\textit{stack}_2\)，\(\textit{stack}_1\) 作为主栈，而 \(\textit{stack}_2\) 是辅助栈。

入栈时：

1. 把 \(\textit{stack}_1\) 中所有的元素移到 \(\textit{stack}_2\) 中；
2. \(\textit{stack}_2\) 中压入新元素；
3. 把 \(\textit{stack}_2\) 中所有的元素弹出，再把弹出的元素压入 \(\textit{stack}_1\)。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class MyQueue {
	Stack<Integer> stack1;
	Stack<Integer> stack2;

	public MyQueue() {
		stack1 = new Stack<>();
		stack2 = new Stack<>();
	}

	public void push(int x) {
		if (stack1.empty()) {
			stack1.push(x);
			return;
		}

		while (!stack1.empty()) {
			stack2.push(stack1.pop());
		}
		stack2.push(x);
		while (!stack2.empty()) {
			stack1.push(stack2.pop());
		}
	}

	public int pop() {
		return stack1.pop();
	}

	public int peek() {
		return stack1.peek();
	}

	public boolean empty() {
		return stack1.empty() && stack2.empty();
	}
}

By Long Luo

Leetcode 225. 用队列实现栈 ，难度为Easy：

1. 用队列实现栈

请你仅使用两个队列实现一个后入先出(LIFO)的栈，并支持普通栈的全部四种操作(\(\texttt{push}\)、\(\texttt{top}\)、\(\texttt{pop}\) 和 \(\texttt{empty}\))。

实现 \(\texttt{MyStack}\) 类：

• \(\texttt{void push(int x)}\) 将元素 \(\textit{x}\) 压入栈顶。
• \(\texttt{int pop()}\) 移除并返回栈顶元素。
• \(\texttt{int top()}\) 返回栈顶元素。
• \(\texttt{boolean empty()}\) 如果栈是空的，返回 \(\textit{true}\)；否则，返回 \(\textit{false}\)。

注意： - 你只能使用队列的基本操作 —— 也就是push to back、peek/pop from front、size和is empty这些操作。 - 你所使用的语言也许不支持队列。 你可以使用list（列表）或者deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示： - 1 <= x <= 9 - 最多调用 \(100\) 次 \(\texttt{push}\)、\(\texttt{pop}\)、\(\texttt{top}\) 和 \(\texttt{empty}\) - 每次调用 \(\texttt{pop}\) 和 \(\texttt{top}\) 都保证栈不为空

进阶：你能否仅用一个队列来实现栈。

这道题考察的是栈和队列两种数据结构知识。

栈是一种后进先出(LIFO)的数据结构，元素从顶端入栈，然后从顶端出栈。

队列是一种先进先出(FIFO)的数据结构，元素从后端入队，然后从前端出队。

2个队列

题目的要求是用 \(2\) 个队列实现一个栈，但是把一个队列中的数据导入另一个队列中，数据的顺序并没有发生改变，并不会变成先进后出的顺序。

那该如何做呢？

用 \(2\) 个队列 \(\textit{queue}_1\) 和 \(\textit{queue}_2\)：

1. 有 \(1\) 个元素 \(\textit{A}\)，那非常简单，直接压入弹出即可；
2. 有 \(2\) 个元素 \(\textit{A}\)，\(\textit{B}\)，\(\textit{queue}_1\) 压入 \(A\)，\(\textit{queue}_2\) 压入 \(B\)，然后将 \(\textit{queue}_1\) 中元素压入 \(\textit{queue}_2\)，这样 \(\textit{queue}_2\) 中的元素顺序就是正确的；
3. 因为 \(\textit{queue}_1\) 是主队列，所以还需要将 \(\textit{queue}_2\) 中元素重新导入到 \(\textit{queue}_1\)。

代码如下所示：

By LongLuo

面试时，经常会遇到一道题，说说HTTPS的实现。

为什么需要加密？

HTTPS是为了满足哪些需求？

HTTP的缺点：

• 通信使用明文（不加密），内容可能会被窃听；
• 不验证通信方的身份，因此有可能遭遇伪装（中间人攻击）；
• 无法证明报文的完整性，所以有可能已遭篡改。

如何设计HTTPS？

兼容性

因为是先有HTTP再有HTTPS。所以HTTPS首先要考虑到对原有HTTP的兼容性。

兼容性包括多方面，比如已有的Web应用要尽可能无缝地迁移到HTTPS；比如对浏览器厂商而言，改动要尽可能小；……

基于“兼容性”方面的考虑，很容易得出如下几个结论：

1. HTTPS还是要基于TCP来传输（如果改为UDP作传输层，无论是Web服务端还是浏览器客户端，都要大改——动静太大，伤筋动骨）

2. 单独使用一个新的协议，把HTTP协议包裹起来（所谓的“HTTP over SSL”，实际上是在原有的HTTP数据外面加了一层SSL的封装。HTTP协议原有的GET、POST之类的机制，基本上原封不动）

打个比方：如果原来的HTTP是塑料水管，容易被戳破；那么如今新设计的HTTPS就像是在原有的塑料水管之外，再包一层金属水管。一来，原有的塑料水管照样运行；二来，用金属加固了之后，不容易被戳破。

可扩展性

前面说了，HTTPS 相当于是“HTTP over SSL”。

如果SSL这个协议在“可扩展性”方面的设计足够牛逼，那么它除了能跟HTTP搭配，还能够跟其它的应用层协议搭配。岂不美哉？

现在看来，当初设计SSL的人确实比较牛。如今的SSL/TLS可以跟很多常用的应用层协议（比如：FTP、SMTP、POP、Telnet）搭配，来强化这些应用层协议的安全性。

接着刚才打的比方：如果把SSL/TLS视作一根用来加固的金属管，它不仅可以用来加固输水的管道，还可以用来加固输煤气的管道。

By LongLuo

2021.05.09这一天是母亲节，想起曾读过留下很深印象的几篇关于母亲的文章，这些文章都在我读中学时在课外读物上读过的，但目前为此都还留下了深刻的印象。记得当时读完心里感觉酸酸的，眼泪在眼眶里打转，又是羞愧又是庆幸自己还有机会去报答爸妈的恩情。

今天花了点时间把它们都找出来，常读常新！

毕淑敏：孝心无价

我不喜欢一个苦孩子求学的故事。家庭十分困难，父亲逝去，弟妹嗷嗷待哺，可他大学毕业后，还要坚持读研究生，母亲只有去卖血……我以为那是一个自私的学子。求学的路很漫长，一生一世的事业，何必太在意几年蹉跎?况且这时间的分分秒秒都苦涩无比，需用母亲的鲜血灌溉!一个连母亲都无法挚爱的人，还能指望他会爱谁?把自己的利益放在至高无上位置的人，怎能成为为人类奉献的大师?

我也不喜欢父母重病在床，断然离去的游子，无论你有多少理由。地球离了谁都照样转动，不必将个人的力量夸大到不可思议的程度。在一位老人行将就木的时候，将他对人世间最后期冀的希望斩断，以绝望之心在寂寞中远行，那是对生命的大不敬。

我相信每个赤诚忠厚的孩子，都曾在心底向父母许下“孝”的宏愿，相信来日方长，相信水到渠成，相信自己必有功成名就衣锦还乡的那一天，可以从容尽孝。可惜人们忘了，忘了时间的残酷，忘了人生的短暂，忘了世上有永远无法报答的恩情，忘了生命本身有不堪一击的脆弱。

父母走了，带着对我们深深的挂念。父母走了，遗留给我们永无偿还的心情。你就永远无以言孝。

有一些事情，当我们年轻的时候，无法懂得。当我们懂得的时候，已不再年轻。世上有些东西可以弥补，有些东西永无弥补…… “孝”是稍纵即逝的眷恋，“孝”是无法重现的幸福。“孝”是一失足成千古恨的往事，“孝”是生命与生命交接处的链条，一旦断裂，永无连接。

赶快为你的父母尽一份孝心。也许是一处豪宅，也许是一片砖瓦。也许是大洋彼岸的一只鸿雁，也许是近在咫尺的一个口信。也许是一顶纯黑的博士帽，也许是作业簿上的一个红五分。也许是一桌山珍海味，也许是一个野果一朵小花。也许是花团锦簇的盛世华衣，也许是一双洁净的旧鞋。也许是数亿万计的金钱，也许只是含着体温的一枚硬币……但“孝”的天平上，它们等值。

只是，天下的儿女们，一定要抓紧啊!趁我们父母健在的光阴。

老舍: 我的母亲

母亲的娘家是北平德胜门外，土城儿外边，通大钟寺的大路上的一个小村里。村里一共有四五家人家，都姓马。大家都种点不十分肥美的地，但是与我同辈的兄弟们，也有当兵的，作木匠的，作泥水匠的，和当巡察的。他们虽然是农家，却养不起牛马，人手不够的时候，妇女便也须下地作活。

对于姥姥家，我只知道上述的一点。外公外婆是什么样子，我就不知道了，因为他们早已去世。至于更远的族系与家史，就更不晓得了；穷人只能顾眼前的衣食，没有功夫谈论什么过去的光荣；“家谱”这字眼，我在幼年就根本没有听说过。

母亲生在农家，所以勤俭诚实，身体也好。这一点事实却极重要，因为假若我没有这样的一位母亲，我以为我恐怕也就要大大的打个折扣了。

母亲出嫁大概是很早，因为我的大姐现在已是六十多岁的老太婆，而我的大外甥女还长我一岁啊。我有三个哥哥，四个姐姐，但能长大成人的，只有大姐，二姐，三姐，三哥与我。我是“老”儿子。生我的时候，母亲已有四十一岁，大姐二姐已都出了阁。

由大姐与二姐所嫁入的家庭来推断，在我生下之前，我的家里，大概还马马虎虎的过得去。那时候定婚讲究门当户对，而大姐丈是作小官的，二姐丈也开过一间酒馆，他们都是相当体面的人。

可是，我，我给家庭带来了不幸：我生下来，母亲晕过去半夜，才睁眼看见她的老儿子——感谢大姐，把我揣在怀中，致未冻死。

一岁半，我把父亲“克”死了。

兄不到十岁，三姐十二三岁，我才一岁半，全仗母亲独力抚养了。父亲的寡姐跟我们一块儿住，她吸鸦片，她喜摸纸牌，她的脾气极坏。为我们的衣食，母亲要给人家洗衣服，缝补或裁缝衣裳。在我的记忆中，她的手终年是鲜红微肿的。白天，她洗衣服，洗一两大绿瓦盆。她作事永远丝毫也不敷衍，就是屠户们送来的黑如铁的布袜，她也给洗得雪白。晚间，她与三姐抱着一盏油灯，还要缝补衣服，一直到半夜。她终年没有休息，可是在忙碌中她还把院子屋中收拾得清清爽爽。桌椅都是旧的，柜门的铜活久已残缺不全，可是她的手老使破桌面上没有尘土，残破的铜活发着光。院中，父亲遗留下的几盆石榴与夹竹桃，永远会得到应有的浇灌与爱护，年年夏天开许多花。

哥哥似乎没有同我玩耍过。有时候，他去读书；有时候，他去学徒；有时候，他也去卖花生或樱桃之类的小东西。母亲含着泪把他送走，不到两天，又含着泪接他回来。我不明白这都是什么事，而只觉得与他很生疏。与母亲相依为命的是我与三姐。因此，她们作事，我老在后面跟着。她们浇花，我也张罗着取水；她们扫地，我就撮土……从这里，我学得了爱花，爱清洁，守秩序。这些习惯至今还被我保存着。

有客人来，无论手中怎么窘，母亲也要设法弄一点东西去款待。舅父与表哥们往往是自己掏钱买酒肉食，这使她脸上羞得飞红，可是殷勤的给他们温酒作面，又给她一些喜悦。遇上亲友家中有喜丧事，母亲必把大褂洗得干干净净，亲自去贺吊——份礼也许只是两吊小钱。到如今如我的好客的习性，还未全改，尽管生活是这么清苦，因为自幼儿看惯了的事情是不易改掉的。

姑母常闹脾气。她单在鸡蛋里找骨头。她是我家中的阎王。直到我入了中学，她才死去，我可是没有看见母亲反抗过。“没受过婆婆的气，还不受大姑子的吗？命当如此！”母亲在非解释一下不足以平服别人的时候，才这样说。是的，命当如此。母亲活到老，穷到老，辛苦到老，全是命当如此。她最会吃亏。给亲友邻居帮忙，她总跑在前面：她会给婴儿洗三——穷朋友们可以因此少花一笔“请姥姥”钱——她会刮痧，她会给孩子们剃头，她会给少妇们绞脸……凡是她能作的，都有求必应。但是吵嘴打架，永远没有她。她宁吃亏，不逗气。当姑母死去的时候，母亲似乎把一世的委屈都哭了出来，一直哭到坟地。不知道哪里来的一位侄子，声称有承继权，母亲便一声不响，教他搬走那些破桌子烂板凳，而且把姑母养的一只肥母鸡也送给他。

可是，母亲并不软弱。父亲死在庚子闹“拳”的那一年。联军入城，挨家搜索财物鸡鸭，我们被搜两次。母亲拉着哥哥与三姐坐在墙根，等着“鬼子”进门，街门是开着的。“鬼子”进门，一刺刀先把老黄狗刺死，而后入室搜索。他们走后，母亲把破衣箱搬起，才发现了我。假若箱子不空，我早就被压死了。皇上跑了，丈夫死了，鬼子来了，满城是血光火焰，可是母亲不怕，她要在刺刀下，饥荒中，保护着儿女。北平有多少变乱啊，有时候兵变了，街市整条的烧起，火团落在我们院中。有时候内战了，城门紧闭，铺店关门，昼夜响着枪炮。这惊恐，这紧张，再加上一家饮食的筹划，儿女安全的顾虑，岂是一个软弱的老寡妇所能受得起的？可是，在这种时候，母亲的心横起来，她不慌不哭，要从无办法中想出办法来。她的泪会往心中落！这点软而硬的个性，也传给了我。我对一切人与事，都取和平的态度，把吃亏看作当然的。但是，在作人上，我有一定的宗旨与基本的法则，什么事都可将就，而不能超过自己划好的界限。我怕见生人，怕办杂事，怕出头露面；但是到了非我去不可的时候，我便不得不去，正象我的母亲。从私塾到小学，到中学，我经历过起码有廿位教师吧，其中有给我很大影响的，也有毫无影响的，但是我的真正的教师，把性格传给我的，是我的母亲。母亲并不识字，她给我的是生命的教育。

当我在小学毕了业的时候，亲友一致的愿意我去学手艺，好帮助母亲。我晓得我应当去找饭吃，以减轻母亲的勤劳困苦。可是，我也愿意升学。我偷偷的考入了师范学校——制服，饭食，书籍，宿处，都由学校供给。只有这样，我才敢对母亲提升学的话。入学，要交十元的保证金。这是一笔巨款！母亲作了半个月的难，把这巨款筹到，而后含泪把我送出门去。她不辞劳苦，只要儿子有出息。当我由师范毕业，而被派为小学校校长，母亲与我都一夜不曾合眼。我只说了句：“以后，您可以歇一歇了！”她的回答只有一串串的眼泪。我入学之后，三姐结了婚。母亲对儿女是都一样疼爱的，但是假若她也有点偏爱的话，她应当偏爱三姐，因为自父亲死后，家中一切的事情都是母亲和三姐共同撑持的。三姐是母亲的右手。但是母亲知道这右手必须割去，她不能为自己的便利而耽误了女儿的青春。当花轿来到我们的破门外的时候，母亲的手就和冰一样的凉，脸上没有血色–那是阴历四月，天气很暖。大家都怕她晕过去。可是，她挣扎着，咬着嘴唇，手扶着门框，看花轿徐徐的走去。不久，姑母死了。三姐已出嫁，哥哥不在家，我又住学校，家中只剩母亲自己。她还须自晓至晚的操作，可是终日没人和她说一句话。新年到了，正赶上政府倡用阳历，不许过旧年。除夕，我请了两小时的假。由拥挤不堪的街市回到清炉冷灶的家中。母亲笑了。及至听说我还须回校，她楞住了。半天，她才叹出一口气来。到我该走的时候，她递给我一些花生，“去吧，小子！”街上是那么热闹，我却什么也没看见，泪遮迷了我的眼。今天，泪又遮住了我的眼，又想起当日孤独的过那凄惨的除夕的慈母。可是慈母不会再候盼着我了，她已入了土！

儿女的生命是不依顺着父母所设下的轨道一直前进的，所以老人总免不了伤心。我廿三岁，母亲要我结了婚，我不要。我请来三姐给我说情，老母含泪点了头。我爱母亲，但是我给了她最大的打击。时代使我成为逆子。廿七岁，我上了英国。为了自己，我给六十多岁的老母以第二次打击。在她七十大寿的那一天，我还远在异域。那天，据姐姐们后来告诉我，老太太只喝了两口酒，很早的便睡下。她想念她的幼子，而不便说出来。

七七抗战后，我由济南逃出来。北平又象庚子那年似的被鬼子占据了，可是母亲日夜惦念的幼子却跑西南来。母亲怎样想念我，我可以想象得到，可是我不能回去。每逢接到家信，我总不敢马上拆看，我怕，怕，怕，怕有那不祥的消息。人，即使活到八九十岁，有母亲便可以多少还有点孩子气。失了慈母便像花插在瓶子里，虽然还有色有香，却失去了根。有母亲的人，心里是安定的。我怕，怕，怕家信中带来不好的消息，告诉我已是失了根的花草。

去年一年，我在家信中找不到关于老母的起居情况。我疑虑，害怕。我想象得到，如有不幸，家中念我流亡孤苦，或不忍相告。母亲的生日是在九月，我在八月半写去祝寿的信，算计着会在寿日之前到达。信中嘱咐千万把寿日的详情写来，使我不再疑虑。十二月二十六日，由文化劳军的大会上回来，我接到家信。我不敢拆读。就寝前，我拆开信，母亲已去世一年了！

生命是母亲给我的。我之能长大成人，是母亲的血汗灌养的。我之所以能成为一个不十分坏的人，是母亲感化的。我的性格，习惯，是母亲传给的。她一世未曾享过一天福，临死还吃的是粗粮。唉！还说什么呢？心痛！心痛！