Chapter 2: Basic Abstract Data Types. Problem 2.16.2

Implement a DeQueue (Double ended Queue) using an linked list.

//DeQueue implemented via a linked list.
//no restrictions on the size of the queue since we are using a linked list.

#include <iostream>
using namespace std; 

struct NODE
{
    int nVal; 
    NODE* next;
}; 

class DEQUEUE
{
    NODE* front; 
    NODE* back; 
public:
    DEQUEUE() { front = back = NULL; } 
    bool IsQueueEmpty() { return ( front == NULL && back == NULL ) ? true : false; } 
    bool FrontInsert( int elem ); 
    bool BackInsert( int elem ); 
    bool FrontDelete(); 
    bool BackDelete(); 
    void Print(); 
}; 

bool DEQUEUE::FrontInsert( int elem )
{
    //allocate a new NODE. 
    NODE* newNode = new NODE; 
    newNode->nVal = elem; 
    newNode->next = front; 
    front = newNode; 
    if( !back )
    {
        //newNode is the first node. 
        //back also points to the same node. 
        back = front; 
    }
    return true;
}

bool DEQUEUE::BackInsert( int elem )
{
    //allocate a new NODE. 
    NODE* newNode = new NODE; 
    newNode->nVal = elem; 
    newNode->next = NULL; 
    if( IsQueueEmpty() )
    {
        //newNode is the first node.
        back = front = newNode;
    }
    else
    {
        back->next = newNode; 
        back = newNode;
    }
    return true;
}

bool DEQUEUE::FrontDelete()
{
    if( IsQueueEmpty() )
    {
        cout << "Queue is empty." << endl; 
        return false;
    }

    NODE* nodeDelete = front; 
    front = front->next; 
    delete nodeDelete; 

    if( !front )
    {
        //nodeDelete was the last node.
        back = NULL;
    }
    return true;
}

bool DEQUEUE::BackDelete()
{
    if( IsQueueEmpty() )
    {
        cout << "Queue is empty." << endl; 
        return false;
    }

    NODE* nodeDelete = back; 
    if( front == back )
    {
        //nodeDelete is the last node. 
        front = back = NULL; 
    }
    else
    {
        NODE* prevBack = front; 
        for( ; prevBack->next != back; prevBack = prevBack->next ); 
        back = prevBack; 
        back->next = NULL; 
    }
    delete nodeDelete; 
    return true;
}

void DEQUEUE::Print()
{
    cout << "DEQUEUE is --> " << endl << endl;
    if( IsQueueEmpty() )
    {
        cout << " EMPTY QUEUE " << endl;
    }
    else
    {
        NODE* curr = front; 
        for( ;curr != NULL; curr = curr->next ) 
            cout << "[" << curr->nVal << "]" ; 
        cout << endl;
    }
    cout << "<-- DEQUEUE END." << endl << endl;
}

//A little program that uses the queue
void main()
{
    DEQUEUE q; 
    q.Print(); 
    //front insert elements in the queue. 
    q.FrontInsert(1); 
    q.FrontInsert(2); 
    q.FrontInsert(3); 
    q.FrontInsert(4); 
    q.FrontInsert(5); 
    q.Print();
    //back insert elements in the queue. 
    q.BackInsert(6);
    q.BackInsert(7);
    q.BackInsert(8);
    q.BackInsert(9);
    q.BackInsert(10);
    q.Print(); 
    //Delete 2 elements from front.
    q.FrontDelete(); 
    q.FrontDelete(); 
    q.Print(); 
    //Delete 2 elements from back.
    q.BackDelete(); 
    q.BackDelete(); 
    q.Print(); 

    //Delete everything else. 
    q.BackDelete(); 
    q.BackDelete(); 
    q.BackDelete(); 
    q.Print(); 
    q.FrontDelete(); 
    q.FrontDelete(); 
    q.FrontDelete(); 
    q.Print(); 
}