Chapter 2: Basic Abstract Data Types. Problem 2.16.1

Implement a DeQueue (Double ended Queue) using an array.

//DEQUEUE is a type of QUEUE data structure where elements can be inserted/deleted at both ends.

#include <iostream>
using namespace std;

const int MAXLENGTH = 10; 
//Double ended Queue - implemented via an array 
class DEQUEUE
{
    int last; //points to the last element. -1 if queue is empty. 
    int list[MAXLENGTH]; 
public:
    DEQUEUE(); 
    bool IsQueueEmpty() { return last == -1 ? true : false; }  
    bool IsQueueFull() { return last+1 == MAXLENGTH ? true : false; }
    bool FrontInsert(int elem); 
    bool BackInsert(int elem); 
    bool FrontDelete(); 
    bool BackDelete(); 
    void Print(); 
}; 

DEQUEUE::DEQUEUE()
{
    last = -1; 
    memset(list, 0, sizeof(list)); 
}

bool DEQUEUE::FrontInsert(int elem)
{
    if( IsQueueFull() )
    {
        cout << "Queue is full." << endl;
        return false;
    }
    if( !IsQueueEmpty() )
    {
        //if the q is not empty, make space for this element by shifting 
        //every other element downwards.
        for( int n = last+1; n > 0; n-- )
            list[n] = list[n-1]; 
    }
    list[0] = elem; 
    last++; 
    return true; 
}

bool DEQUEUE::BackInsert(int elem)
{
    if( IsQueueFull() )
    {
        cout << "Queue is full." << endl;
        return false;
    }
    last++; 
    list[last] = elem; 
    return true;
}

bool DEQUEUE::FrontDelete()
{
    if( IsQueueEmpty() )
    {
        cout << "Queue is empty." << endl;
        return false;
    }
    if( last != 0 )
    {
        //if there are more than one elements in the list... 
        //move all elements one step upwards.
        for( int n = 0; n < last; n++ )
            list[n] = list[n+1]; 
    }
    last--; 
    return true;
}

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

void DEQUEUE::Print()
{
    cout << "DEQUEUE is --> " << endl << endl;
    if( IsQueueEmpty() )
    {
        cout << " EMPTY QUEUE " << endl;
    }
    else
    {
        cout << "Elements in Queue: [" << last+1 << "]" << endl;
        for( int n=0; n<last+1; n++ )
            cout << "[" << list[n] << "]"; 
        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(); 
}