STL очереди поп-путаницы - PullRequest
Новая
       20

STL очереди поп-путаницы

0 голосов
/ 06 ноября 2018

Я немного смущен тем, как работает функциональность всплывающих очередей, я полагаю.

Во-первых, я не уверен, как реализована очередь, будь то связанный список или очередь. Но если это связанный список, pop () удалит передний узел, удаляя узел (включая данные, верно?), Поэтому, когда мы попадаем в цикл while, мы устанавливаем наш темп равным началу очереди, а затем немедленно поп? Не совсем имеет смысл для меня; Тем не менее, я проверил это, добавив несколько узлов, затем напечатав дерево, и все выглядело так, как ожидалось.

Я ожидал неопределенного поведения, так как мы открываем фронт, затем пытаемся получить доступ к левому и правому узлам фронта, но фронт только что вытолкнулся.

Я думаю, что было бы больше смысла, если бы мы выдавали в конце цикла while, а затем переназначали наш rootTemp на front.

Наверное, мой главный вопрос: почему это работает?

Этот код взят из https://www.geeksforgeeks.org/insertion-in-a-binary-tree-in-level-order/

/*function to insert element in binary tree */
void insert(struct Node* temp, int key) 
{ 
    queue<struct Node*> q; 
    q.push(temp); 

    // Do level order traversal until we find 
    // an empty place.  
    while (!q.empty()) { 
        struct Node* temp = q.front(); 
        q.pop(); 

      if (!temp->left) { 
        temp->left = newNode(key); 
        break; 
      } else
        q.push(temp->left); 

      if (!temp->right) { 
        temp->right = newNode(key); 
        break; 
      } else
        q.push(temp->right); 
    } 
}

Ценю любую помощь, спасибо!

1 Ответ

0 голосов
/ 06 ноября 2018

Это работает, потому что очередь содержит только указатели на Node с. При обращении к front возвращается копия указателя. Когда очередь pop 'ed, уничтожается только указатель, а не указатель на Node.

std::queue реализация по умолчанию - std::deque - но это можно изменить, установив параметр шаблона.

...