algorithm - 以非常规方式反转队列

Question

假设我有一个队列，里面装满了某种类型的元素，并且它们的填充方式是，如果任何两个元素被指定的比较器评估为相同，它们将彼此相邻。

现在我想按以下方式反转队列:如果队列中的所有元素都是唯一的，则将其反转为反转的正常定义。

如果有一些元素是相同的(考虑到它们的填充方式，它们将彼此相邻)，则反转队列但保持非唯一元素的相对位置不变。

图表可能更容易理解问题所在。

如果队列如下:

[11 22 33 44 55]

我的比较器通过查看他们的第一个数字来比较两个整数，然后上面队列的反向将是:

[55 44 33 22 11]

但是，如果我的输入队列是:

[11 22 23 44 55]

反过来应该是:

[55 44 22 23 11]

给定比较器。

我正在尝试以递归方式执行此操作，仅使用一个堆栈作为附加辅助存储。但是，我很难找到正确有效的方法。能否请你帮忙？非常感谢!

PS:我使用堆栈作为额外存储的原因是因为使用堆栈最容易以传统方式反转队列(出列并将所有内容压入堆栈，然后弹出并重新入列到队列中)。

Answer 1

方法 1)

首先反转整个队列(不考虑 21,22 等的相等性)，然后使用堆栈反转每个单独的 block (即 21,22 等)。这可以迭代完成。

这类似于句子问题(著名面试问题)中的反向单词。

(参见下面的示例和伪代码)

方法 2)

如果你绝对想做递归，那么我建议你使用队列作为你的辅助存储，而不是堆栈。

您将一个 block 排入辅助队列，递归地反转列表的其余部分，然后将元素排回主队列。

代码将是这样的(handwavy pseudo)

StrangeReverse(Queue <T> q) {
    Queue<T> aux;
    // this removes first block from q, and places them in aux
    while (elem_of_first_block(q)) {
        aux.Enque(elem);
    }
    // Recursively reverse the rest of the q.
    StrangeReverse(q);

    // place the first block back in q, at the end.
    // in the order they appeared originally.
    while (aux.HasElements()) {
        q.Enque(aux.Deque());
    }
}

递归版本可以通过队列堆栈转换为迭代版本!您从每个 block 中创建一个队列，并将它们堆叠起来。然后出栈，使用队列。

方法 1 的示例

[11, 12, 21, 22, 43, 44]

反转这个(使用堆栈或通过递归方法)

[44, 43, 22, 21, 12, 11]

现在反转每个 block :

push 44, the 43.

堆栈 = [44, 43]。队列 = [22, 21, 12, 11]

现在从栈中弹出Enque

堆栈 = []，队列 = [22, 21, 12, 11, 43, 44]

推送 22、21

堆栈 = [22, 21]，队列 = [12, 11, 43, 44]

通过弹出堆栈进行查询。

堆栈 = []，队列 = [12, 11, 43, 44, 21, 22]

最后我们得到

[43, 44, 21, 22, 11, 12]

注意:要确定一个 block ，您可能需要对队列使用 peek 方法。

方法一的伪代码

void StrangeReverse(Queue<T> q) {
    Stack<T> s;
    int count = q.Count();
    if (count < 2) return;
    for (i = 0; i < count; i++) {
        T elem = q.Deque();
        s.Push(elem);
    }    
    while (s.HasElements()) {
        T elem = s.Pop();
        q.Enque(elem);
    }
    // Now the queue has been reversed,
    // in the normal fashion.
    ReverseBlocks(q);
}

void ReverseBlocks(Queue<T> q) {
    int reversed = 0;
    int count = q.Count();
    while (reversed < count) {
        reversed += ReverseSingleBlock(q);
    }
}

int ReverseSingleBlock(Queue <T> q) {
    Stack <T> s;
    T prevElem = q.Deque();
    s.Push(prevElem);
    T curElem = q.Peek();
    while(curElem == prevElem) {
        s.Push(curElem);
        q.Deque();
        prevElem = curElem;
        curElem = q.Peek();
    }
    int count = 0;
    while(s.HasElements()) {
        T elem = s.Pop();
        q.Enque(elem);
        count++;
    }
    return count;
}