A Queue is a linear abstract data type which operates in a FIFO (first in first out) order. Because it is an abstract data type, it can be implemented under the hood with arrays, linked-list or other concrete data structures. Linked lists are a common choice because in (most) linked list implementations the necessary operations are O(1) (constant time).