アプローチ 1)
最初にキュー全体を反転し (21、22 などの等価性を考慮せずに)、次にスタックを使用して個々のブロック (つまり 21、22 など) を反転します。これは繰り返し行うことができます。
これは、文の問題（有名なインタビューの質問）の逆の単語に似ています。
(以下の例と疑似コードを参照してください)
アプローチ 2)
絶対に再帰を行いたい場合は、スタックではなくキューを補助ストレージとして使用することをお勧めします。
ブロックを補助キューにエンキューし、リストの残りを再帰的に反転してから、要素をメイン キューにエンキューします。
コードはこのようなものになります（handwavy疑似）
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());
}
}
再帰的なバージョンは、キューのスタックを持つことで反復的に変換できます! 各ブロックからキューを作成し、それらを積み重ねます。次に、スタックをポップし、キューを使用します。
アプローチ 1 の具体例
[11, 12, 21, 22, 43, 44]
これを逆にします（スタックを使用するか、再帰的な方法で）
[44, 43, 22, 21, 12, 11]
次に、各ブロックを逆にします。
push 44, the 43.
Stack = [44, 43]. Queue = [22, 21, 12, 11]
スタックからポップしてエンキューする
Stack = [], Queue = [22, 21, 12, 11, 43, 44]
push 22, 21
Stack = [22, 21], Queue = [12, 11, 43, 44]
スタックをポップしてエンキューします。
Stack = [], Queue = [12, 11, 43, 44, 21, 22]
最後に、
[43, 44, 21, 22, 11, 12]
注: ブロックを特定するには、Queue の peek メソッドが必要になる場合があります。
アプローチ1の疑似コード
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;
}