What is the algorithm for inserting values into a queue in c plus plus?

Answer 1

A queue usually infers first in first out (FIFO), therefore new values will need to be inserted after the last node (the tail node) and the queue must maintain pointers to both the head node for extraction and the tail node for insertion, and each node must maintain a pointer to the next node in the queue (singly-linked list).

The following code provides a bare-bones implementation of a singly-linked FIFO list, where each value is an integer. In real-life you'd use one of the built-in class templates, otherwise you'd have to re-write the same code to cater for all the different value types you might want to place in a queue (or create your own class template). However, the example serves to show the algorithm that is used to insert new values to the end of a queue. It does not show how to extract the first node from the queue.

#include <iostream>

using namespace std;

class Node

{

public:

Node( int iValue ):m_iValue( iValue ),m_pNext( NULL ){}

~Node(){ if( m_pNext ) delete m_pNext; }

Node * GetNext()const{ return m_pNext; }

void SetNext(Node * pNext ){ m_pNext = pNext; }

int GetValue()const{ return m_iValue; }

private:

Node * m_pNext;

int m_iValue;

};

class Queue

{

public:

Queue():m_pFirst(NULL),m_pLast(NULL){}

~Queue(){ if( m_pFirst ) delete m_pFirst; }

Node * GetFirst()const{ return m_pFirst; }

Node * GetLast()const{ return m_pLast; }

void Insert( int iValue );

void ShowAll()const;

private:

Node * m_pFirst;

Node * m_pLast;

};

void Queue::Insert( int iValue )

{

Node * pNew = new Node( iValue );

if( m_pLast )

m_pLast->SetNext( pNew );

else

m_pFirst = pNew;

m_pLast = pNew;

}

void Queue::ShowAll() const

{

Node * pNode = m_pFirst;

while( pNode )

{

cout << pNode->GetValue();

if( pNode != m_pLast )

cout << ", ";

pNode = pNode->GetNext();

}

cout << endl << endl;

}

int main()

{

Queue queue;

queue.Insert( 2 );

queue.Insert( 1 );

queue.Insert( 3 );

queue.ShowAll();

return( 0 );

}