- 包含min函数的栈
题目:定义栈的数据结构,在其中实现一个能够得到栈的最小元素的min函数。在该栈中,调用min、push和pop的时间复杂度都是O(1)。
分析:使用一个辅助栈来存入当前栈的最小值,适当改进后不用重复插入辅助栈相同的数据。插入的值小于等于min,s2就push,弹出的值就是min,s2就pop。
class StackWithMin { private: stack<int> MinStack; //数据栈 stack<int> MinElement;//辅助栈 public: void push(const int&); int pop(); int min(); }; void StackWithMin::push(const int& value) { MinStack.push(value); //<=插入两个相等的数 if(MinElement.size() == 0 || value <= MinElement.top()) MinElement.push(value); } int StackWithMin::pop() { assert(MinStack.size()>0 && MinElement.size()>0); int temp = MinStack.top(); MinStack.pop(); if(temp == MinElement.top()) MinElement.pop(); return temp; } int StackWithMin::min() { assert(MinStack.size()>0 && MinElement.size()>0); return MinElement.top(); } int main() { StackWithMin test; test.push(3); test.push(4); test.push(2); test.push(1); cout << test.min()<<endl; test.pop(); cout<< test.min()<<endl; test.pop(); cout<< test.min()<<endl; test.push(0); cout<< test.min()<<endl; return 0; }
- 用两个栈实现队列
题目:用两个栈实现一个队列,队列声明如下,请实现它的两个函数appendTail和deleteHead,分别完成在队列尾部插入节点和在队列头部删除节点的功能。
template <typename T> class CQueue { public: CQueue(void); ~CQueue(void); void appendTail(const T& node); T deleteHead(); private: stack<T> stack1; stack<T> stack2; };
分析:进队列appendTail–直接压入stack1
出队列deleteHead–stack2非空则直接弹出元素,stack2空则将stack1元素倒入stack2中
template <typename T> void CQueue<T>::appendTail(const T& element) { stack1.push(element); } template <typename T> T CQueue<T>::deleteHead() { if(stack2.size()<=0) { while(stack1.size()>0) { T& data = stack1.top(); stack1.pop(); stack2.push(data); } } if(stack2.size() == 0) throw new exception("queue is empty"); T head = stack2.top(); stack2.pop(); return head; }
延伸:如何用两个队列实现一个栈
入栈push–所有元素依次进入一个非空队列(首次直接进入队列queue1)
出栈pop–判断栈元素个数是否为1,如果为1,队列直接出列;如果不为1,所有元素(除最后一个元素)出队列进入另一个空队列,最后一个元素pop。
两队列互相循环,新push进来的元素总是插入到非空队列中,空队列则用来保存pop操作之后的元素,此时空队列就不为空了,原来的非空队列变为空队列。 - 栈的压入、弹出序列
题目:输入两个整数序列,第一个序列表示栈的压入顺序,判断第二个序列是否为该栈的弹出顺序。假设压入的数字均不相等。
分析:如果下一个弹出的数字刚好是栈顶数字,那么直接弹出;如果不在栈顶,就把压栈序列中还没有入栈的数字压入辅助栈,知道把下一个需要弹出的数字压入栈顶为止。如果所有的数字都压入栈了仍没有找到下一个弹出的数字,那该序列就不是一个弹出序列。
bool IsPoporder(const int *push,const int *pop,int length) { bool flag = false; if(push != NULL && pop != NULL && length > 0) { std::stack<int> stack; const int *nextPush = push; const int *nextPop = pop; while(nextPop - pop < length) { while(stack.empty() || stack.top() != *nextPop) { //下一个弹出的数字不在栈顶,把push序列中为入栈的压入栈 if(nextPush - push == length) break;//所有数字都已压入 stack.push(*nextPush); nextPush++; } if(stack.top() != *nextPop) break; stack.pop(); // 找到=nextPop的 nextPop ++; } if(stack.empty() && nextPop-pop == length) flag = true; } return flag; } int main() { int a[5] = {1,2,3,4,5}; int b[5] = {4,5,3,2,1}; int c[5] = {4,3,5,1,2}; cout << IsPoporder(a,b,5)<<endl; cout << IsPoporder(a,c,5)<<endl; return 0; }
- 用一个数组实现三个堆栈
解法一:将数组划分成3等份,每一份独立的用来实现堆栈。大小固定。stack1: [0,n/3), stack2: [n/3,2n/3), stack3: [2n/3,n).
解法二:数组中如果还有空余的空间,堆栈就还能增长。每次为堆栈分配一个空间的时候,在这个新空间中记录上一个空间地址。这样堆栈中的每个元素都有一个指针指向之前的元素。这样的实现方法有一个问题就是如果一个堆栈弹出一个空间(释放空间),这个空间并不会作为空闲空间现在数组后面。这样话我们就不能使用新产生的空闲空间。为了解决这个问题,我们用一个列表来记录空闲的空间。当有新空闲空间出现,我们就把它加入到这个表中。如果需要新分配一个空间,就从这个表中删除一个元素。这样的实现方法使得3个堆栈能够动态的使用数组的空间,但是这是以增大空间复杂度换来的。 - 堆栈池
SetOfStack当中包含很多的堆栈,当一个堆栈达到上限的时候,启用下一个堆栈。SetOfStack.push 和 SetOfStack.pop应该和普通堆栈的操作一样。实现一个函数popAt(int index),指定在哪个堆栈上弹出元素。
push:每次push()都必须将元素放到最近使用的一个堆栈中,如果这个堆栈已经满了,就必须创建一个新的堆栈然后再入栈。
pop:也在最近的一个堆栈上操作,如果最后一个堆栈是空的话,就应该将其移除。
popAt(int index):需要翻转。我pass了。 - 经典的汉诺塔问题
题目:有3根柱子,柱子上串有N个 尺寸不同的碟子。汉诺塔问题的起始状态为,所有的碟子都从小到大的穿在柱子上(下面的碟子最大)。在满足下面三个限制:(A) 每次只能移动一个碟子;(B) 只有每根柱子顶端的碟子才能移动;(C)任何碟子只能放在比它大的碟子上。写一段程序(要求使用堆栈),将第一个根柱子上所有的碟子移动到移到最后一根柱 子上。
分析:经典递归,Hannoi(n,a,b,c)分解为三步:
1)Hannoi(n-1,a,c,b)–将塔A上的n-1个碟子借助塔C移到塔B
2)move(n,a,c)–将塔A剩余的一个碟子移至塔C
3)Hannoi(n-1,b,a,c)–将n-1个碟子从塔B借助塔A移到塔C - 将堆栈升序排序。
题目:该堆栈就是一个普通的堆栈,不能有其他假设。函数实现是只能调用函数push(),pop(),peek()和isEmpty这几个函数。
分析:再建一个堆栈,从原堆栈中弹出一个元素到新的堆栈中。然后再比较原堆栈栈顶元素和新堆栈栈顶大小。如果符合排序规则,再次入新堆栈。如果不符合,在弹出新堆栈中的元素逐个比较直到满足排序关系。这样类似插入排序的方法,之间复杂度为O(n^2)。stack<int> sort(stack<int> s) { stack<int> r; while(!s.empty()) { int tmp = s.pop();//原堆栈 while(!r.empty()&&r.peek()>tmp) s.push(r.pop()); r.push(tmp); } return r; }