以非常规方式颠倒队列

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等），然后反转每个块（即， 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]

现在Enque从堆栈中弹出

Stack = [], Queue = [22, 21, 12, 11, 43, 44]

push 22, 21

Stack = [22, 21], Queue = [12, 11, 43, 44]

Enque通过弹出堆栈。

Stack = [], Queue = [12, 11, 43, 44, 21, 22]

最终我们得到

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

注：确定块，你可能需要在队列偷看方法。

伪方法的代码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; 
} 

Answer 2

仍然假设： enque - > [11,21,22,23,30] - >双端队列/ PEEK
应该更好现在：

first = queue.peek(); 
start = true; 
while (queue.peek() != first || start) { 
    start = false; 
    el = queue.deque(); 
    if (el.compare(queue.peek())) { 
    stack.push(el); 
    while (el.compare(queue.peek())) { 
     el1 = queue.dequeue(); 
     if (first.compare(el1)) { 
     first = el1; 
     } 
     stack.push(el1); 
    } 
    while (!stack.isEmpty()) { 
     queue.enque(stack.pop());  
    } 
    } else { 
    queue.enque(el); 
    } 
} 
while (!queue.isEmpty()) { 
    stack.push(queue.deque()); 
} 
while (!stack.isEmpty()) { 
    queue.enque(stack.pop()); 
} 

所以第一即时旋转队列，变）的“等效”元件 最后我做普通的队列的次序相反

Answer 3

class ReverseQueue(object): 
    def __init__(self, limit=5): 
     self.rear = None 
     self.front = None 
     self.que = [] 
     self.size = 0 
     self.limit = limit 

    def enQueue(self, item): 
     if self.size >= self.limit: 
      print "Queue Overflow" 
      return 
     else: 
      self.que.append(item) 

     # two case 
     # 1. if front is None then the queue is empty. 
     # so if item is added both front 
     # end point to the same position i.e 0 
     # 2. if front is not None then item is added to the end of the 
     # list(append does that). we then increase the size of rear 

     # note: rear is 0 indexed but size is not 
     # that's why there's a diff of 1 always b/w these rear and size 
     if self.front is None: 
      self.rear = self.front = 0 
      self.size = 1 
     else: 
      self.rear = self.size 
      self.size += 1 

     return 

    def deQueue(self): 
      if self.size <= 0: 
       print "Queue Underflow" 
       return 
      else: 
       temp = self.que.pop(0) 

      # change the size 
      self.size -= 1 

      # if list is empty set both front and rear = None 
      # This is in sync with the queue method 
      # where we check if front = none when adding item 
      # change front and rear 
      if self.size is 0: 
      # if only one element 
      self.rear = self.front = None 
      else: 
      # more then one element 
      self.rear -= 1 

      return temp 

     def isEmpty(self): 
      return self.size <= 0 

     def reverse(self): 
      if not self.isEmpty(): 
       temp = self.deQueue() 
       self.reverse() 
       self.enQueue(temp) 

myQueue中= ReverseQueue（）

myQueue.enQueue（ “第一”）

myQueue.enQueue（ “第二”） （“第三”）

myQueue.enQueue（ “四”）

myQueue.enQueue（ “十五”）

打印myQueue.que

myQueue中。反向（）

打印myQueue.que

Answer 4

这里是一个代码段使用递归扭转一个C++ STL队列。

void reverseQueue(queue<int>& q){ 
    while(q.size() != 0){ 
     q.pop(); 

     reverseQueue(q); 

     q.push(value); 
     break; 
    } 
}