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 );
    }
}