Technical Interview

Home
Added Recently
Data Structures
Puzzles
Google & Microsoft
C/C++ Questions
Java Interview Questions
Quantitative Problems
Algorithms
Featured Articles
Amazon Interview Question
Compaq Interview Question
Technical Interview
Interview Process
Introduction Questions
Object Oriented
Google Pages
Fundamental Questions
Resume Tips
Links
Contact Us
Submit Question/Answer



Implement a Queue using an Array




Problem: Implement a queue using an Array. Make efficient use of the space in the array.

Solution: Queue is a data structure that supports Enqueue and Dequeue methods. The Enqueue method adds an item to the end of the list and Dequeue method removes an item from the beginning of the list. This means that the Queue is a FIFO (First In First Out) data structure. Theoretically speaking a Queue doesn't have a fixed size. It grows as items are added to the end of the list. The implementation below has a fixed sized determined at the time of instantiating the Queue object. Ideally, the array should be reallocated to accommodate more items. The implementations makes use of the space efficiently by reusing space that is released when items are dequeued.

/************ Queue.h *********************/
// Queue class implements the Queue ADT(abstract data type) or Abstract Data Structure
// using an array as the underlying data structure
class Queue
{
private:
int *itemsArray; // array used for storing items in the queue
int startIndex; // index in the array where the queue starts
int size; // size of the array holding the queue
int count; // number of items in queue

public:
Queue(int size);
~Queue();
void Enqueue(int i);
int Dequeue();
int GetCount();
void Print();
};
/************ Queue.cpp *********************/
#include "stdafx.h"
#include "malloc.h"
#include "Queue.h"

Queue::Queue(int size)
{
this->size = size;
itemsArray = (int *)malloc(sizeof(int) * size);
startIndex = 0;
count = 0;
}



Queue::~Queue()
{
free(itemsArray);
}

// Enqueue method adds an item to the end of the queue
void Queue::Enqueue(int i)
{
if(count < size) // queue is not full
{
int destinationIndex = (startIndex + count) % size;
itemsArray[destinationIndex] = i;
count++;
}
else
{
printf("Queue is full...\n");
}
}

// Dequeue method removes an item from the front of the queue
int Queue::Dequeue()
{
if(count == 0)
{
printf("queue is empty!\n");
throw "queue is empty";
}
int ret = itemsArray[startIndex];
count--;
startIndex = (startIndex + 1)%size;
return ret;
}

int Queue::GetCount()
{
return count;
}

// Print the current contents of the queue
void Queue::Print()
{
printf("Queue contents: ");

for(int i = 0; i<count;i++)
{
printf("%d, ", itemsArray[(startIndex + i)%size]);
}
printf("\n");
}