c-将打印队列的迭代函数转换为递归函数时的问题

Question

我有一个显示队列的迭代函数：

void displayQueue(queue *Q){
int temp;
while(!isEmpty(Q)){
temp = dequeue(Q);
printf("%d -> ", temp);
displayQueue(Q);
enqueue(Q, temp);
}
reverse(Q);
}

我想通过删除while循环来使它完全递归，这就是我迄今为止得到的：

void displayQueue(queue *Q){
if(isEmpty(Q)) return;
int temp = dequeue(Q);
printf("%d -> ", temp);
displayQueue(Q);
enqueue(Q, temp);
}

问题是何时调用"reverse(Q("函数，当函数返回时，必须在打印结束时调用该函数，但此时Q为空，因此不会被反转(队列的打印导致其反转(

这是我的队列结构：

typedef struct queue{
unsigned capacity;
int size;
int front;
int rear;
int *array;
}queue;

Answer 1

看起来函数应该以的方式

void displayQueue( queue *Q )
{
if ( !isEmpty( Q ) )
{
int temp = dequeue( Q );
printf( "%d -> ", temp );
displayQueue( Q );
reverse( Q );
enqueue( Q, temp );
reverse( Q );
}
}

如果你想避免经常反转队列，那么你可以用静态变量来编写函数，例如

void displayQueue( queue *Q )
{
static int state = 0;
if ( !isEmpty( Q ) )
{
int to_reverse = state ^ 1;
if ( to_reverse ) state = to_reverse;
int temp = dequeue( Q );
printf( "%d -> ", temp );
displayQueue( Q );
enqueue( Q, temp );
if ( to_reverse )
{
reverse( Q );
state = 0;
}
}
}

如果没有静态变量，您可以编写将其拆分为两个函数的函数。第一个调用递归函数并反转结果。第二个是显示队列的递归函数。

例如

void recursiveDisplayQueue( queue *Q )
{
if ( !isEmpty( Q ) )
{
int temp = dequeue( Q );
printf( "%d -> ", temp );
recursiveDisplayQueue( Q );
enqueue( Q, temp );
}
}
void displayQueue( queue *Q )
{
if ( !isEmpty( Q ) )
{
recursiveDisplayQueue( Q );
reverse( Q );
}
}