一点一点前进...

0%

发表于 分类于 ， Disqus：

说到数据在内存中的布局问题就不得不提到另一个概念：大端和小端。
存储地址内的排列则有两个通用规则。一个多位的整数将按照其存储地址的最低或最高字节排列。如果最低有效字节在最高有效字节的前面，则称小端序；反之则称大端序。

先来看个实际例子。

1
2
3
int i = 1 << 15;
short s = * (short*) &i;
std::cout << s << std::endl;

如果是大端机器，i的布局是0x00 0x00 0x80 0x00，s所对应的就是0x00 0x00，即0。
如果是小端机器，i的布局是0x00 0x80 0x00 0x00，s所对应的就是0x00 0x80，即-32768。

再来看个例子加深下理解。

1
2
3
float f = 7.0;
short s = * (short*) &f;
std::cout << s << std::endl;

7.0 = 1.75 * 2 ^ (129 - 127)
在大端机器中，对应的内存分布是一个0，接下来八位是10000001，接下来是两个1，后面都是0。s对应的是一个挺大的数字。在小端机器中，按照字节翻转，后面的0都跑前面来了，那么s就是0。

我们可以用一个简单的程序来检测到底是大端还是小端（当然，上面的两个例子也能检测）

1
2
3
4
5
6
7
8
9
10
int i = 1;
char ch = * (char*) &i;
if(ch == 1)
{
	std::cout << "little endian" << std::endl;
}
else
{
	std::cout << "big endian" << std::endl;
}

现在的机器几乎都是小端了，这是为什么呢？小端机器有什么好处呢？
StackOverflow和StackExchange上的答案类似：
使用同样的地址，可以使用不同的长度去读取一个变量。比如32bit的值，我们想读8bit或者16bit，直接读就好了，结果就是我们想要的，如果是大端，计算机还要计算偏移量再读取。
不过，在Quora上最高票答案是一个CPU Designer的回答，说是几乎没有什么区别。就和大端小端的来源一样，你会关心敲鸡蛋先敲开哪一端吗？
对于大多数程序员而言，现成的工具/库都考虑了这个问题，不用自己操心。不过，还是知道这个知识点比较好，说不准那天程序没有跑对就是因为这个呢？是吧。还有一点，万一面试的时候用呢。

发表于 分类于 ， Disqus：

C/C++不外乎以下几种基本类型：bool，char，short，int，long，float，double，还有不常用的long long。

char占用一个字节，而short占用两个字节，在char转化为short时，全部复制到short占用内存的低八位里面。

1
2
3
4
5
6
7
8
9
#include <iostream>

int main()
{
	char ch = 'A';
	short s = ch;
	std::cout << s << std::endl;
	return 0;
}

A对应的ASCII码是65，所以输出是65。

反之，short转化为char时，把高位的一个字节直接扔掉，只复制低字节。

1
2
3
short s = 67;
char ch = s;
std::cout << ch << std::endl;

输出是一个大写的C。

int一般占用4个字节，和short转化和上面char和short转化类似。下面看一个不太一样的例子。

1
2
3
int i = 1 << 15;
short s = i;
std::cout << s << std::endl;

i在内存中的表示是0000 0000，0000 0000，1000 0000，0000 0000
short占用两个字节，直接把低位两个字节复制过来，s在内存中的表示是1000 0000，0000 0000
第一位是符号位，表示负数，根据补码表示的意义，输出应该是负2的15次方，即-32768

float也占用四个字节，但是每一位的含义不一样，第一位是符号位s，接着的八位是exp，接着23位是尾数，表示0.ddd
float的值等于(-1)^s * (1.ddd) * 2 ^ (exp - 127)
正常的int转float很简单，比如：

1
2
3
int i = 5;
float f = i;
std::cout << f << std::endl;

就是正常的输出5，只是i和f占用的内存对应的bit位上0/1差别很大

来看个不正常的转化

1
2
3
int i = (1 << 22) + (1 << 30);
float f = * (float*) &i;
std::cout << f << std::endl;

i在内存中的表示是0100 0000，0100 0000，0000 0000，0000 0000
f没有分配新的空间，而是使用了i的内存，以float的方式去读而已
符号位是0，表示正数
exp是1000 0000，也就是128
再后面是一个1，22个0，尾数就是1.1
所以f等于(-1)^0 * (1.1) * 2 ^ (128 - 127) = 1.5 * 2 = 3，即输出3
注意，上面等式第一步把二进制变成了十进制

