10-1-2：
两个栈分别从数组的两端开始，向中间扩展；
10-1-5：
这个deque的代码以前的实现过（c++ STL），这里就不写了。这里的head和tail一开始都指向数组的中间位置即可；
10-1-6：
栈是先进后出，队列是先进先出，
对于由两个栈实现一个队列，根据负负得正的原则，一开始先将元素加入栈1，等到删除元素时，先将元素删除到栈2，然后通过栈2出栈，然后继续，等到栈2中的元素都删除完了，再进行栈1元素全部清空到栈2。
这里使用stack类构造queue类，参见栈和队列代码，
其中对于stack代码的改动是添加friend声明；
template<typename T,typename Alloc=alloc>
class queue
{
private:
stack<T,Alloc> _stack1;
stack<T,Alloc> _stack2;
int capacity;
public:
queue(int queueCapacity=10);//构造队列，默认容量为10；
bool Empty() const{return _stack1.Empty() && _stack2.Empty();}
T& Front() ;//返回队列头部元素
T& Rear() ;//返回队列尾部元素
void Push(const T& x);//插入元素，只能在队列尾部插入
void Pop();//删除元素，只能在队列头部删除
};
//----------------------------------------------------------------------------------------
template<typename T,typename Alloc>
queue<T,Alloc>::queue(int queueCapacity)
:capacity(queueCapacity)
{
if(capacity<1) throw"queue capacity must >0";
_stack1.capacity=queueCapacity;
_stack1.allocate_and_fill(10,T());
}
//-------------------------------------------------------------------------------------------
template<typename T,typename Alloc>
T& queue<T,Alloc>::Front()
{
if(Empty()) throw"queue is empty";
if(_stack2.Empty()){//此时栈2为空，我们需要获取的元素必然是栈2的栈顶元素，所以需要先把
//栈1中的元素全部清空到栈2,
T tmp;
while(!_stack1.Empty()){
tmp=_stack1.Top();
_stack2.Push(tmp);
_stack1.Pop();
}
}
return _stack2.Top();
}
//---------------------------------------------------------------------------------------------
template<typename T,typename Alloc>
T& queue<T,Alloc>::Rear()
{
if(Empty()) throw"queue is empty";
if(_stack1.Empty()){
return _stack2._stack[0];
}else{
return _stack1.Top();
}
}
//-------------------------------------------------------------------------------------------
template<typename T,typename Alloc>
inline void queue<T,Alloc>::Push(const T& x)
{
_stack1.Push(x);
}
//------------------------------------------------------------------------------------------ ----
template<typename T,typename Alloc>
void queue<T,Alloc>::Pop()
{
if(Empty()) throw" queue is empty";
if(_stack2.Empty()){//此时栈2为空，我们需要获取的元素必然是栈2的栈顶元素，所以需要先把
//栈1中的元素全部清空到栈2,
while(!_stack1.Empty()){
_stack2.Push(_stack1.Top());
_stack1.Pop();
}
}
_stack2.Pop();
}
10-1-7：
这里正正是不能得负的。
这里的实现很没有技巧性，看过别人的解题方法，都是一个思路，当要出栈的时候，就把一个队列中的前n-1个元素全部倾倒到另一个队列中，然后队列剩下的最后一个元素出栈；
或者从开始入栈的时候，两个队列中，其中一个是空队列，将值入这个空队列，然后将另一个非空队列的值依次取出并加入这个队列中；
10-2-8:
此处http://blog.csdn.net/mishifangxiangdefeng/article/details/7706631非常详细，主要是怎么由np获得prev和next
10-4-x：
//---------------------------------------------------------------------------------------
template<typename T>
struct _tree_node
{
T data;
_tree_node<T>* left_child;
_tree_node<T>* right_child;
_tree_node(T a=T(),_tree_node<T>* b=NULL,_tree_node<T>* c=NULL)
:data(a),left_child(b),right_child(c){ }
};
template<typename T,typename Alloc=alloc>
class tree
{
private:
typedef _tree_node<T> tree_node;
typedef simple_alloc<tree_node,Alloc> node_allocator;
//这里主要考虑的是树的遍历问题
public:
void Inorder(tree_node* current_node);//中序遍历
void Iterative_Inorder(tree_node* current_node);//迭代中序遍历
void Preorder(tree_node* current_node);//先序遍历
void Postorder(tree_node* current_node);//后序遍历
void level_order(tree_node* current_node);//层次遍历
private:
tree_node* root;
private:
void Visit(tree_node* current_node);//表示访问某一节点
};
//-----------------------------------------------------------------------------------
template<typename T,typename Alloc>
void tree<T,Alloc>::Inorder(tree_node* current_node)
{
if(current_node){
Inorder(current_node->left_child);
Visit(current_node);
Inorder(current_node->right_child);
}
}
//-----------------------------------------------------------------------------------
template<typename T,typename Alloc>
void tree<T,Alloc>::Preorder(tree_node* current_node)
{
if(current_node){
Visit(current_node);
Preorder(current_node->left_child);
Preorder(current_node->right_child);
}
}
//--------------------------------------------------------------------------------
template<typename T,typename Alloc>
void tree<T,Alloc>::Postorder(tree_node* current_node)
{
if(current_node){
Postorder(current_node->left_child);
Postorder(current_node->right_child);
Visit(current_node);
}
}
//---------------------------------------------------------------------------------
//完全模拟的是递归算法的执行过程，由显式的程序调用栈转化为我们自己的栈
template<typename T,typename Alloc>
void tree<T,Alloc>::Iterative_Inorder(tree_node* current_node)
{
stack<tree_node*> s;
tree_node* _current_node=current_node;
while(1){
while(_current_node){
s.Push(_current_node);
_current_node=_current_node->left_child;
}
if(s.Empty()) return;
_current_node=s.Top();
s.Pop();
Visit(_current_node);
_current_node=_current_node->right_child;
}
}
//-------------------------------------------------------------------
//访问节点，此处我们是打印节点的值到cout
template<typename T,typename Alloc>
void tree<T,Alloc>::Visit(tree_node* current_node)
{
std::cout<<current_node->data<<' ';
}
//-----------------------------------------------------------------------------------------
//使用队列的思想
template<typename T,typename Alloc>
void tree<T,Alloc>::level_order(tree_node* current_node)
{
queue<tree_node*> q;
tree_node* _current_node=current_node;
while(_current_node){
Visit(_current_node);
if(_current_node->left_child) q.Push(_current_node->left_child);
if(_current_node->right_child) q.Push(_current_node->right_child);
if(q.Empty()) return;
_current_node=q.Front();
q.Pop();
}
}
//-------------------------------------------------------------------------------------
10-4-5：
这里要求的是使用固定量的额外空间，一种方法是增加parent域，但是这种方法会造成巨大的空间代价，远不如使用栈来的划算；
使用这种方法，仍然模拟的是中序遍历的执行过程，只是这里并不是使用栈，而是采用parent索引；
第二种方法是使用线索树：由于叶结点的left_child和right_child域都是没使用的，我们可以充分利用这些空间：
如果节点p的right_child为空，那么设置right_child指向p在中序遍历时的后继节点；
如果节点p的left_child为空，那么设置left_child指向p在中序遍历时的前驱节点；
同时节点增加两个域，bool型的：left_thread和right_thread，当值为true时，对应的孩子节点是线索；
10-4-6：
线索树