Queue Basic Concepts and Implementation

A Queue is a fundamental data structure that stores and manipulates data based on the First In First Out (FIFO) principle. A queue can be viewed as a linear container where insertion operations (enqueue) are performed at one end, and deletion operations (dequeue) are performed at the other end. The enqueue operation adds elements to the tail of the queue, while the dequeue operation removes elements from the head of the queue.

The basic operations of a queue include Enqueue and Dequeue. A queue can also perform operations such as viewing the front element (Front) and determining whether the queue is empty (IsEmpty).

Applications of Queues are extremely widespread, such as in task scheduling, Breadth-First Search (BFS), and caching. In task scheduling, tasks are placed into a queue and scheduled according to the FIFO principle; in Breadth-First Search, each node is first added to the queue and then traversed in FIFO order; in caching, cached data is replaced based on the FIFO principle.

Queues can be implemented using an array or a linked list. If an array is used to implement a queue, a certain amount of memory space must be allocated in advance, and when the queue is full, larger space needs to be reallocated. If a linked list is used to implement a queue, nodes can be dynamically added or removed without needing to allocate memory space in advance.

The time complexity of queue operations is typically O(1), as all operations are performed at the head or tail of the queue and do not require traversing the entire queue. However, if an array is used to implement a queue, reallocating larger space when the queue is full incurs additional overhead.

Queue Implementation

::: code-tabs
@tab Java

public class Queue<V> {
    private int maxSize;
    private V[] array;
    private int front;
    private int back;
    private int currentSize;
    
    @SuppressWarnings("unchecked")
    public Queue(int maxSize) {
        this.maxSize = maxSize;
        array = (V[]) new Object[maxSize];
        front = 0;
        back = -1;
        currentSize = 0;
    }
    
    public int getMaxSize() {
        return maxSize;
    }
    
    public int getCurrentSize() {
        return currentSize;
    }
    
    public V top() {
        return array[front];
    }
    
    public boolean isEmpty() {
        return currentSize == 0;
    }
    
    public boolean isFull() {
        return currentSize == maxSize;
    }
    
    public void enqueue(V value) {
        if (isFull()) {
            return;
        }
        back = (back + 1) % maxSize; 
        array[back] = value;
        currentSize++;
    }
    
    public V dequeue() {
        if (isEmpty()) {
            return null;
        }
        V temp = array[front];
        front = (front + 1) % maxSize; 
        currentSize--;
        return temp;
    }
}

:::