public class Queue<T> implements Iterable<T> {
private LinkedList<T> list = new LinkedList<>();
/**
* Peek the element from without removing the front of the queue
*
* @return element
*/
public T peek() {
if (isEmpty()) {
throw new RuntimeException("Queue Empty");
}
return list.peek();
}
/**
* Poll an element and remove it from the front of the queue
*
* @return element
*/
public T poll() {
if (isEmpty()) {
throw new RuntimeException("Queue Empty");
}
return list.poll();
}
/**
* Add an element to the back of the queue
*
* @param element element to be added
*/
public void offer(T element) {
list.addLast(element);
}
public int size() {
return list.size();
}
public boolean isEmpty() {
return size() == 0;
}
@Override
public Iterator<T> iterator() {
return list.iterator();
}
}
public class IntQueue {
private int[] arr;
private int size;
private int front, end;
public IntQueue(int maxSize) {
this.size = maxSize + 1;
arr = new int[size];
}
/**
* Add an element to the queue
*
* @param value to add
*/
public void enqueue(int value) {
arr[end++] = value;
if (end == size) {
end = 0;
}
if (end == front) {
throw new RuntimeException("Queue is too small.");
}
}
/**
* Poll an element from the front
*
* @return element
*/
public int dequeue() {
if (isEmpty()) {
throw new RuntimeException("Queue is empty");
}
var value = arr[front++];
if (front == size) {
front = 0;
}
return value;
}
public int peek() {
return arr[front];
}
public boolean isEmpty() {
return front == end;
}
/**
* Return the number of elements inside the queue
*
* @return size of the queue
*/
public int size() {
if (front > end) {
return end + size - front;
}
return end - front;
}
}
Given a fixed size array, any of the elements could be considered as a head in a queue. As long as we know the length of the queue, we then can instantly locate its tail, based on the following formula:
<aside>
📌 tailIndex = (headIndex + count − 1) mod capacity
</aside>
where the variable capacity is the size of the array, the count is the length of the queue and the headIndex and tailIndex are the indice of head and tail elements respectively in the array. Here we showcase a few examples how a circular queue could reside in a fixed size array.
/*
poll, peek <-> deque, enque, Front, Rear
*/
class MyCircularQueue {
private int[] queue;
//size of the array
private int capacity;
//indice of head elements in the array
private int headIndex;
// length of the queue
private int count;
/** Initialize your data structure here. Set the size of the queue to be k. */
public MyCircularQueue(int k) {
this.queue = new int[k];
this.capacity = k;
}
/** Insert an element into the circular queue. Return true if the operation is successful. */
public boolean enQueue(int value) {
if (isFull()) return false;
queue[(headIndex + count) % capacity] = value;
count++;
return true;
}
/** Delete an element from the circular queue. Return true if the operation is successful. */
public boolean deQueue() {
if (isEmpty()) return false;
headIndex = (headIndex + 1) % capacity;
count--;
return true;
}
/** Get the front item from the queue. */
public int Front() {
if (isEmpty()) return -1;
return queue[headIndex];
}
/** Get the last item from the queue. */
public int Rear() {
if (isEmpty()) return -1;
return queue[tailIndex()];
}
/** Checks whether the circular queue is empty or not. */
public boolean isEmpty() {
return count == 0;
}
/** Checks whether the circular queue is full or not. */
public boolean isFull() {
return count == capacity;
}
private int tailIndex() {
return (headIndex + count - 1) % capacity;
}
}
O(1). All of the methods in our circular data structure is of constant time complexity.O(N). The overall space complexity of the data structure is linear, where N is the pre-assigned capacity of the queue. However, it is worth mentioning that the memory consumption of the data structure remains as its pre-assigned capacity during its entire life cycle.Similar with Array, the Linked List is another common building block for more advanced data structures.
Different than a fixed size Array, a linked list could be more memory efficient, since it does not pre-allocate memory for unused capacity.
With a singly-linked list, we could design a circular queue with the same time and space complexity as the approach with Array. But we could gain some memory efficiency, since we don't need to pre-allocate the memory upfront.
