↞↞Previous ↞Stack Data Structure

What is Queue?

You must have seen people line up in a bank to be served by a teller or at a Train ticket counter to get the ticket. This is always a fair practice which we follow in our real life. Queues maintain first-in, first-out order (FIFO). The FIFO property of a queue makes it similar like a line of customers waiting to get the tickets. We use Queue when order of retrieval should be the same as the order of insertion. Queues are often described in terms of producers and consumers. A producer is anything that stores data in a queue, while a consumer is anything that retrieves data from a queue.
Operations on a queue:

• Enqueue(x): Insert item x at the back of queue.
• Dequeue(): Return (and remove) the front item from queue.
• peek(): Return the front item of queue.
• Full(): Test whether the more items can be enqueued to the Queue.
• Empty(): Test whether the more items can be dequeued from the Queue.

Implementation of Queue Data Structure:

1. Implement using simple array. (bounded)
2. Implement using linked list. (unbounded)

Queues are little more difficult to implement than stacks, because action happens at both ends. Queue maintain indices to the first (front) and last (rear) elements in the array. We always enqueue an element at the rear of the queue, just as a newly arriving customer takes a place at the end of the line. The element dequeued is always the one at the front of the queue, like the customer at the head of the line who has waited the longest.

When you insert a new item in the queue in the Queue, the Front arrow moves upward, toward higher numbers in the array. When you remove an item, Rear also moves upward. The problem with this arrangement is that pretty soon the rear of the queue is at the end of the array. Even if there are empty cells at the beginning of the array, because you have removed them with dequeue, you still can’t insert a new item because Rear can’t go any further.

To avoid the problem of not being able to insert more items into the queue even when it’s not full, the Front and Rear arrows wrap around to the beginning of the array. The result is a circular queue.

Queue implementation in Java using Array

public class Queue {

	private int maxSize;
	private int queueArray[];
	private int front;
	private int rear;
	private int nItems;

	public Queue(int size) {
		maxSize = size;
		queueArray = new int[size];
		front = 0;
		rear = -1;
		nItems = 0;
	}

	public void enqueue(int value) {
		if(isFull()){
			System.err.println("Error: queue is full...");
			return;
		}
		if (rear == maxSize - 1) {
			rear = -1;
		}
		queueArray[++rear] = value;
		++nItems;
	}

	public int dequeue() {
		if(isEmpty()){
			System.err.println("Error: queue is empty...");
			return -1;
		}
		int temp = queueArray[front++];
		if (front == maxSize ) {
			front = 0;
		}
		nItems--;
		return temp;
	}
	
	public int peek(){
		return queueArray[front];
	}
	
	public boolean isEmpty(){
		return nItems==0;
	}
	
	public boolean isFull(){
		return nItems == maxSize;
	}
	public int size(){
                return nItems;
        }
	public static void main(String[] args) {
		Queue queue = new Queue(5);
		queue.enqueue(10);
		queue.enqueue(20);
		queue.enqueue(30);
		queue.enqueue(40);
		queue.enqueue(50);
		
		queue.dequeue();
		queue.dequeue();
		
		queue.enqueue(110);
		queue.enqueue(120);
		
		while(!queue.isEmpty()){
			System.out.print(queue.dequeue()+" ");
		}
	}
}
Output
----------
30 40 50 110 120 

Queue implementation in Java using Linked List

Create a Node class which will hold value and link to the next element.

public class Node {

	private int value;
	private Node next;
	
	public Node(int value) {
		this.value = value;
	}

	public int getValue() {
		return value;
	}

	public void setValue(int value) {
		this.value = value;
	}

	public Node getNext() {
		return next;
	}

	public void setNext(Node next) {
		this.next = next;
	}
}

Create the Queue with all the methods.

public class Queue {
	private Node front;
	private Node rear;
        private int nItems;

	public Queue() {
		front = null;
		rear = null;
	}

	public boolean isEmpty() {
		return front == null;
	}

	public void enqueue(int value) {
		Node newNode = new Node(value);
		if (isEmpty()) {
			front = newNode;
		} else {
			rear.setNext(newNode);
		}
		rear = newNode;
                nItems++;
	}
	
	public int dequeue(){
		int val = front.getValue();
		if(front == rear){
			front = null;
			rear = null;
		}else{
			front= front.getNext();
		}
                nItems--;
		return val;
	}
	
	public void displayList(){
		Node current = front;
		while(current != null){
			System.out.print(current.getValue()+" ");
			current = current.getNext();
		}
		System.out.println();
	}
	
        public int size(){
              nItems;
        }
	public static void main(String[] args) {
		Queue queue = new Queue();
		queue.enqueue(10);
		queue.enqueue(20);
		queue.enqueue(30);
		queue.enqueue(40);
		queue.enqueue(50);
		
		queue.dequeue();
		queue.dequeue();
		
		queue.enqueue(110);
		queue.enqueue(120);
		
		queue.displayList();
	}
}

Output
---------
30 40 50 110 120 

References:

• Introduction To Algorithm – CLRS.
• Algorithm Design Manual – Skiena
• Data Structure & Algorithms In Java – Robert Lafore