What is Queue in Data Structure ?

    • A queue is a container of objects (a linear collection) that are inserted and removed according to the first-in first-out (FIFO) principle.
Queue(FIFO)
  • Here the first element is inserted from one end called REAR and deleted from the other end called as FRONT.
  • Front points to the beginning of the queue and Rear points to the end of the queue.
Enqueue Dequeue

Operations on Queue

Operation Description
enqueue() This function defines the operation for adding an element into queue.
dequeue() This function defines the operation for removing an element from queue.
init() This function is used for initializing the queue.
Front Front is used to get the front data item from a queue.
Rear Rear is used to get the last item from a queue.

Queue Implementation

 Queue in Data Structure
  • Array is the easiest way to implement a queue. Queue can be also implemented using Linked List or Stack.
  • Front and Rear of the queue point at the first index of the array. (Array index starts from 0).
  • While adding an element into the queue, the Rear keeps on moving ahead and always points to the position where the next element will be inserted. Front remains at the first index.

Sample Code

import java.io.*;
class Queue
{
int front, rear, size;
int capacity;
int array[];

public Queue(int capacity) {
this.capacity = capacity;
front = this.size = 0;
rear = capacity - 1;
array = new int[this.capacity];

}

// Queue is full when size becomes equal to
// the capacity
boolean isFull(Queue queue)
{ return (queue.size == queue.capacity);
}

// Queue is empty when size is 0
boolean isEmpty(Queue queue)
{ return (queue.size == 0); }

// Method to add an item to the queue.
// It changes rear and size
void enqueue( int items)
{
if (isFull(this))
return;
this.rear = (this.rear + 1)%this.capacity;
this.array[this.rear] = items;
this.size = this.size + 1;
System.out.println(items+ " enqueued to the queue");
}

// Method to remove an item from queue.
// It changes front and size
int dequeue()
{
if (isEmpty(this))
return Integer.MIN_VALUE;

int item = this.array[this.front];
this.front = (this.front + 1)%this.capacity;
this.size = this.size - 1;
return item;
}

// Method to get front of queue
int front()
{
if (isEmpty(this))
return Integer.MIN_VALUE;

return this.array[this.front];
}

// Method to get rear of queue
int rear()
{
if (isEmpty(this))
return Integer.MIN_VALUE;

return this.array[this.rear];
}
}


// Driver class
public class Test
{
public static void main(String[] args)
{
Queue q1 = new Queue(1000);

q1.enqueue(7);
q1.enqueue(8);
q1.enqueue(18);
q1.enqueue(25);

System.out.println(q1.dequeue() +
" dequeued from the queue\n");

System.out.println("Front item is " +
q1.front());

System.out.println("Rear item is " +
q1.rear());
}
}

Output

7 enqueued to the queue
8 enqueued to the queue
18 enqueued to the queue
12 enqueued to the queue
7 dequeued from the queue

Front item is 8
Rear item is 25

Categorized in:

Tagged in:

, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,