Google Interview Question
SDE-2sCountry: United States
public class CircularQueue<E> {
private E[] queue;
private int size;
private int head,tail;
public CircularQueue(int size){
this.head = 0;
this.tail = 0;
this.size = size;
this.initialize(size);
}
@SuppressWarnings("unchecked")
public void initialize(int size){
this.setQueue((E[]) new Object[size]);
this.head = 0;
this.tail = 0;
this.size = size;
}
public E[] getQueue() {
return queue;
}
public void setQueue(E[] queue) {
this.queue = queue;
}
public synchronized void enqueue(E e){
if(checkOverflow()){
System.out.println("Queue overflow");
return;
}
this.queue[this.tail] = e;
this.tail = (this.tail+1)%this.size;
}
public synchronized void dequeue(){
if(checkUnderflow()){
System.out.println("Queue underflow");
return;
}
this.queue[this.head] = null;
this.head = (this.head+1)%this.size;
}
private boolean checkOverflow(){
if(this.tail==this.head && this.queue[this.head]!=null){
return true;
}
return false;
}
private boolean checkUnderflow(){
if(this.tail==this.head && this.queue[this.head]==null){
return true;
}
return false;
}
}
public class CircularQueue {
int maxSize;
int[] array;
int head; // index of the head element
int tail; // index of the last added element
int size;
CircularQueue(int maxSize) {
array = new int[maxSize];
this.maxSize = maxSize;
head = 0;
tail = -1;
size = 0;
}
synchronized void push(int value) {
if (size == maxSize) {
throw new RuntimeException("Queue is full");
}
if (tail == array.length - 1) {
// wrap around case
tail = -1;
}
array[++tail] = value;
size++;
}
synchronized int pop() {
if (size == 0) {
throw new RuntimeException("Queue is empty");
}
int value = array[head++];
if (head == array.length) {
head = 0;
}
size--;
return value;
}
@Override
public String toString() {
if(size ==0 ) {
return "Queue is empty";
}
StringBuilder buf = new StringBuilder();
buf.append("Size: "+size+" Queue: ");
int i = head;
while(true) {
buf.append(array[i]+" ");
if( i == tail) {
break;
}
if(i == array.length -1) {
i =-1;
}
i++;
}
return buf.toString();
}
}
- ganni December 19, 2013