| Operation | T.C. | Operation | T.C. |
|---|---|---|---|
| Enqueue | O(1) | Contains | O(n) |
| Dequeue | O(1) | Removal | O(n) |
| Peeking | O(1) | IsEmpty | O(1) |
java.util.LinkedList to implement queue.Queue interface.Integer with 0. public interface Queue<T> {
public void offer(T elem);
public T poll();
public T peak();
public int size();
public boolean isEmpty();
}
public class LinkedListQueue<T> implements Queue<T> {
private final LinkedList<T> data;
private int size;
public LinkedListQueue() {
data = new LinkedList<>();
size = 0;
}
public LinkedListQueue(T elem) {
data = new LinkedList<>();
offer(elem);
}
@Override
public void offer(T elem) {
data.addFirst(elem);
size++;
}
@Override
public T poll() {
T elem = data.getLast();
data.removeLast();
size--;
return elem;
}
@Override
public T peak() {
return data.getLast();
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public String toString() {
return data.toString();
}
}
Integer with 0. public class ArrayQueue<T> implements Queue<T> {
private final T[] arr;
private int front;
private int rear;
// Initial capacity is 8
private static int initialCapacity = 1 << 3;
public ArrayQueue() {
this(initialCapacity);
}
@SuppressWarnings("unchecked")
public ArrayQueue(int capacity) {
initialCapacity = capacity;
arr = (T[]) new Object[initialCapacity];
front = rear = 0;
}
@Override
public void offer(T elem) {
if (isFull()) {
throw new RuntimeException("Queue is full.");
}
arr[rear++] = elem;
rear = adjustIndex(rear, arr.length);
}
@Override
public T poll() {
if (isEmpty()) {
throw new RuntimeException("Queue is empty.");
}
front = adjustIndex(front, arr.length);
return arr[front++];
}
@Override
public T peak() {
if (isEmpty()) {
throw new RuntimeException("Queue is empty.");
}
front = adjustIndex(front, arr.length);
return arr[front];
}
@Override
public int size() {
return adjustIndex(rear + arr.length - front, arr.length);
}
@Override
public boolean isEmpty() {
return front == rear;
}
/**
* Return current index if it's less than array length, else return (index - length).
*
* @param index index
* @param length array length
* @return effective Index
*/
private int adjustIndex(int index, int length) {
return index >= length ? index - length : index;
}
/**
* Checks if Queue is full.
*/
private boolean isFull() {
return (front + arr.length - rear) % arr.length == 1;
}
@Override
public String toString() {
return ... ;
}
}
//Let Q be a Queue
Q.enqueue(starting_node)
starting_node.visited = true
while Q is not empty Do
node = Q.dequeue()
// do business with node data
for neighbour in neighbours(node):
if neighour is not visited:
neighbour.visited = true
Q.enqueue(neighbour)
/**
* Traverse all the connected nodes starting from given node in the graph.
*
* @param adjacecyList
* @param sourceNode
*/
private static void breadFirstSearch(List<List<Integer>> adjacecyList, int sourceNode) {
final boolean[] visitTracker = new boolean[adjacecyList.size()];
final Queue<Integer> queue = new LinkedList<>();
// mark source as visited
visitTracker[sourceNode] = true;
// add current node in queue
queue.add(sourceNode);
while (!queue.isEmpty()) {
// get the Node (int) from the queue
Integer t = queue.poll();
System.out.println("Node : " + t);
for (int node : adjacecyList.get(t)) {
if(!visitTracker[node]) {
System.out.println(" Processing node : " + node);
visitTracker[node] = true;
System.out.println(" Visited: " + node);
queue.add(node);
} else {
System.out.println(" Skipping visited node : " + node);
}
}
System.out.println("Queue : " + queue.toString());
}
}
/**
* Add the edge link in the list.
*
* @param adjacecyList
* @param u
* @param v
*/
private static void addEdge(List<List<Integer>> adjacecyList, int u, int v) {
adjacecyList.get(u).add(v);
// Undirected graph
adjacecyList.get(v).add(u);
}