Amazon Interview Question
Software Engineer / DevelopersHi,
Actually the insertToLeft() operation should behave as a FIFO queue on the left side. so whatever was inserted first on the left should be removed when removeFromLeft() is called. i guess ur doubly linked list implementation removes the head node(which was last inserted) on calling removeFromLeft(). Please correct me if i am wrong.
#include <stdio.h>
- Anonymous April 28, 2011#include <iostream>
/*
Implement various operations of a double ended queue (Deque).
Deque is a data structure where items can be inserted and removed from both ends.
Operations :- insertToLeft(), removeFromLeft(), insertToRight(),removeFromRight().
*/
using namespace std;
class dequeu;
struct node
{
int data;
struct node *next;
struct node *prev;
friend class dequeue;
};
typedef struct node* Node;
class dequeue
{
Node head;
Node tail;
Node createNode(int data);
public:
dequeue():head(NULL),tail(NULL){}
~dequeue()
{
Node cur = head;
Node temp = NULL;
while(cur)
{
temp = cur;
cur=cur->next;
delete temp;
temp =NULL;
}
head = tail = NULL;
}
void insertToLeft(int data);
void insertToRight(int data);
int removeFromLeft();
int removeFromRight();
void print();
};
Node dequeue::createNode(int data)
{
Node temp = new struct node;
temp->data = data;
temp->prev = NULL;
temp->next = NULL;
}
void dequeue::insertToLeft(int data)
{
Node temp = createNode(data);
if(head == NULL)
{
head= tail = temp;
}
else
{
temp->next = head;
head->prev = temp;
head = temp;
}
}
void dequeue::insertToRight(int data)
{
Node temp = createNode(data);
if(head == NULL)
{
head = tail = temp;
}
else
{
tail->next = temp;
temp->prev = tail;
tail = temp;
}
}
int dequeue::removeFromLeft()
{
if(head == NULL)
{
cout<<"Empty dequeue";
return -1;
}
else
{
Node temp = head;
if(head == tail)
{
head = tail = NULL;
}
else
{
head=head->next;
head->prev= NULL;
}
delete temp;
temp = NULL;
}
return 1;
}
int dequeue::removeFromRight()
{
if(tail == NULL)
{
cout<<"dqueue Empty ";
return -1;
}
else
{
Node temp = tail;
if(head == tail)
{
head = tail = NULL;
}
else
{
tail = tail->prev;
tail->next = NULL;
}
delete temp;
temp = NULL;
}
return 1;
}
void dequeue::print()
{
Node cur = head;
while(cur)
{
cout<<" "<<cur->data;
cur = cur->next;
}
}
int main()
{
dequeue q;
q.removeFromRight();
q.removeFromLeft();
int i;
for(i=1;i<5;i++)
q.insertToLeft(i);
for(i=8;i<13;i++)
q.insertToRight(i);
q.print();
system("PAUSE");
return EXIT_SUCCESS;
}