发表于 分类于 ， Disqus：

题目链接

在一个坛子中有赤橙黄绿青蓝紫七种颜色的球，每种10个，共70个球。从中随机挑选出20个球，求有几种颜色的期望值。

这个题思路很明确，期望等于颜色的种数乘以对应的概率。
直接算不太好算，我们换个等价的形式。
用i j k l m n q七个数字表示每个颜色的球的数量，遍历i j k l m n q每种可能的情况，对于特定的一组值，计算出可能出现的拿法，然后乘以颜色种数，除以C(20,70)，就是对应这组值的期望值。比如3 3 3 3 3 5 0，可能出现的拿法是C(3,10) ^ 5 * C(5,10)，颜色种类是5。
这里，C(20,70)是定值，所以可以提取出来，最后除一次就可以了。

首先，给出求排列组合的函数： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static long GetCombinationsCount(long total,long pickedCount)
{
	long count = 1;

	for (int i = 0; i < pickedCount; i++)
	{
		count *= (total - i);
	}

	for (int i = 0; i < pickedCount; i++)
	{
		count /= (i + 1);
	}

	return count;
}

计算颜色种类的函数： 

1
2
3
4
private static int GetColors(int[] counts)
{
	return counts.Count(i => i != 0);
}

准备工作做完了，我们来遍历i j k l m n q，由于最多20个球，循环的时候可以做一下简单的修剪以提高效率

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
BigInteger count = 0;
for (int i = 0; i < 11; i++)
{
	for (int j = 0; i < 11 && i + j <= 20; j++)
	{
		for (int k = 0; k < 11 && i + j + k <= 20; k++)
		{
			for (int l = 0; l < 11 && i + j + k + l <= 20; l++)
			{
				for (int m = 0; m < 11 && i + j + k + l + m <= 20; m++)
				{
					for (int n = 0; n < 11 && i + j + k + l + m + n <= 20; n++)
					{
						int q = 20 - i - j - k - l - m - n;
						if (q >= 0 && q <= 10)
						{
							int[] counts = new int[] { i, j, k, l, m, n, q };
							long tmp = 1;
							foreach (var c in counts)
							{
								tmp *= Utils.GetCombinationsCount(10, c);
							}

							count += GetColors(counts) * tmp;
						}
					}
				}
			}
		}
	}
}

最后，我们除以C(20,70)

1
2
3
4
5
6
7
8
9
10
11
12
for (int i = 1; i <= 20; i++)
{
	count *= i;
}

double dc = (double)count;
for (int i = 51; i <= 70; i++)
{
	dc /= i;
}

return dc.ToString().Substring(0, 11);

整个算法简洁明了，在我机器上不到500ms就能得到结果。

发表于 分类于 ， Disqus：

给定一个整数数组a[n]，求max{aj … ai}，其中0 <= i < j < n。要求时间复杂度为O(n)，空间复杂度为O(1)。

这道题若没有最后的空间复杂度时间复杂度的要求，很简单，两层循环就能解决了。

这个题看似要使用动态规划，但仔细一想，不好弄，不能使用额外的存储空间。
比如假定前i个的解是am-an，考虑第i+1个，若am到ai之间有个很小的数ak，可以使得a(i+1)-ak比am-an大，同时也比a(i+1)-an大。怎么弄？很难搞。

退回原始问题，看着有点像求连续最大子数组之和。
想办法把max{aj - ai}转化为max{am+…+an}。这里我对使用下标使用有点随意，明白这个意思就好。

我们构造如下数组：
a1,a2-a1,a3-a2,…an-a(n-1)

那么连续最大子数组之和就是：
a(i+1)-ai,a(i+2)-a(i+1),…aj-a(j-1) = aj - ai

也就是说，通过构造一个数组，把原问题转化为了一个很容易解决的问题。

新构造的数据是没有必要保存下来的，只需要将处理连续最大子数组之和程序中sum += ai;修改为sum += (ai - a(i-1))即可。

发表于 分类于 ， Disqus：

题目大致是说，
30能够分解得到的因数分别是1,2,3,5,6,10,15,30
对于30的每一个因数d，d+30/d都是一个质数。

