Circular Queue

CIRCULAR-QUEUE

  What is a Circular Queue ?

 It is same like a queue with same FIFO operations .It is like the luggage belt on airport where the bags are there n the user picks the bag and the place becomes vacant .
Note:-Also always remember in queue's element is deleted from front and inserted at the end 

 

(Example of a conveyer belt at airport)

(Example of a circular queue)

ENQUEUE operation on the circular queue

In order to insert a element in a circular queue we need to check if the queue is full or not in order to do so we check if rear pointer has reached the DEFAULT_CAPACITY of our array and if front is at 0th element or front is at rear+1 position,we print "Queue is Full"

(front==0 && rear<DEFAULT_CAPACITY-1)
OR
front=rear+1

Now check if the rear is at the last element,if so set rear to first and insert

rear==0;

arr[rear]=data;

if not then we just insert an element in the array by

arr[++rear]=data

Also if in any case front =-1 i.e. initial state we need to set it to front=0 to get the front pointer at first position

DEQUEUE operation from the circular queue

In order to delete a element from a queue we need to check if the queue is empty or no.

In order to do so we check if our counters are at front=-1 and rear=-1 position that means initial position(Note:- here initial does not mean first element)so we print "Queue is Empty"

i.e.

front==-1 && rear==-1

If front and rear is at same position delete the element and make front go back one position as the element is deleted from front.

Now if front is at the last element point it to the first position after deletion i.e. front is set to 0 (front=0)

For normal scenario just delete the element and increase the front by 1

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 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114

