Queue Data Structure
Kamaluddin“Behzad”
Bachelor in Computer Application
Queue data structure
A queue is a container of items (a linear collection) that are
inserted and removed according to the first-in first-out (FIFO)
principle.
An excellent example of a queue is a line of people at the ticket
counter. New additions to a line made to the rear end of the
queue, while removal happens in the front.
Stacks
Operations on a Queue
• Insert operation(also called enqueue)
To insert an item into the back of the queue.
• Delete operation(also called dequeue)
To remove the front item.
Stacks
Abnormal conditions on a Queue
• Queue full
A queue full occurs where you try to insert an element onto an
already full queue.
• Queue empty
A queue empty occurs where you try to delete an element from an
already empty
Stacks
Types of queue
There are four different types of queues:
1. Simple Queue
2. Circular Queue
3. Priority Queue
4. Double Ended Queue
Simple queue
In a simple queue, insertion takes place at the rear and removal occurs at
the front.
It strictly follows the FIFO (First in First out) rule.
Circular Linked list
In a circular queue, the last element points to the first element making a
circular link.
The main advantage of a circular queue over a simple queue is better
memory utilization. If the last position is full and the first position is
empty, we can insert an element in the first position. This action is not
possible in a simple queue.
Priority Queue
A priority queue is a special type of queue in which each element is
associated with a priority and is served according to its priority. If
elements with the same priority occur, they are served according to their
order in the queue.
Double Ended Queue
In a double ended queue, insertion and removal of elements can be
performed from either from the front or rear. Thus, it does not follow the
FIFO (First In First Out) rule.
Queue program used linked list
import java.util.Queue;
import java.util.LinkedList;
class Main {
public static void main(String[] args) {
Queue<Integer> numbers = new LinkedList<>();
numbers.offer(1);
numbers.offer(2);
System.out.println("Queue: " + numbers);
int removedNumber = numbers.poll();
System.out.println("Removed Element: " + removedNumber);
System.out.println("Queue after deletion: " + numbers); }}
Queue program
class Queue {
int SIZE = 5;
int items[] = new int[SIZE];
int front, rear;
Queue() {
front = -1;
rear = -1;
}
Types of queue
boolean isFull() {
if (front == 0 && rear == SIZE - 1) {
return true;
}
return false;
}
boolean isEmpty() {
if (front == -1)
return true;
else
return false; }
Types of queue
void enQueue(int element) {
if (isFull()) {
System.out.println("Queue is full");
} else {
if (front == -1) {
front = 0; }
rear++;
items[rear] = element;
System.out.println("Insert " + element);
}}
Types of queue
int deQueue() {
int element;
if (isEmpty()) {
System.out.println("Queue is empty");
return (-1); } else {
element = items[front];
if (front >= rear) {
front = -1; rear = -1;}
else { front++;}
System.out.println( element + " Deleted");
return (element);}}
Types of queue
void display() {
int i;
if (isEmpty()) {
System.out.println("Empty Queue");
}
else { System.out.println("\nFront index-> " + front);
System.out.println("Items -> ");
for (i = front; i <= rear; i++)
System.out.print(items[i] + " ");
System.out.println("\nRear index-> " + rear);
}}
Types of queue
public static void main(String[] args) {
Queue q = new Queue();
q.deQueue();
for(int i = 1; i < 6; i ++) {
q.enQueue(i);
}
q.enQueue(6);
q.display();
q.deQueue();
q.display();
}}