求不超过100000000，且满足性质：
n的每一个因数d，d+n/d都是质数
的n的和。

分析一下什么样的n满足上述性质。
n能够分解成一系列的因数，记做d1, d2, d3, … c3, c2, c1
其中c1 * d1 = n => d1 = n / c1
也就是说只要分析前面一半，小于sqrt(n)的因数即可。

第一个因数肯定是1，那么1 + n 是质数。
所以我先使用筛选法得到小于100000000的质数，然后都减去1，得到的数才可能满足题意。

1
2
3
4
5
6
7
long[] primes = Utils.GenPrimes(100000000);

List<int> alternativeNumbers = new List<int>();
for (int i = 0; i < primes.Length; i++)
{
	alternativeNumbers.Add((int)primes[i] - 1);
}

假如n能整除4，也就是说n = 4k，第二个因数是2，且n / 2 = 2k
2 + 2k是偶数，肯定不是质数，所以我们把能整除4的数排除。
同理，n也不能被9整除。但是剩余数能被9整除的也就只有几十万了，对于二百八十多万来说，差距不大，就没有用这条性质再过滤数据了。

1
alternativeNumbers = alternativeNumbers.Where(i => i % 4 != 0).ToList();

现在，从剩余的n中看有多少是满足题意的。
正如上面所分析的，只要分析前面一半，小于sqrt(n)的因数即可。这能节省一半的时间呢。

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
long result = 0;
foreach (int n in alternativeNumbers)
{
	bool meet = true;
	int h = (int)Math.Sqrt(n);
	for (int i = 2; i <= h; i++)
	{
		if (n % i != 0)
		{
			continue;
		}

		int d = n / i;
		if (Array.BinarySearch(primes, d + i) < 0)
		{
			meet = false;
			break;
		}
	}

	if (meet)
	{
		result += n;
	}
}

return result;

我们之前已经得到了1亿之前的所有质数，那么利用二分法来判断是否是质数比传统的方式要快很多。
整个流程大约用时25s。
可优化的地方还很多，比如在筛选法的时候，使用了长度为1亿bool数组而不是bitset；多次去整理数组，这也是没有必要的，要知道，每次创建一个数百万大小的数组并复制所有的值，还是很耗时间的。

发表于 分类于 ， Disqus：

题目链接

众所周知，如果一个自然数的平方根不是整数，那么就是无理数。这样的平方根的小数部分是无限并且没有任何重复模式的。
2的平方根是 1.41421356237309504880…, 小数部分的前一百位和是475。

对于前一百个自然数，找出其中无理平方根的小数部分前一百位的总和。

这个题的难度在于精确的计算出小数点后99位。首先想到的是，肯定要模拟手算来开平方，具体的方法请参考Wiki百科里面的长除式算法。

代码如下：

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
private static string GetSqrt(int n)
{
	StringBuilder result = new StringBuilder();
	int integerPart = (int)Math.Sqrt(n);
	result.Append(integerPart);

	BigInteger a = new BigInteger(integerPart);
	BigInteger remainder = new BigInteger(n - integerPart * integerPart);
	for (int i = 0; i < 99; i++)
	{
		remainder *= 100;
		int b = 1;
		while ((a * 20 + b) * b < remainder)
		{
			b++;
		}

		b--;

		remainder = remainder - (a * 20 + b) * b;
		a = a * 10 + b;
		result.Append(b);
	}

	return result.ToString();
}

根据算法，a和余数会越来越大，a的长度会趋于100位，余数的长度会趋于200位，所以我使用了BigInteger来存储。for循环做了99次，因为题目要求100个数字，个位数已经占了一位了。
有了这个函数就可以求得给定整数开平方后的前一百位数字了。现在，只要写一个简单的循环就能得到最后的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int sum = 0;
for (int i = 2; i < 100; i++)
{
	int sqrt = (int)Math.Sqrt(i);
	if (sqrt * sqrt == i)
	{
		continue;
	}

	string decimalPart = GetSqrt(i);
	sum += decimalPart.Select(c => int.Parse(c.ToString())).Sum();
}

return sum;

在循环中，我排除了完全平方数，根据题意，它们是不计算到最后的和里面的。
值得一提的是，如果向GetSqrt里面传入完全平方数，在进入循环之前，余数是0，计算得到的b也就是0，循环不变，余数一直是0，b也一直是0，最后返回的数是平方根后面跟着99个0。

