Моя очередь не обновляется, так как я ставлю в очередь

Question

Я изучаю очереди, и я борюсь за эту реализацию со связанным списком. Ниже в моем коде я пытаюсь реализовать методы en-queue и de-queue, но когда я реализую эти методы, мой список ссылок не обновляется. Я чувствую, что это как-то связано с моими указателями. Любой совет или помощь будет принята с благодарностью.

#include <iostream>
using namespace std;

// A linked list node 
class Node 
{ 
  public:
    int data; 
    Node *next;
    Node()
    {
      data = 0;
      next = nullptr;
    }
    Node(int data)
    {
      this->data = data;
      next = nullptr;
    }
}; 

class List 
{ 
  public:
    struct Node* head;
    struct Node* tail;
    List()
    {
      head = tail = nullptr;
    }
}; 

void ListPrint(List *list)
{
  Node *tempNode = list->head;
  while(tempNode != nullptr){
    cout<<tempNode->data<<",";
    tempNode = tempNode->next;

  }
}


void ListAppend(List *list, Node *newNode)
{
   if(list->head == nullptr)
   {
      list->head = newNode;
      list->tail = newNode;
   }
   else{
      list->tail->next = newNode;
      list->tail = newNode;
   }
}

void ListRemoveAfter(List *list, Node *curNode) {
   // Special case, remove head
   Node *sucNode;
   if (curNode == nullptr && list->head != nullptr) {
      sucNode = list->head->next;
      //delete(list->head);
      list->head = sucNode;

      if (sucNode == nullptr) { // Removed last item
         list->tail = nullptr;
      }
   }
   else if (curNode->next != nullptr) {
      sucNode = curNode->next->next;
      //delete(curNode->next);
      curNode->next = sucNode;

      if (sucNode == nullptr) { // Removed tail
         list->tail = curNode;
      }
   }
}
void enqueue(List *queue, Node *newItem)
{
  ListAppend(queue, newItem);
  ListPrint(queue);
}

Node dequeue(List *queue)
{
  Node poppedItem = queue->head-> data;
  ListRemoveAfter(queue, nullptr);
  return poppedItem;
}

void isEmpty(List *queue)
{

}
int main() {
  List *myQueue= new List;
  int data;
  char input;

  do
  {
    cout<<"\nCurrent Queue: ";
    ListPrint(myQueue);
    cout<<endl;
    cout<<"\nEnter Queue operation: ";
    cout<<"Enqueue(e), dequeue(d), quit(q): ";
    cin>>input;
    switch(input)
    {
      case 'e':
        cout<<"enter data to enqueue: ";
        cin>>data;
        enqueue(myQueue, new Node(data));
        break;

      case 'd':
        if(!isEmpty(myQueue)){
          Node* poppedItem = dequeue(myQueue);
          cout<<"Dequeued: "<<poppedItem->data;
          delete(poppedItem);
        }
        else
          cout<<"Queue Empty";
       break;

    }

  }while(input != 'q');
}

Answer 1

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

Однако код далек от good :

1. Во-первых, это не код C ++ , а C с некоторыми нотациями C ++ - здесь не используются классы, которые создают эти ListPrint и ListAppend, которые на 100% C функции.
2. Не соответствует API очереди (FIFO, то есть не удаляется после !).
3. Он подвержен утечкам памяти при использовании необработанных указателей (что является плохой практикой после C ++ 11).

Посмотрите на следующий код:

#include <stdint.h>
#include <memory>
#include <iostream>

template <typename T>
class Queue
{
public:
    T pop()
    {
        if (size > 0)
        {
            T ret_val = head->data;
            if (size == 1)
            {
                head = nullptr;
                tail = nullptr;
            }
            else
            {
                head = head->next;
            }

            --size;

            return ret_val; // here the previous head has no more references, thus deleted.
        }
        else
        {
            // some error handling.
        }
    }

    void push(T value)
    {
        std::shared_ptr<Node<T>> node = std::shared_ptr<Node<T>>(new Node<T>(value));

        if (size == 0)
        {
            head = node;
            tail = node;
        }
        else
        {
            tail->next = node;
            tail = node;
        }

        ++size;
    }

    void print() const
    {
        if (size == 0)
        {
            std::cout << "Empty Queue" << std::endl;
        }
        else
        {
            std::shared_ptr<Node<T>> node = head;

            std::cout << "Queue of size " << size << ": ";

            while (node != nullptr)
            {
                std::cout << node->data << ",";
                node = node->next;
            }

            std::cout << std::endl;
        }
    }

    bool isEmpty() const { return size == 0; }

private:
    template <typename S>
    struct Node
    {
        S data;
        std::shared_ptr<Node<S>> next;

        Node(S data) :
            data(data),
            next(nullptr)
        {
        }
    };

    std::shared_ptr<Node<T>> head = nullptr;
    std::shared_ptr<Node<T>> tail = nullptr;
    uint64_t size = 0;
};



int main()
{
    Queue<int> q;

    q.print();

    for (int i = 0; i < 10; ++i)
    {
        q.push(i);
        q.print();
    }

    for (uint64_t i = 0; i < 10; ++i)
    {
        std::cout << "Popped: " << q.pop() << std::endl;
        q.print();
    }
}

Его вывод :

Empty Queue
Queue of size 1: 0,
Queue of size 2: 0,1,
Queue of size 3: 0,1,2,
Queue of size 4: 0,1,2,3,
Queue of size 5: 0,1,2,3,4,
Queue of size 6: 0,1,2,3,4,5,
Queue of size 7: 0,1,2,3,4,5,6,
Queue of size 8: 0,1,2,3,4,5,6,7,
Queue of size 9: 0,1,2,3,4,5,6,7,8,
Queue of size 10: 0,1,2,3,4,5,6,7,8,9,
Queue of size 9: 1,2,3,4,5,6,7,8,9,
Queue of size 8: 2,3,4,5,6,7,8,9,
Queue of size 7: 3,4,5,6,7,8,9,
Queue of size 6: 4,5,6,7,8,9,
Queue of size 5: 5,6,7,8,9,
Queue of size 4: 6,7,8,9,
Queue of size 3: 7,8,9,
Queue of size 2: 8,9,
Queue of size 1: 9,
Empty Queue

Как и ожидалось.

В этом коде используются классы (чего-то, чего полностью не было в вашем коде!), Упрощенный алгоритм pop, интеллектуальные указатели для управления памятью, и он может содержать данные любого типа, не только целые числа!