/* * Circular queue using a array * @ Author Karan Deep Singh * */ public class CircularQueue { private static int DEFAULT_CAPACITY = 5; static int arr[]; static int front; static int rear; public CircularQueue() { arr = new int[DEFAULT_CAPACITY]; front = -1; rear = -1; } /* * Insertion :- * inserting an element - * 1. check if queue is full * 2. check if rear is at last element set rear to first and insert else just insert at position * 3. if front comes to be -1 reset it to 0 */ private void enqueue(int data) { if (isFull()) { System.out.println("queue is full"); return; } if (rear == DEFAULT_CAPACITY - 1) { rear = 0; arr[rear] = data; } else arr[++rear] = data; if (front == -1) front = 0; } /* * Deletion :- * 1. Check if queue is empty * 2. if front and rear are same position delete and make front go back one position as element is deleted from front * 3. if front is at last element point it to first position after deletion * 4. or just delete the element at given position and increment front * */ private void dequeue() throws Exception { if (isEmpty()) { System.out.println("queue is empty"); return; } if (front == rear) { System.out.println(arr[front]); front = rear = -1; } else if (front == DEFAULT_CAPACITY - 1) { System.out.println(arr[front]); front = 0; } else System.out.println(arr[front++]); } public static void main(String[] args) throws Exception { CircularQueue queue = new CircularQueue(); queue.enqueue(10); queue.enqueue(12); queue.enqueue(13); queue.enqueue(14); queue.enqueue(15); queue.dequeue(); queue.dequeue(); queue.enqueue(16); queue.enqueue(17); queue.enqueue(18); queue.dequeue(); queue.dequeue(); queue.dequeue(); queue.dequeue(); queue.dequeue(); queue.dequeue(); queue.enqueue(19); queue.enqueue(20); queue.enqueue(21); queue.dequeue(); queue.dequeue(); queue.dequeue(); queue.dequeue(); } // check if queue is empty i.e. front and rear pointers are back to initial // state -1 boolean isEmpty() { if (rear == -1 && front == -1) return true; return false; } // check if queue is full i.e. front came back to 0th element and rear is at // last element or front is equal to rear+1 boolean isFull() { if ((front == 0 && rear == DEFAULT_CAPACITY - 1) || front == rear + 1) return true; return false; } }

Queue

QUEUE

What is Queue ?

Whenever I am asked about a queue i am reminded of the boring queue that I use to stand in to pay my bills .And yes its same in programming languages too though here its not boring . If I am first standing in a Queue I would be the first one to pay my bill and get out of the line . This makes the queue a FIFO(First In First Out) operation,the first element added to queue would be the first one to be removed .

(Example of a Queue at a booth)

(FIFO operations done on a queue)

It is just so simple to understand always remember the general idea behind it and you could use in programming.
Now I would put some light on the FIFO operations in programming .
There are two types of operations that can be performed on a queue:-
1. Enqueue - Insertion/Pushing of element 
2. Dequeue - Deletion/Poping of element 

Considering a array the enqueue always done at end and dequeue from the front

I have taken two counters(front & rear) representing front of the queue and rear/end of the queue

ENQUEUE operation on the  queue(Insertion of new element)

In order to insert a element in a queue we need to check if the queue is full or not in order to do so we check if rear pointer has reached the INIT_CAPACITY of our array by

rear<INIT_CAPACITY-1

If condition is satisfied we insert an element in the array by

arr[++rear]=data

else we print "Queue is Full"

DEQUEUE operation from the  queue(Delete a element from queue)

In order to delete a element from a queue we need to check if the queue is empty or not because if we delete a element from a empty queue it would throw an exception that should be handled . 

In order to do so we check if our pointer has reached front=-1 or does the front pointer has a higher value than rear pointer 

i.e.

front==-1 || front>rear

If condition satisfies we handle the exception as queue is empty .

If not we remove the element from the queue by returning the element 

return arr[front++]

 

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

/* * Queue using an array * @ Author Karan Deep Singh * */ public class Queue { private static int INIT_CAPACITY = 5; int arr[]; int front; int rear; public Queue() { arr = new int[INIT_CAPACITY]; front = 0; rear = -1; } // Enqueue/Insert elements in queue by checking if queue is full or not private void enqueue(int data) { if(rear<INIT_CAPACITY-1) arr[++rear] = data; else System.out.println("Queue is Full"); } //Dequeue/Delete elements from queue by checking if queue is empty or not private int dequeue()throws Exception { if(front==-1 || front > rear) throw new Exception("Queue is Empty"); return arr[front++]; } public static void main(String[] args) throws Exception { Queue queue = new Queue(); queue.enqueue(10); queue.enqueue(12); queue.enqueue(13); queue.enqueue(14); queue.enqueue(15); queue.enqueue(16); queue.enqueue(17); queue.enqueue(18); System.out.println(queue.dequeue()); System.out.println(queue.dequeue()); System.out.println(queue.dequeue()); System.out.println(queue.dequeue()); System.out.println(queue.dequeue()); System.out.println(queue.dequeue()); } }

Stack

Stack

What is stack ? 

Lets talk about it in general terms to be most simple its nothing but a pile of objects e.g. pile of plates,boxes,towels,etc . So whenever you want to take out a box you need to pick the boxes above and then reach the your target desired box .

 

(Example of stack of boxes)

(Example of stack of plates)

Right its so simple you need something from a stack just pick the objects on top and you get to your target destination. 

Same goes for programming Languages we follow the same steps the IT jargon for its operations is LIFO(Last In Last Out) . We make a pile of objects and play with them in order to achieve the required object by our program .


Now I am gonna jump to a program that is gonna help you understand how stack operation is done in JAVA . 


Code Description:-

I have declared an array naming "arr"  and have maintained a counter name "top".

PUSH operation on a stack(Insertion of elements on stack):-

When trying to push or insert an element onto a stack i am going to insert a element at the end in order to do so I need to increase my counter by 1.
For e.g.:-

when top =0
     arr[++top] --> means arr[1] 
     so when an element is inserted it is at arr[1] position.

The increment is done first in order to take our new element at a vacant position for insertion .

Also while pushing/inserting an element on the stack we need to check if the stack is full or not, as it might throw an exception and we need to handle it.Doing it by following statement 

top < DEFAULT_CAPACITY-1  

POP operation on a stack(Deletion of elements on stack):-

When trying to pop or delete an element from a stack i am going to delete an element from  the end in order to do so I need to first decrease my counter by 1.
For e.g.:-

when top =10
     arr[top--] --> means element at arr[10]th position 
this is so because its a post increment operator and in next line the counter becomes 9 i.e. top becomes 9
so when an element is deleted it is deleted from arr[10] position.

The decrement is done latter in order to make the element available for GC(Garbage Collection)

Also while poping/deleting the elements from the stack we need to check if the stack is already empty,as it would again throw an exception when we try to remove an element from a empty stack . So if our counter turns to "-1" it means all the elements are removed and stack is empty .

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

/* * Stack using an Array * @ Author Karan Deep Singh * */ public class Stack { static int arr[]; public static int top=0; public static int DEFAULT_CAPACITY=5; Stack() { arr=new int[DEFAULT_CAPACITY]; top=-1; } // insert element on a stack, first increase the pointer then insert so that element is inserted on top of stack // check if stack is full or not private void push(int data) { if(top<DEFAULT_CAPACITY-1) { arr[++top]=data; }else System.out.println("Stack Overflow"); } //delete element from a stack, after delete then decrease the pointer so that element is removed from top of stack //check if stack is empty private int pop() throws Exception { if(top==-1) { throw new Exception("Stack is Empty"); } return arr[top--]; } // traverse or just view the element at a given position private int peek() { return arr[top]; } public static void main(String[] args) throws Exception { Stack stack=new Stack(); stack.push(10); stack.push(12); stack.push(13); stack.push(14); stack.push(15); stack.push(16); System.out.println(stack.pop()); System.out.println(stack.peek()); System.out.println(stack.peek()); System.out.println(stack.pop()); System.out.println(stack.peek()); System.out.println(stack.pop()); System.out.println(stack.pop()); System.out.println(stack.pop()); System.out.println(stack.pop()); } }