发表于 分类于 ， Disqus：

题目链接

给定一个a，n取何值时能让(a-1)^n + (a+1)^n % a^2最大呢？
首先考虑n是偶数的时候，
(a-1)^n + (a+1)^n
= 2 * (a^n + Cn,2*a^(n-2) + Cn,4*a^(n-4) + … + 1)
由于n是偶数，a^n能够被a^2整除，同理，a^(n-2)，a^(n-4)…a^2都可以被a^2整除。
所以，最后的余数是1，显然不大，下面我们考虑n是奇数的时候。
(a-1)^n + (a+1)^n
= 2 * (a^n + Cn,2*a^(n-2) + Cn,4*a^(n-4) + … + Cn,n-1*a)
a^n模a^2余数是a，同理，a^(n-2)…a模a^2都余a。
那么上面的数模a^2等于
2*a*(1+Cn,2+Cn,4+…+Cn,n-1) = 2*a*f(n)

想要2*a*f(n)模a^2余数最大呢，让2*a*f(n)越接近a^2越好，也就是2*f(n)越接近a越好，但是不能等于a。
2*f(n)一定是偶数。所以，当a是奇数的时候，2*f(n)=a-1，当a是偶数的时候，2*f(n)=a-2。

有了以上的分析，很容易就能写出获取Rmax的函数：

1
2
3
4
private static int GetMaxRByA(int a)
{
	return (a - 1) / 2 * 2 * a;
}

离最后的答案只差一步：

1
2
3
4
5
6
7
8
9
10
11
public static int GetAnswer()
{
	List<int> rs = new List<int>();

	for (int a = 3; a <= 1000; a++)
	{
		rs.Add(GetMaxRByA(a));
	}

	return rs.Sum();
}

有了数学分析得到的结论之后，程序的时间复杂度是O(n)，理论最低值了，而且这里n就1000，在我的机器上，14ms就完成了。

发表于 分类于 ， Disqus：

题目如下：

三角形数，四角形数，五角形数，六角形数，七角形数和八角形数都是定形数，他们分别由以下公式产生：
三角形数 P3,n=n(n+1)/2 1, 3, 6, 10, 15, …
四角形数 P4,n=n2 1, 4, 9, 16, 25, …
五角形数 P5,n=n(3n−1)/2 1, 5, 12, 22, 35, …
六角形数 P6,n=n(2n−1) 1, 6, 15, 28, 45, …
七角形数 P7,n=n(5n−3)/2 1, 7, 18, 34, 55, …
八角形数 P8,n=n(3n−2) 1, 8, 21, 40, 65, …

三个四位数形成的有序集合: 8128, 2882, 8281,有三个有趣的性质：

这个集合是循环的：每个数的后两位数是下一个数的前两位数，包括第三个和第一个的关系。
三种定形数中的每一种都能被这三个数中的一个不同的数代表：三角形数 (P3,127=8128), 四角形数 (P4,91=8281), 和五角形数 (P5,44=2882)。
这是唯一具有以上性质的四位数的集合。

找出唯一的一个六个四位数的循环集合，使得从三角形数到八角形数中的每一种都能由该集合中的一个不同的数代表。

求这个集合中元素之和。

首先，我们应该初始化这六个数组。同时排除倒数第二位为0的数字，因为这种数不可能在循环集合里面（不可能有数字以0开始）。

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
private static void Initialize(
	out List<int> P3, out List<int> P4, out List<int> P5,
	out List<int> P6, out List<int> P7, out List<int> P8)
{
	P3 = new List<int>();
	P4 = new List<int>();
	P5 = new List<int>();
	P6 = new List<int>();
	P7 = new List<int>();
	P8 = new List<int>();
	int n = 1;
	while (true)
	{
		if (n * (n + 1) / 2 > 10000)
		{
			break;
		}

		P3.Add(n * (n + 1) / 2);
		P4.Add(n * n);
		P5.Add(n * (3 * n - 1) / 2);
		P6.Add(n * (2 * n - 1));
		P7.Add(n * (5 * n - 3) / 2);
		P8.Add(n * (3 * n - 2));

		n++;
	}

	P3 = P3.Where(Meet).ToList();
	P4 = P4.Where(Meet).ToList();
	P5 = P5.Where(Meet).ToList();
	P6 = P6.Where(Meet).ToList();
	P7 = P7.Where(Meet).ToList();
	P8 = P8.Where(Meet).ToList();
}

