Following is the DeQueue Source Code

#include <iostream.h>

//QUEUE
template <class Item>
class QUEUE
{
 private:
        struct node
        {
                     Item item; node *next; node *p;
                     node(Item x)
                    {
                  item=x; next=0; p=0;
                      }
            };

            typedef node *link;
            link head, tail;

 void deletelist()
{
            for(link t=head;t!=0;head=t)
           {
              t=head->next;
             delete head;
           }
  }

 public:
            QUEUE()
            {
              head=0; tail=0;       
             }
  
 QUEUE(const QUEUE& rhs)
  { head=0; *this=rhs;}
 
~QUEUE()  //destructor
 {
  deletelist();
 }
 QUEUE& operator=(const QUEUE& rhs)
  {
  if(this==&rhs)
 return *this;
 deletelist();
            link t=rhs.head;
 while(t!=0)
 {
             inject(t->item);
  t=t->next;
  }
 return *this;
        }

        int empty() const                        // to check if queue is empty or not
        {
         return head==0;
        }

        void inject(Item x)                     // to enter character at the back of the queue
        {
         link t=tail;
          tail=new node(x);
          if(head==0)
             head=tail;
         else
   { t->next=tail; tail->p=t;}
        }

        Item eject()                       // to get character from the back of the queue
        {
   Item v=tail->item;
            link t=head;
            while(t->next!=tail)
            {
     t=t->next;
            }
            delete tail;
            tail=t;
            tail->next=NULL;
            return v;

        }
 

  void push(Item x)                 // to enter character at the front of the queue
  {
   link t = new node(x);
   if(head == 0)
   {head = t; tail =t;}
   else
   {
    head->p = t;
    t->next = head;
    head = t;
   }
  }

  Item pop()                // to get character from the front of the queue
  {
   Item v = head->item; link t = head->next;
   if(head == tail)
   { head = 0; tail = 0;}
   else
   { t->p = 0; delete head; head = t;}
   return v;
  }

};

void display(QUEUE<char> Q)        // to view the current queue without changing it
{
 QUEUE<char> Que;
 Que = Q;
 cout<<"Displaying the current queue:     ";
 while(!Que.empty())
 {
  cout<<Que.pop();
 }
}

int main()
{
 QUEUE<char> Q;
 char x;
 cout<<"Please enter the characters in the queue."<<endl;
 while(cin.peek()!='\n')
 {
  cin>>x;
  Q.inject(x);

 }
 display(Q);

 cout<<endl<<"Enter a character to push in the queue:  ";
 cin>>x;
 Q.push(x);
 display(Q);

 cout<<endl<<"Now ejecting a character from the queue."<<endl;
 Q.eject();
 display(Q);

 cout<<endl<<"Enter a character to inject in the queue:  ";
 cin>>x;
 Q.inject(x);
 display(Q);

 cout<<endl<<"Now poping a character from queue"<<endl;
 Q.pop();
 display(Q);

 cout<<endl;

 return 0;
}