- 包含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; }