private static bool Meet(int i)
{
	if (i <= 1000 || i >= 10000)
	{
		return false;
	}

	if ((i / 10) % 10 == 0)
	{
		return false;
	}

	return true;
}

循环集合，不管最终的数字顺序是怎么样的，都可以看作是从P3开始，最后循环到P3。当然，你也可以从P4什么的开始，都一样的。
我的思路是遍历P3数组，然后再遍历其他的数组，若P3里面数字的后两位等于其他数组中的前两位，就把他们拼接起来组成新的集合M1，M1中都是可能的解。
再接着，遍历M1和剩余数组，这里剩余数组指的是排除P3和某个数组之后的其他数组。比如第一次遍历P4的某个数拼接在P3的某个数后面，那么这里的剩余数组就是指P5，P6，P7和P8。和第一次遍历一样，继续拼接可能的字符串，组成集合M2。
以此类推。最后，每个数组贡献一个数字，拼接成了一个满足题意的字符串。

为了能知道在5次遍历中，那个数组用过了，那个数组没有被使用，我使用了下面这个数据结构：

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
private class OrderedSet : ICloneable
{
	public OrderedSet(string content)
	{
		this.Content = content;
	}

	public string Content { get; set; }
	public bool Has4 { get; set; }
	public bool Has5 { get; set; }
	public bool Has6 { get; set; }
	public bool Has7 { get; set; }
	public bool Has8 { get; set; }

	public object Clone()
	{
		OrderedSet other = new OrderedSet(this.Content);
		other.Has4 = this.Has4;
		other.Has5 = this.Has5;
		other.Has6 = this.Has6;
		other.Has7 = this.Has7;
		other.Has8 = this.Has8;

		return other;
	}
}

我把P3的数组扔到一个队列中，作为循环的初始：

1
2
3
4
5
Queue<OrderedSet> cur = new Queue<OrderedSet>();
foreach (var i in P3)
{
	cur.Enqueue(new OrderedSet(i.ToString()));
}

然后进行五次遍历，把P4到P8五个数组拼接到后面，代码有点丑。。。

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
for (int i = 0; i < 5; i++)
{
	Queue<OrderedSet> next = new Queue<OrderedSet>();

	foreach (var orderedSet in cur)
	{
		if (!orderedSet.Has4)
		{
			foreach (var j in P4)
			{
				if (orderedSet.Content.EndsWith(j.ToString().Substring(0, 2)))
				{
					OrderedSet other = (OrderedSet)orderedSet.Clone();
					other.Content = orderedSet.Content + j.ToString().Substring(2, 2);
					other.Has4 = true;
					next.Enqueue(other);
				}
			}
		}

		if (!orderedSet.Has5)
		{
			foreach (var j in P5)
			{
				if (orderedSet.Content.EndsWith(j.ToString().Substring(0, 2)))
				{
					OrderedSet other = (OrderedSet)orderedSet.Clone();
					other.Content = orderedSet.Content + j.ToString().Substring(2, 2);
					other.Has5 = true;
					next.Enqueue(other);
				}
			}
		}

		if (!orderedSet.Has6)
		{
			foreach (var j in P6)
			{
				if (orderedSet.Content.EndsWith(j.ToString().Substring(0, 2)))
				{
					OrderedSet other = (OrderedSet)orderedSet.Clone();
					other.Content = orderedSet.Content + j.ToString().Substring(2, 2);
					other.Has6 = true;
					next.Enqueue(other);
				}
			}
		}

		if (!orderedSet.Has7)
		{
			foreach (var j in P7)
			{
				if (orderedSet.Content.EndsWith(j.ToString().Substring(0, 2)))
				{
					OrderedSet other = (OrderedSet)orderedSet.Clone();
					other.Content = orderedSet.Content + j.ToString().Substring(2, 2);
					other.Has7 = true;
					next.Enqueue(other);
				}
			}
		}

		if (!orderedSet.Has8)
		{
			foreach (var j in P8)
			{
				if (orderedSet.Content.EndsWith(j.ToString().Substring(0, 2)))
				{
					OrderedSet other = (OrderedSet)orderedSet.Clone();
					other.Content = orderedSet.Content + j.ToString().Substring(2, 2);
					other.Has8 = true;
					next.Enqueue(other);
				}
			}
		}
	}

	cur = next;
}

