[go: up one dir, main page]
Scribd
Upload
5 views4 pages

Queue

queue explained

Uploaded by

Anukampa Behera
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
5 views4 pages

Queue

queue explained

Uploaded by

Anukampa Behera
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

Queue

A Queue is a linear structure which follows a particular order in which the operations are performed.
The order is First In First Out (FIFO).

Operations on Queue:
Mainly the following four basic operations are performed on queue:

Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition.
Dequeue: Removes an item from the queue. The items are popped in the same order in which they
are pushed. If the queue is empty, then it is said to be an Underflow condition.
Front: Get the front item from queue.
Rear: Get the last item from queue.

Applications of Queue:
Queue is used when things don’t have to be processed immediately, but have to be processed
in First In First Out order like Breadth First Search. This property of Queue makes it also useful in
following kind of scenarios.

1) When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk
Scheduling.
2) When data is transferred asynchronously (data not necessarily received at same rate as sent)
between two processes. Examples include IO Buffers, pipes, file IO, etc.

Array implementation Of Queue


For implementing queue, we need to keep track of two indices, front and rear. We enqueue an item
at the rear and dequeue an item from front. If we simply increment front and rear indices, then
there may be problems, front may reach end of the array.

// A class to represent a queue


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 item)
{
if (isFull(this))
return;
this.rear = (this.rear + 1)%this.capacity;
this.array[this.rear] = item;
this.size = this.size + 1;
System.out.println(item+ " enqueued to 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 queue = new Queue(1000);
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.enqueue(40);
System.out.println(queue.dequeue() + " dequeued from queue\n");
System.out.println("Front item is " + queue.front());
System.out.println("Rear item is " + queue.rear());
}
}
Linked list implementation
// A linked list (LL) node to store a queue entry
class QNode {
int key;
QNode next;
// constructor to create a new linked list node
public QNode(int key)
{
this.key = key;
this.next = null;
}}
// A class to represent a queue
// The queue, front stores the front node of LL and rear stores the
// last node of LL
class Queue {
QNode front, rear;
public Queue()
{
this.front = this.rear = null;
}
// Method to add an key to the queue.
void enqueue(int key)
{
// Create a new LL node
QNode temp = new QNode(key);
// If queue is empty, then new node is front and rear both
if (this.rear == null) {
this.front = this.rear = temp;
return;
}
// Add the new node at the end of queue and change rear
this.rear.next = temp;
this.rear = temp;
}
// Method to remove an key from queue.
QNode dequeue()
{
// If queue is empty, return NULL.
if (this.front == null)
return null;

// Store previous front and move front one node ahead


QNode temp = this.front;
this.front = this.front.next;

// If front becomes NULL, then change rear also as NULL


if (this.front == null)
this.rear = null;
return temp;
}
}
public class Test {
public static void main(String[] args)
{
Queue q = new Queue();
q.enqueue(10);
q.enqueue(20);
q.dequeue();
q.dequeue();
q.enqueue(30);
q.enqueue(40);
q.enqueue(50);

System.out.println("Dequeued item is " + q.dequeue().key);


}
}

You might also like