Cracking the coding interview--Q3.3

Hawstein | December 20, 2012

题目

原文:

Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOfStacks should be composed of several stacks, and should create a new stack once the previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack).

FOLLOW UP

Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.

译文:

栈就像叠盘子,当盘子叠得太高时,就会倾斜倒下。因此,在真实的世界中,当一叠盘子 (栈)超过了一定的高度时,我们就会另起一堆,再从头叠起。实现数据结构SetOfStacks 来模拟这种情况。SetOfStacks由几个栈组成,当前一栈超出容量时,需要创建一个新的栈 来存放数据。SetOfStacks.push()和SetOfStacks.pop()的行为应当和只有一个栈时 表现的一样。

进一步地,

实现函数popAt(int index)在指定的子栈上进行pop操作。

解答

首先,我们如果不考虑popAt这个麻烦的函数,那么SetOfStacks的实现就简单很多。 SetOfStacks由栈的数组构成,我们需要一个指向当前栈的变量cur, 每当执行push操作时,我们需要检查一下当前栈是否已经达到其容量了, 如果是的话,就要将cur加1,指向下一个栈。而执行pop操作时, 需要先检查当前栈是否为空,如果是,则cur减1,移向上一个栈。top操作同理。 这时候,SetOfStacks可以想象成把一个本来可以叠得很高的栈,分成了好几个子栈。 push和pop操作其实都只是在“最后”一个子栈上操作。

代码如下:

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 SetOfStacks{//without popAt()
private:
	stack *st;
	int cur;
	int capacity;

public:
	SetOfStacks(int capa=STACK_NUM){
		st = new stack[capa];
		cur = 0;
		capacity = capa;
	}
	~SetOfStacks(){
		delete[] st;
	}
	void push(int val){
		if(st[cur].full()) ++cur;
		st[cur].push(val);
	}
	void pop(){
		if(st[cur].empty()) --cur;
		st[cur].pop();
	}
	int top(){
		if(st[cur].empty()) --cur;
		return st[cur].top();
	}
	bool empty(){
		if(cur==0) return st[0].empty();
		else return false;
	}
	bool full(){
		if(cur==capacity-1) return st[cur].full();
		else return false;
	}    
};

当加入popAt函数,情况就变得复杂了。因为这时候的数据分布可能出现中间的某些子栈使 用popAt把它们清空了,而后面的子栈却有数据。为了实现方便,我们不考虑因为popAt 带来的空间浪费。即如果我用popAt把中间某些子栈清空了,并不把后面子栈的数据往前移 动。这样一来,cur指向操作的“最后”一个栈,它后面的子栈一定都是空的, 而它本身及前面的子栈由于popAt函数的缘故都有可能是空的。如果没有popAt函数, cur前面的子栈一定都是满的(见上面的例子)。这样一来,push仍然只需要判断一次当前子 栈是否为满。但是,pop函数则要从cur向前一直寻找,直到找到一个非空的子栈, 才能进行pop操作。同理,popAt,top,empty也是一样的。

代码如下:

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
class SetOfStacks1{
private:
	stack *st;
	int cur;
	int capacity;

public:
	SetOfStacks1(int capa=STACK_NUM){
		st = new stack[capa];
		cur = 0;
		capacity = capa;
	}
	~SetOfStacks1(){
		delete[] st;
	}
	void push(int val){
		if(st[cur].full()) ++cur;
		st[cur].push(val);
	}
	void pop(){
		while(st[cur].empty()) --cur;
		st[cur].pop();
	}
	void popAt(int idx){
		while(st[idx].empty()) --idx;
		st[idx].pop();
	}
	int top(){
		while(st[cur].empty()) --cur;
		return st[cur].top();
	}
	bool empty(){
		while(cur!=-1 && st[cur].empty()) --cur;
		if(cur==-1) return true;
		else return false;
	}
	bool full(){
		if(cur==capacity-1) return st[cur].full();
		else return false;        
	}
};

完整代码如下:

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <iostream>
using namespace std;

const int STACK_SIZE = 100;
const int STACK_NUM = 10;
class stack{
private:
	int *buf;
	int cur;
	int capacity;

public:
	stack(int capa = STACK_SIZE){
		buf = new int[capa];
		cur = -1;
		capacity = capa;
	}
	~stack(){
		delete[] buf;
	}
	void push(int val){
		buf[++cur] = val;
	}
	void pop(){
		--cur;
	}
	int top(){
		return buf[cur];
	}
	bool empty(){
		return cur==-1;
	}
	bool full(){
		return cur==capacity-1;
	}
};

class SetOfStacks{//without popAt()
private:
	stack *st;
	int cur;
	int capacity;

public:
	SetOfStacks(int capa=STACK_NUM){
		st = new stack[capa];
		cur = 0;
		capacity = capa;
	}
	~SetOfStacks(){
		delete[] st;
	}
	void push(int val){
		if(st[cur].full()) ++cur;
		st[cur].push(val);
	}
	void pop(){
		if(st[cur].empty()) --cur;
		st[cur].pop();
	}
	int top(){
		if(st[cur].empty()) --cur;
		return st[cur].top();
	}
	bool empty(){
		if(cur==0) return st[0].empty();
		else return false;
	}
	bool full(){
		if(cur==capacity-1) return st[cur].full();
		else return false;
	}    
};
class SetOfStacks1{
private:
	stack *st;
	int cur;
	int capacity;

public:
	SetOfStacks1(int capa=STACK_NUM){
		st = new stack[capa];
		cur = 0;
		capacity = capa;
	}
	~SetOfStacks1(){
		delete[] st;
	}
	void push(int val){
		if(st[cur].full()) ++cur;
		st[cur].push(val);
	}
	void pop(){
		while(st[cur].empty()) --cur;
		st[cur].pop();
	}
	void popAt(int idx){
		while(st[idx].empty()) --idx;
		st[idx].pop();
	}
	int top(){
		while(st[cur].empty()) --cur;
		return st[cur].top();
	}
	bool empty(){
		while(cur!=-1 && st[cur].empty()) --cur;
		if(cur==-1) return true;
		else return false;
	}
	bool full(){
		if(cur==capacity-1) return st[cur].full();
		else return false;        
	}
};
int main(){
	// SetOfStacks ss;
	// for(int i=0; i<STACK_SIZE+1; ++i){
	//     ss.push(i);
	// }
	// while(!ss.empty()){
	//     cout<<ss.top()<<endl;
	//     ss.pop();
	// }
	SetOfStacks1 ss1;
	for(int i=0; i<3*STACK_SIZE+1; ++i){
		ss1.push(i);
	}
	for(int i=0; i<STACK_SIZE; ++i){
		ss1.popAt(0);
		//ss1.popAt(1);
		ss1.popAt(2);
	}
	ss1.popAt(3);
	while(!ss1.empty()){
		cout<<ss1.top()<<endl;
		ss1.pop();
	}

	return 0;
}

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview

版权声明:自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证,转载请注明作者及出处。