Mumbai University > Information Technology > Sem 3 > Data Structure and Algorithm analysis

Marks: 10 M

Year: Dec 2014

1. A double ended queue can be defined as a homogeneous list in which elements can be added or removed from both the ends i.e. element can be added or removed from both front and rear end.

2. It is also called as deque.

3. There are two variant of double ended queue depending upon the restriction to perform insertion or deletion operations at the two ends which are as follows:

i. Input restricted deque: An input restricted deque is a deque, which allows insertion at only 1 end, rear end, but allows deletion at both ends, rear and front end of the lists.

ii. Output restricted deque:An output-restricted deque is a deque, which allows deletion at only one end, front end, but allows insertion at both ends, rear and front ends, of the lists.

4. ADT for double ended queue:

i. insertFirst(e): insert e at the beginning of the deque

ii. insertLast(e): insert e at the end of the deque

iii. removeFirst(): remove and return the first element

iv. removeLast(): remove and return the last element

v. first(): return the first element

vi. last(): return the last element

vii. isEmpty(): return true if deque is empty; false otherwise

viii. size(): return the number of objects in the deque

5. Program:

Following program implements output restricted queue:

#include<iostream>
#include<conio.h>
using namespace std; 

#define MAX 50

class dequeue 
{ 

int a[MAX],front,rear,count; 

public: 
dequeue(); 
void add_at_beg(int); 
void add_at_end(int);
void display(); 
}; 


dequeue::dequeue() 
{ 
front=-1; 
rear=-1; 
} 


void dequeue::add_at_beg(int item) 
{
if ((front == 0 && rear == MAX-1) || (front==rear+1))
{
    cout<<"\nQueue Overflow";
    return;
}
if (front == -1)
{
    front = 0;
    rear = 0;
}
else if (left== 0)
    front = MAX-1;
else
    front = front-1;
    a[front] = item ;
} 



void dequeue::add_at_end(int item) 
{ 
if ((front == 0 && rear == MAX-1) || (front == rear+1))
{
    cout<<"\nQueue Overflow";
    return;
}
if(front==-1)
{
    front = 0;
    rear = 0;
}
else if(rear == MAX-1) 
    rear = 0;
else
    rear = rear+1;
    a[rear] = item;
} 



void dequeue::display() 
{
    int i;
if(front==-1 && rear==-1)
{
    cout<<"Queue is empty";
}
else
{
    cout<<"\nDequeue is:\n";
    for(i=front;i<=rear;i++)
    {
        cout<<a[i]<<"\n";
    }
}
}



void main()
{
      int ch;
      dequeue queue;
      while(1)
        {
              cout <<"\n1.Insert at beginning  2.Insert at end  3.Display  4.Exit\nEnter ur choice";
              cin >> ch;
              switch(ch)
              {
                  case 1:    cout <<"Enter the element you want to insert";
     cin >> ch;
             queue.add_at_beg(ch);
                             break;
                case 2:  cout <<"Enter the element you want to insert";
     cin >> ch;
             queue.add_at_end(ch);
                             break;
                    case 3:  queue.display();
                break;
                    case 4: exit(0);
              }
          }
}

Sample Output:

1.Insert at beginning  2.Insert at end  3.Display  4.Exit
Enter ur choice 3
Queue is empty
1.Insert at beginning  2.Insert at end  3.Display  4.Exit
Enter ur choice 1
Enter the element you want to insert 11

1.Insert at beginning  2.Insert at end  3.Display  4.Exit
Enter ur choice 2
Enter the element you want to insert 22

1.Insert at beginning  2.Insert at end  3.Display  4.Exit
Enter ur choice 3

Dequeue is:
11
22