如何遍历C++中的Stack

由于 stack 的特性，你只有弹出（pop）了最上面的一个元素，才能看到紧接着的一个元素。
因此，你要遍历 stack 的话，就要一个一个的弹出（pop）最上面的元素，当 stack 变空的时候，你也就遍历 stack 了。

可以看到，你只能遍历 stack 一次，然后 stack 就变成空的了。

//遍历先序二叉树（非递归）
//访问T->data后，将T入栈，遍历左子树；
//遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。
void preorder_stack(Bitnode *t)
{
Bitnode *stack[MAXN];
int top = -1;
while(t || top!=-1)
{
while(t)
{
printf("%c",t->data);
stack[++top] = t;
t = t->lchild;
}
if(top != -1)
{
t = stack[top--];
t = t->rchild;
}
}
}

//遍历中序二叉树（非递归）
//先将T入栈，遍历左子树；
//遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。
void inorder_stack(Bitnode *t)
{
Bitnode *stack[MAXN];
int top = -1;
while(t || top!=-1)
{
while(t)
{
stack[++top] = t;
t = t->lchild;
}
if(top != -1)
{
t = stack[top--];
printf("%c",t->data);
t = t->rchild;
}
}
}

//遍历后序二叉树（非递归）
//可采用标记法，结点入栈时，配一个标志tag一同入栈(0：遍历左子树前的现场保护，1：遍历右子树前的现场保护)。
//首先将T和tag(为0)入栈，遍历左子树；返回后，修改栈顶tag为1，遍历右子树；最后访问根结点。
void postorder_stack(Bitnode *t)
{
Bitnode *stack[MAXN];
bool tag[MAXN];
int top = -1;
while(t || top!=-1)
{
while(t)
{
stack[++top] = t;
tag[top] = 0;
t = t->lchild;
}
while(top!=-1 && tag[top] == 1)
{
t = stack[top--];
printf("%c",t->data);
}
if(top != -1)
{
tag[top] = 1;// 设置栈顶标记
t = stack[top];// 取栈顶保存的指针
t = t->rchild;
}
else break;
}
}