好了，离胜利还有两步了。
第一步，遍历cur集合中的字符串，根据题目要求，最后两位和开头两位是相等的：

1
2
3
4
5
6
7
8
List<string> results = new List<string>();
foreach (var orderedSet in cur)
{
	if (orderedSet.Content.Substring(0, 2).Equals(orderedSet.Content.Substring(12, 2)))
	{
		results.Add(orderedSet.Content);
	}
}

题目已经告诉我们结果是唯一的了，这时，results集合里面应该只有一个元素。
最后一步，得到了这六个数字，求和即可。

发表于 分类于 ， Disqus：

栈是先进后出，队列是先进先出。考虑把栈A的数据弹出再压入栈B中，顺序就完全反过来了，如果再把B中的元素弹出，就按照进栈A的顺序了。此题解题思路大致如此。进队列的时间复杂度就是压入栈A的时间复杂度O(1)，出栈的话，如果栈B有数据，也是O(1)，但是没有数据，对于当次操作而言是O(n)，其中n为栈A中的元素个数，但是平摊分析一下，每个元素进栈A，倒到栈B，然后出栈，所以平均时间复杂度是O(1)。

下面是C#代码：

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public class QueueWith2Stacks<T>
{
	private Stack<T> enqueueStack;
	private Stack<T> dequeueStack;

	public QueueWith2Stacks()
	{
		enqueueStack = new Stack<T>();
		dequeueStack = new Stack<T>();
	}

	public int Count { get; private set; }

	public bool Empty { get { return Count == 0; } }

	public void Enqueue(T item)
	{
		enqueueStack.Push(item);
		Count++;
	}

	public T Peek()
	{
		if (Empty)
		{
			throw new InvalidOperationException();
		}
		else
		{
			if (dequeueStack.Count == 0)
			{
				EnqueueToDequeue();
			}

			return dequeueStack.Peek();
		}
	}

	public T Dequeue()
	{
		if (Empty)
		{
			throw new InvalidOperationException();
		}
		else
		{
			Count--;
			if (dequeueStack.Count==0)
			{
				EnqueueToDequeue();
			}

			return dequeueStack.Pop();
		}
	}

	private void EnqueueToDequeue()
	{
		while (enqueueStack.Count>0)
		{
			dequeueStack.Push(enqueueStack.Pop());
		}
	}
}

发表于 分类于 ， Disqus：

栈是先进后出，队列先进先出，问题在于如何在队列中找到最后一个进队列的元素。好在有两个队列。从一个队列往另外一个队列里面转移数据，转移到剩余一个的时候，就弹出该元素。压入栈比较简单，向正在使用的队列里面插入一个元素就可以了。

入栈的时间复杂度和普通的栈一致O(1)，但是出栈就是要把装有数据的队列操作一遍，复杂度是O(n)，其中n是队列中元素的个数。

下面是C#实现代码： 

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
public class StackWith2Queues<T>
{
	private Queue<T> curQueue;
	private Queue<T> otherQueue;

	public StackWith2Queues()
	{
		curQueue = new Queue<T>();
		otherQueue = new Queue<T>();
	}

	public int Count { get; private set; }

	public bool Empty { get { return Count == 0; } }

	public void Push(T item)
	{
		curQueue.Enqueue(item);
		Count++;
	}

	public T Peek()
	{
		if (Empty)
		{
			throw new InvalidOperationException();
		}
		else
		{
			while (curQueue.Count > 1)
			{
				otherQueue.Enqueue(curQueue.Dequeue());
			}

			T result = curQueue.Dequeue();
			otherQueue.Enqueue(result);
			SwapQueue();
			return result;
		}
	}

	public T Pop()
	{
		if (Empty)
		{
			throw new InvalidOperationException();
		}
		else
		{
			Count--;
			while (curQueue.Count > 1)
			{
				otherQueue.Enqueue(curQueue.Dequeue());
			}

			T result = curQueue.Dequeue();
			SwapQueue();
			return result;
		}
	}

	private void SwapQueue()
	{
		var tmp = curQueue;
		curQueue = otherQueue;
		otherQueue = tmp;
	}
}