数据结构基础

1、两个queue实现stack

解题思路

首先我们需要理一下队列和栈，队列特点是先进先出，栈的特点是先进后出，对应的基本操作：

队列的操作有：push 入队，front 取队首元素，pop 队首元素出队，empty 判断是否为空

栈的操作有：push 入栈，top 取栈顶元素，pop 栈顶元素出栈，empty 判断是否为空

用两个队列实现栈，最简单的思路是用第一个队列模拟栈，那么第一个队列的元素顺序应该和插入顺序是相反的。如果我们在每次插入元素时，将其放到第一个队列的队首，同时队列中原来的元素顺序保持不变（和插入顺序相反），那么就可以保证这个队列的出队顺序和栈的出栈顺序相同。

我们可以通过第二个队列来辅助实现，具体地，在插入一个元素时，先将其放到第二个队列（第二个队列在插入时为空，所以新元素在第二个队列的队首），接着将第一个队列里的元素依次放到第二个队列。那么此时第二个队列就满足新元素在队首，其它元素顺序保持不变。交换两个队列，就保证了第一个队列出队顺序和栈的出栈顺序相同，插入完第二个队列仍保持空。这样pop操作就可以直接用第一个队列的pop操作实现。

C++代码实现如下

class MyStack {
public:
 queue<int> queue_0;
 queue<int> queue_1;

 MyStack() {}

 void push(int value) {
 queue_1.push(value); // 插入到第二个队列
 while (!queue_0.empty()) { // 把第一个队列的元素全放到第二个队列
 queue_1.push(queue_0.front());
 queue_0.pop();
 }
 swap(queue_0, queue_1); // 交换
 }

 void pop() {
 queue_0.pop(); // 栈的出栈顺序和第一个队列的出队顺序相同
 }

 int top() {
 int value = queue_0.front(); // 第一个队列的队首就是栈顶
 return value;
 }

 bool empty() {
 return queue_0.empty(); // 栈的元素全放在第一个队列
 }
 
 int size() {
 return queue_0.size(); 
 }
};

队列的push、pop、front操作时间复杂度为O(1)，那么实现的栈的push操作复杂度为O(n)，pop和top操作时间复杂度为O(1)

扩展

用一个队列实现栈

此时队列中元素不借助额外数据结构是不能逆置的，但我们可以通过队列的size来知道栈顶在队列的第几个元素，然后我们就可以通过出队入队操作将栈顶元素移到队首。具体代码实现如下：

class MyStack {
public:
 queue<int> queue_0;
 queue<int> queue_1;

 MyStack() {}

 void push(int value) {
 queue_1.push(value);
 while (!queue_0.empty()) {
 queue_1.push(queue_0.front());
 queue_0.pop();
 }
 swap(queue_0, queue_1);
 }

 void pop() {
 queue_0.pop();
 }

 int top() {
 int value = queue_0.front();
 return value;
 }

 bool empty() {
 return queue_0.empty();
 }
};


class MyStack {
 queue<int> q;
public:
 MyStack() {
 while (!q.empty()) q.pop();
 }
 
 void push(int x) {
 q.push(x);
 }
 
 void pop() {
 int sz = q.size() - 1;
 while (sz--) {
 int tmp = q.front();
 q.pop();
 q.push(tmp);
 }
 q.pop();
 }
 
 int top() {
 int sz = q.size();
 int tmp;
 while (sz--) {
 tmp = q.front();
 q.pop();
 q.push(tmp);
 }
 return tmp;
 }
 
 bool empty() {
 return q.empty();
 }
};

此时插入复杂度O(1)，pop和top操作O(n)

另一个扩展：用两个栈实现队列

2、用随机产生7以内数字的函数去写随机产生10以内数字的函数

解答思路：只要产生了目标范围内的随机数，则直接返回，如果产生的随机数不在目标范围内，则丢弃该值，重新取样。由于目标范围内的数字被选中的概率相等，则获得了一个均匀分布。

假定rand7( )来获得rand10（），显然rand7需要至少执行2次，否则产生不了1-10的数字。通过执行rand7两次，可以获得1-49的整数。又因为49不是10的倍数，所以需要丢弃一些值。代码如下：

nt rand10() { 
 int row, col, idx; 
 do { 
 row = rand7(); 
 col = rand7(); 
 idx = col + (row-1)*7; 
 } while (idx > 40); 
 return 1 + (idx-1)%10; 
}

由于row范围为1-7，col范围为1-7，则idx值范围是1-49，大于40的值被丢弃，这样剩下1-40范围内的数字，通过取模，最后返回10以内范围结果。

优化：

对于大于40的数，不一定马上丢弃，可以对41-49的数减去40可得到1-9的随机数，而rand7可以产生1-7的随机数，这样可以生成1-63的随机数，对于1-60可以直接返回，而61-63丢弃，则需要丢弃的数只有3个，相比之前的9个效率有所提升。而对于61-63的数，减去60后为1-3，rand产生1-7，这样可以再利用产生1-21的数，对于1-20直接返回，对于21直接丢弃，这样丢弃的数只剩一个，又可优化效率。代码如下：

int rand10Imp() {
 int a, b, idx;
 while (true) {
 a = rand7();
 b = rand7();
 idx = b + (a-1)*7;
 if (idx <= 40)
 return 1 + (idx-1)%10;
 a = idx-40;
 b = rand7();
 // 得到分布 1 - 63
 idx = b + (a-1)*7;
 if (idx <= 60)
 return 1 + (idx-1)%10;
 a = idx-60;
 b = rand7();
 // 得到分布 1-21
 idx = b + (a-1)*7;
 if (idx <= 20)
 return 1 + (idx-1)%10;
 }
}