Queue

Queue is also an abstract data type or a linear data structure, in which the first element is inserted from one end called REAR(also called tail), and the deletion of exisiting element takes place from the other end called as FRONT(also called head). This makes queue as FIFO data structure, which means that element inserted first will also be removed first.

The process to add an element into queue is called Enqueue and the process of removal of an element from queue is called Dequeue.

---

Basic features of Queue

1.      Like Stack, Queue is also an ordered list of elements of similar data types.

2.      Queue is a FIFO( First in First Out ) structure.

3.      Once a new element is inserted into the Queue, all the elements inserted before the new element in the queue must be removed, to remove the new element.

4.      peek( ) function is oftenly used to return the value of first element without dequeuing it.

---

Java program to create a Queue using Linked List:

import java.util.Iterator;

import java.util.NoSuchElementException;

/**

 * Generic Queue implementaion using linked list

 * @author Manoj

 */

public class Queue<Item> implements Iterable<Item> {

   private Node<Item> first;

   private Node<Item> last;

   private int n;

   private static class Node<Item> {

        private Item item;

        private Node<Item> next;

   }

   public Queue() {

        first = null;

        last = null;

        n = 0;

   }

   public boolean isEmpty() {

        return first == null;

   }

   public int size() {

       return n;

   }

   public Item peek() {

      if (isEmpty())

          throw new NoSuchElementException("Queue underflow");

          return first.item;

   }

   public void enqueue(Item item) {

          Node<Item> oldlast = last;

          last = new Node<Item>();

          last.item = item;

          last.next = null;

          if (isEmpty())

               first = last;

            else

               oldlast.next = last;

           n++;

   }

   public Item dequeue() {

       if (isEmpty())

           throw new NoSuchElementException("Queue underflow");

           Item item = first.item;

           first = first.next;

           n--;

       if (isEmpty())

           last = null; // to avoid loitering

           return item;

   }

   public String toString() {

        StringBuilder s = new StringBuilder();

        for (Item item : this) {

            s.append(item);

            s.append(' ');

        }

        return s.toString();

    }

    public Iterator<Item> iterator() {

       return new ListIterator<Item>(first);

   }

    private class ListIterator<Item> implements Iterator<Item> {

       private Node<Item> current;

       public ListIterator(Node<Item> first) {

             current = first;

       }

       public boolean hasNext() {

             return current != null;

       }

       public void remove() {

            throw new UnsupportedOperationException();

       }

       public Item next() {

            if (!hasNext())

              throw new NoSuchElementException();

              Item item = current.item;

              current = current.next;

              return item;

       }

       }

       public static void main(String[] args) {

           Queue<String> queue = new Queue<String>();

           queue.enqueue("M");

           queue.enqueue("A");

           queue.enqueue("N");

           System.out.println(queue);

      }

}

---

Reverse a Queue

package com.mk.ds.queue;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class ReverseQueue {

    static Queue<Integer> queue;
    static void Print() {
        while (!queue.isEmpty()) {
            System.out.print(queue.peek() + ", ");
            queue.remove();
        }
    }

    static void reverseQueue() {
        Stack<Integer> stack = new Stack<>();
        while (!queue.isEmpty()) {
            stack.add(queue.peek());
            queue.remove();
        }
        while (!stack.isEmpty()) {
            queue.add(stack.peek());
            stack.pop();
        }
    }

    public static void main(String args[]) {
        queue = new LinkedList<Integer>();
        for(int i =10 ; i < 100 ; i = i+10) {
            queue.add(i);
        }   // insert in seq 10, 20, 30, 40, 50, 60, 70, 80, 90
        reverseQueue();
        Print(); // reverse the inserted order
        // 90, 80, 70, 60, 50, 40, 30, 20, 10
    }
}

---

Interleave the first half of the queue with second half

Rearrange the elements by inserting the elements of second half of the queue in the first half of the queue in alternate position.

Example - 

Input:  1 2 3 4

Output: 1 3 2 4

Input: 10 20 30 40 50 60 70 80

Output: 10 50 20 60 30 70 40 80

package com.mk.ds.queue;

import java.util.*;
import java.util.Queue;

class InterLeaveQueue {

    public static void interLeaveQueue(Queue<Integer> q) {
        if (q.size() % 2 != 0)
            System.out.println("Input even number of integers.");

        Stack<Integer> s = new Stack<>();
        int halfSize = q.size() / 2;

        for (int i = 0; i < halfSize; i++) {
            s.push(q.peek());
            q.poll();
        }

        while (!s.empty()) {
            q.add(s.peek());
            s.pop();
        }

        for (int i = 0; i < halfSize; i++) {
            q.add(q.peek());
            q.poll();
        }

        for (int i = 0; i < halfSize; i++) {
            s.push(q.peek());
            q.poll();
        }

        while (!s.empty()) {
            q.add(s.peek());
            s.pop();
            q.add(q.peek());
            q.poll();
        }
    }

    public static void main(String[] args) {
        Queue<Integer> q = new LinkedList<Integer>();
        for(int i =10 ; i < 20 ; i++) {
            q.add(i);
        }

        interLeaveQueue(q);
        int length = q.size();
        for (int i = 0; i < length; i++) {
            System.out.print(q.peek() + " ");
            q.poll();
        }
    }
}