2

一連のノード（値、次のノードへのポインター）としてキューを実装している場合、そのキューを横断して特定の値を確認し、その値を含むすべてのノードが次のようになるようにキューを編集するのが最善の方法です。削除されました。ただし、それ以外の場合、キューの順序は残ります。

これがすべての機能を説明するヘッダーです

class queue
{
  public:
    queue(); // constructor - constructs a new empty queue.
    void enqueue( int item ); // enqueues item.
    int dequeue();  // dequeues the front item.
    int front();   // returns the front item without dequeuing it.
    bool empty();  // true iff the queue contains no items.
    int size();  // the current number of items in the queue.
    int remove(int item); // removes all occurrances of item 
      // from the queue, returning the number removed.

  private:
    class node  // node type for the linked list 
    {
       public:
           node(int new_data, node * next_node ){
              data = new_data ;
              next = next_node ;
           }
           int data ;
           node * next ;
    };

    node* front_p ;
    node* back_p ;
    int current_size ; // current number of elements in the queue.
};

これがqueue.cppです

#include "queue.h"
#include <stdlib.h>
#include <iostream>
using namespace std;

queue::queue()
{
   front_p = NULL;
   back_p = NULL;
   current_size = 0;
}

void queue::enqueue(int item)
{
    node* newnode = new node(item, NULL);
   if (front_p == NULL) //queue is empty
        front_p = newnode;
    else
        back_p->next = newnode;
   back_p = newnode;
   current_size ++;
}

int queue::dequeue()
{
   //if there is only one node
    int value = front_p->data;
    if (front_p == back_p)
    {
        front_p = NULL;
        back_p = NULL;
    }
    //if there are two or more
    else
    {
        node* temp = front_p;
        front_p = temp->next;
        delete temp;
    }
    current_size --;
    return value;
}

int queue::front()
{
    if (front_p != NULL)
        return front_p->data;
}

bool queue::empty()
{
    if (front_p == NULL && back_p == NULL)
        return true;
    else
        return false;
}

int queue::size()
{
    return current_size;
}

int queue::remove(int item)
{
//?????
}
4

2 に答える 2

2

各ノードの値をチェックして、リストをトラバースする必要があります。シーケンス A -> B -> C (B は削除する値) が表示される場合は、リンクを A から B ではなく C を指すように変更する必要があります。

これを容易にするために、最後に見たノードと現在のノードへの参照を保持する必要があります。現在のノードの値が削除する値と等しい場合、最後のノードの次のポインターを現在のノードの次のポインターに変更します。続行する前に、必ず現在のノードのメモリを解放してください。

于 2012-10-26T06:20:58.290 に答える
0

キューが標準イテレータを公開している場合、最善の方法は標準アルゴリズムを使用することです。

queue.erase(std::remove(queue.begin(), queue.end(), value_to_remove), queue.end());
于 2012-10-26T06:21:26.743 に答える