CODEWITHSUNDEEP
c++linked-listqueuenodes
E.Cross
E.Cross

Reputation: 2137

Remove all item from queue c++

If I have a queue implemented as a series of nodes (value, pointer to next node), what would be the best way to transverse that queue and check for a specific value, and edit the queue such that all nodes containing that value would be removed. But the order of the queue would otherwise remain.

Ok here is the header describing all the functions

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.
};

and here is the 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)
{
//?????
}

Upvotes: 2

Views: 4391

Answers (2)

Mankarse
Mankarse

Reputation: 40613

If your queue exposes standard iterators, the best way would be to use a standard algorithm:

queue.erase(std::remove(queue.begin(), queue.end(), value_to_remove), queue.end());

Upvotes: 0

Jordan Lewis
Jordan Lewis

Reputation: 17928

You need to traverse the list, checking the values of each node. If you see a sequence A -> B -> C, where B is the value that you want to remove, you need to change the link from A to point to C instead of B.

To facilitate this, you'll need to keep a reference to the last node you saw as well as the current one. If the current node's value is equal to the one to remove, change the last node's next pointer to the current node's next pointer. Make sure to free the current node's memory before continuing on.

Upvotes: 2

Related Questions