在了解了《同步与互斥的区别 》之后，我们来看看几个经典的线程同步的例子。相信通过具体场景可以让我们学会分析和解决这类线程同步的问题，以便以后应用在实际的项目中。

一、生产者-消费者问题

问题描述：

一组生产者进程和一组消费者进程共享一个初始为空、大小为 n 的缓冲区，只有缓冲区没满时，生产者才能把消息放入到缓冲区，否则必须等待；只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，或者一个消费者从中取出消息。

同步与互斥这两个概念经常被混淆，所以在这里说一下它们的区别。

一、同步与互斥的区别

1. 同步

同步，又称直接制约关系，是指多个线程（或进程）为了合作完成任务，必须严格按照规定的 某种先后次序来运行。

例如，线程 T2 中的语句 y 要使用线程 T1 中的语句 x 的运行结果，所以只有当语句 x 执行完成之后语句 y 才可以执行。我们可以使用信号量进行同步：

进程间通信（IPC，InterProcess Communication）是指在不同进程之间传播或交换信息。IPC的方式通常有管道（包括无名管道和命名管道）、消息队列、信号量、共享存储、Socket、Streams等。其中 Socket和Streams支持不同主机上的两个进程IPC。

一、管道

管道，通常指无名管道，是 UNIX 系统IPC最古老的形式。

写这篇文章的动因是因为 2015 年 04 月 02 日的阿里在线笔试题考到了这个知识点。我当时模模糊糊的写了一些，估计写的也不对，所以在这里总结一下。

原题

常常会有频繁申请、释放内存的需求，比如在发送网络报文时，每次都要分配内存以存储报文，等报文发送完成后又需要删除报文。

阅读全文 »

一、题目描述

描述：

输入n个整数，输出其中最小的k个。

输入：

1. 输入 n 和 k
2. 输入一个整数数组
   阅读全文 »

一、题目描述

描述：

• 计算一个数字的立方根，不使用库函数。
• 函数原型double getCubeRoot(double input)

输入：

一、题目描述

描述：

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学不交换位置就能排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1, 2, …, K，他们的身高分别为T1, T2, …, TK，则他们的身高满足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K) 。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

一、题目描述

描述：

计算两个字符串的最大公共子串（Longest Common Substring）的长度，字符区分大小写。

输入：

输入两个字符串

3、栈与队列

3.1 描述如何只用一个数组来实现三个栈。

3.2 请设计一个栈，除pop与push方法，还支持min方法，可返回栈元素中的最小值。pop、push和min三个方法的时间复杂度必须为O(1)。

3.3 设想有一堆盘子，堆太高可能会倒下来。因此，在现实生活中，盘子堆到一定高度时，我们就会另外堆一堆盘子。请实现数据结构SetOfStacks，模拟这种行为。SetOfStacks应该由多个栈组成，并且在前一个栈填满时新建一个栈。此外，SetOfStacks.push()和SetOfStacks.pop()应该与普通栈的操作方法相同（也就是说，pop()返回的值，应该跟只有一个栈时的情况一样）

1、数组与字符串

1.1 实现一个算法，确定一个字符串的所有字符是否全都不同。假设不允许使用额外的数据结构，又该如何处理？

1.2 用C或C++实现void reverse(char* str)函数，即反转一个null结尾的字符串。

1.3 给定两个字符串，请编写程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。

1.4 编写一个方法，将字符串中的空格全部替换为“%20”。假设该字符串尾部有足够的空间存放新增字符，并且知道字符串的“真实”长度。示例：输入Mr John Smith，输出Mr%20John%20Smith。