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

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)"函数，这个函数必须在打印结束时调用，当函数returns但是那一刻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 );
    }
}

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

Problem while transforming an iterative function that prints a Queue into a recursive one

c

queue

recursion

function-definition