Dynamic Queue
As we discussed in previous example that a queue throws an exception if enough space is not available to accept an element to be pushed. To overcome this situation we can create dynamic queue whose capacity will keep increases as it reaches to max capacity.
Example
package com.w3schools;
public class Test {
private int capacity;
int queueArray[];
int front = 0;
int rear = -1;
int currentSize = 0;
public Test(int queueSize){
this.capacity = queueSize;
queueArray = new int[this.capacity];
}
/**
* Adds element at the end of the queue.
* @param item
*/
public void enqueue(int item) {
if (isQueueFull()) {
System.out.println("Overflow state. Increase capacity.");
increaseCapacity();
} else {
rear++;
if(rear == capacity-1){
rear = 0;
}
queueArray[rear] = item;
currentSize++;
System.out.println("Element " + item+ " is pushed to Queue.");
}
}
/**
* Removes an element from the top of the queue
*/
public void dequeue() {
if (isQueueEmpty()) {
System.out.println("Underflow state.");
} else {
front++;
if(front == capacity-1){
System.out.println("Removed element: "+queueArray[front-1]);
front = 0;
} else {
System.out.println("Removed element: "+queueArray[front-1]);
}
currentSize--;
}
}
/**
* Checks whether the queue is full or not
* @return boolean
*/
public boolean isQueueFull(){
boolean status = false;
if (currentSize == capacity){
status = true;
}
return status;
}
/**
* Checks whether the queue is empty or not
* @return
*/
public boolean isQueueEmpty(){
boolean status = false;
if (currentSize == 0){
status = true;
}
return status;
}
private void increaseCapacity(){
//Create new array with double size as the current one.
int newCapacity = this.queueArray.length*2;
int[] newArr = new int[newCapacity];
//Copy elements to new array
int tmpFront = front;
int index = -1;
while(true){
newArr[++index] = this.queueArray[tmpFront];
tmpFront++;
if(tmpFront == this.queueArray.length){
tmpFront = 0;
}
if(currentSize == index+1){
break;
}
}
//Convert new array as queue
this.queueArray = newArr;
System.out.println("New array capacity: "+this.queueArray.length);
//Reset front and rear values
this.front = 0;
this.rear = index;
}
public static void main(String args[]){
try {
Test queue = new Test(4);
queue.enqueue(41);
queue.dequeue();
queue.enqueue(6);
queue.enqueue(24);
queue.enqueue(7);
queue.enqueue(4);
queue.enqueue(45);
queue.dequeue();
} catch (Exception e) {
e.printStackTrace();
}
}
} |
package com.w3schools;
public class Test {
private int capacity;
int queueArray[];
int front = 0;
int rear = -1;
int currentSize = 0;
public Test(int queueSize){
this.capacity = queueSize;
queueArray = new int[this.capacity];
}
/**
* Adds element at the end of the queue.
* @param item
*/
public void enqueue(int item) {
if (isQueueFull()) {
System.out.println("Overflow state. Increase capacity.");
increaseCapacity();
} else {
rear++;
if(rear == capacity-1){
rear = 0;
}
queueArray[rear] = item;
currentSize++;
System.out.println("Element " + item+ " is pushed to Queue.");
}
}
/**
* Removes an element from the top of the queue
*/
public void dequeue() {
if (isQueueEmpty()) {
System.out.println("Underflow state.");
} else {
front++;
if(front == capacity-1){
System.out.println("Removed element: "+queueArray[front-1]);
front = 0;
} else {
System.out.println("Removed element: "+queueArray[front-1]);
}
currentSize--;
}
}
/**
* Checks whether the queue is full or not
* @return boolean
*/
public boolean isQueueFull(){
boolean status = false;
if (currentSize == capacity){
status = true;
}
return status;
}
/**
* Checks whether the queue is empty or not
* @return
*/
public boolean isQueueEmpty(){
boolean status = false;
if (currentSize == 0){
status = true;
}
return status;
}
private void increaseCapacity(){
//Create new array with double size as the current one.
int newCapacity = this.queueArray.length*2;
int[] newArr = new int[newCapacity];
//Copy elements to new array
int tmpFront = front;
int index = -1;
while(true){
newArr[++index] = this.queueArray[tmpFront];
tmpFront++;
if(tmpFront == this.queueArray.length){
tmpFront = 0;
}
if(currentSize == index+1){
break;
}
}
//Convert new array as queue
this.queueArray = newArr;
System.out.println("New array capacity: "+this.queueArray.length);
//Reset front and rear values
this.front = 0;
this.rear = index;
}
public static void main(String args[]){
try {
Test queue = new Test(4);
queue.enqueue(41);
queue.dequeue();
queue.enqueue(6);
queue.enqueue(24);
queue.enqueue(7);
queue.enqueue(4);
queue.enqueue(45);
queue.dequeue();
} catch (Exception e) {
e.printStackTrace();
}
}
}
Output
Adding element at front: 134
[134]
Adding element at front: 14
[14, 134]
Adding element at front: 13
[13, 14, 134]
Remove element from front: 13
[14, 134]
Adding element at rear: 455
[14, 134, 455]
Remove element from front: 14
[134, 455] |
Adding element at front: 134
[134]
Adding element at front: 14
[14, 134]
Adding element at front: 13
[13, 14, 134]
Remove element from front: 13
[14, 134]
Adding element at rear: 455
[14, 134, 455]
Remove element from front: 14
[134, 455]