Microsoft Interview Question
Software Engineer in TestsArray is enough with head, and tail position indexes (initially or when empty both be -1), the notion of circular is that the queue start and end positions could be anywhere in the array. Then basic operations are implemented as:
- enQueue: if queue is not full, add the element to tail = (tail + 1) % QUEUE_ARRAY_SIZE
- deQueue: if not empty, take element at head, and head = (head + 1) % QUEUE_ARRAY_SIZE
Note: For the case of full, you might need to re-size your array to a bigger size.
For the first time at enQueue you might need to point head to what tail points to.
In deQueue if no more element in queue set head and tail to -1
actually circular queue can be implemented as the array or as well as linked list also
array --for circular queue implementation
struct queue
{
int item[10000];
int front;
int rear;}q;
q.front=999;
q.rear=999;
so the queue is initialised as empty and both the front and rear are pointing towards the last index of the array
and as the q.front==q.rear means the queue is empty
otherwise the dequee operation can be done by incrementing the front if front!=999
if front =999 then by dequee operation we can get the front as 0
and in the enquee operation
just always increment he (q.rear)++=item one exception is also in case of enqueue operation that is if rear is 999
then just do this
q.rear=item;
q.rear=0;
public class CircularQueue {
public static final int MAX_SIZE = 3;
public static int counter = 0;
private static int [] a = new int[MAX_SIZE];
private static int front = 0;
private static int rear = 0;
public void insert(int d){
if(counter == MAX_SIZE){
System.out.println("queue is full. Cant insert "+ d);
return;
}
a[rear] = d;
rear++;
if(rear>=MAX_SIZE){
rear = rear%MAX_SIZE;
}
counter++;
}
public int remove(){
if(counter ==0){
System.out.println("queue empty");
return -1;
}
int d = a[front];
front++;
if(front >= MAX_SIZE){
front = front % MAX_SIZE;
}
counter--;
return d;
}
public static void main(String [] args){
CircularQueue q = new CircularQueue();
q.insert(1);
q.insert(2);
q.insert(3);
q.insert(4);
System.out.println("data from queue: "+q.remove());
System.out.println("data from queue: "+q.remove());
System.out.println("data from queue: "+q.remove());
System.out.println("data from queue: "+q.remove());
}
}
public class CircularQueue {
public static final int MAX_SIZE = 3;
public static int counter = 0;
private static int [] a = new int[MAX_SIZE];
private static int front = 0;
private static int rear = 0;
public void insert(int d){
if(counter == MAX_SIZE){
System.out.println("queue is full. Cant insert "+ d);
return;
}
a[rear] = d;
rear++;
if(rear>=MAX_SIZE){
rear = rear%MAX_SIZE;
}
counter++;
}
public int remove(){
if(counter ==0){
System.out.println("queue empty");
return -1;
}
int d = a[front];
front++;
if(front >= MAX_SIZE){
front = front % MAX_SIZE;
}
counter--;
return d;
}
public static void main(String [] args){
CircularQueue q = new CircularQueue();
q.insert(1);
q.insert(2);
q.insert(3);
q.insert(4);
System.out.println("data from queue: "+q.remove());
System.out.println("data from queue: "+q.remove());
System.out.println("data from queue: "+q.remove());
System.out.println("data from queue: "+q.remove());
}
}
What is a circular queue?
- Anonymous August 05, 2010