Queue

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.Examine the item least recently added.

Application:

1. recursion
2. Backtracking
3. Expression evaluation and syntax parsing
   1. Reverse Polish notation
   2. calculation
4. Efficient Algorithm
5. Runtime memory management

Typical Questions：

1. Implement Stack using Queues (keep one queue only have one element)

Complexity：

The time complexity of push and _pop _operations should be O(1)

Implementation:

pop(), push(), isEmpty(), peek()

public class QueueOfStrings {
    void enqueue(String item)
    String dequeue()
    boolean isEmpty()
    int size()
}

Linked List:

public class LinkedQueueOfStrings {

     private Node first, last;

     private class Node {  
     /* same as in StackOfStrings */  
     }

     public boolean isEmpty() {
         return first == null;
     }
     public void enqueue(String item) {
         Node oldlast = last;
         last = new Node();
         last.item = item;
         last.next = null;
         if (isEmpty()) first = last;
         else oldlast.next = last;
     }

     public String dequeue() {
         String item = first.item;
         first = first.next;
         if (isEmpty()) last = null;
         return item;
     }
 }