4

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

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

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

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

如果队列如下：

[11 22 33 44 55]

我的比较器通过查看它们的第一个数字来比较两个整数，那么上面队列的反面将是：

[55 44 33 22 11]

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

[11 22 23 44 55]

相反的应该是：

[55 44 22 23 11]

给定比较器。

我正在尝试以递归方式执行此操作，只有一个堆栈作为额外的辅助存储。但是，我很难找出正确有效的方法。能否请你帮忙？非常感谢你！

PS：我使用堆栈作为额外存储的原因是因为以传统方式反转队列最容易使用堆栈完成（出列并将所有内容推入堆栈，然后弹出并入队返回队列）。

4

4 回答 4

2

方法 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]

注意：要确定一个块，您可能需要在队列上使用 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;
}
于 2013-03-22T08:29:01.553 回答
0

仍然假设： enque -> [11,21,22,23,30] -> deque/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());
}

所以首先我正在旋转队列，改变“等效”元素的顺序，最后我正在做一个普通的队列反向

于 2013-03-22T04:36:09.683 回答
0 
 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.enQueue("第一")

myQueue.enQueue("第二个")

myQueue.enQueue("第三个")

myQueue.enQueue("第四")

myQueue.enQueue("第五个")

打印 myQueue.que

myQueue.reverse()

打印 myQueue.que

于 2016-12-13T15:56:39.333 回答
0

这是使用递归反转 C++ STL 队列的代码片段。

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

        reverseQueue(q);

        q.push(value);
        break;
    }
}
于 2017-09-02T01:54:24.980 回答