25 Jan 2014

Circular Queue

Problem Statement :
           Implement Circular Queue Using Arrays

Source Code Link
Solution:

Circular Queue is efficient version of Queue, in which elements are stored efficiently without wastage of space.
The concept that circular queue uses is incrementation of the index pointer, which is achieved by
index = (index +1 )%N , this formula brings the index to start position if it crosses the end of the array.

We will be using two pointers namely "rear" and "front".
rear pointer - tracks the latest item inserted.
front pointer - tracks the oldest item in the queue.

Below is the name of the methods that Circular Queue will support as an ADT.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Queue Interface that ADT supports
 * @author Prateek
 * @param <T>
 */
public interface IQueue<T> {
 /**
  * Inserts an item to Queue, pointed by Rear.
  * @param item
  */
  void enqueue(T item);

  /**
   * @return oldest element in the queue, pointer by front pointer
   */
  T dequeue();
  
  boolean isEmpty();
  
  /*return size of Queue*/
  int size();
  
  boolean isFull();
}

Now given below is implementation of all the operations present in the interface.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/**
 * Circular Queue
 * @author Prateek....
 */
public class CircularQueue implements IQueue<Integer>{

 private static final int DEFAULT_CAPACITY = 5;
 private int N,front,rear;
 private int[] arr;

 public CircularQueue() {
  arr = new int[DEFAULT_CAPACITY];
  N=DEFAULT_CAPACITY;
  Arrays.fill(arr, -1);
  front = rear =0;
 }

 public CircularQueue(int capacity){
  arr = new int[capacity];
  N=DEFAULT_CAPACITY;
  Arrays.fill(arr, -1);
  front = rear =0;
 }

 @Override
 public void enqueue(Integer item) {
  if(isFull())
   System.err.println("Stack is Full");
  else {
   arr[rear] = item;
   rear = (rear +1 ) % N;
  }
 }

 @Override
 public Integer dequeue() {
  if(isEmpty()){
   System.err.println("Stack is Empty");
   return null;
  }
  else{
   int val=arr[front];
   arr[front] = -1;
   front = (front +1) % N ;
   return val;
  }
 }

 @Override
 public boolean isEmpty() {
  return (front == rear) ? true : false;
 }

 @Override
 public boolean isFull() {
  int diff = rear - front;
  return (diff == N-1 || diff == -1) ? true : false; 
 }

 @Override
 public int size() {
  return (rear > front) ? (rear-front) : (N - (front - rear));
 }
 
 /**
  * Displays the content of the Queue
  */
 public void display(){
  int size = size();
  int index = front;
  int count=0;
  
  while(count!=size){
   System.out.print(arr[index]+"\t");
       index = (index + 1) % N;
       count++;
  }
 }
}

Any improvement or suggestions for the above code are most welcome. Source Code is hosted on Ideone , please follow the link given above.
Happy Coding!! :)

3 comments:

  1. Yes! Finally someone writes about cane.

    my page: clash of clans hack

    ReplyDelete
  2. I will right away grab your rss fwed as I can't in finding your email subscription hyperlink or e-newsletter service.
    Do you've any? Kindly allow me recognize inn order thqt I may just subscribe.
    Thanks.

    Also visit my website - clash of clans hack

    ReplyDelete
  3. Very good information. Lucky mme I found your site by chance (stumbleupon).

    I've bookmarked it for later!

    My blog ... clash of clans cheats

    ReplyDelete