Skip to content

Queues

Quote

“It is better to have 100 functions operate on one data structure than to have 10 functions operate on 10 data structures.” — Alan Perlis

Operation PriorityQueue LinkedList ArrayDequeue ConcurrentLinkedQueue ArrayBlockingQueue PriorityBlockingQueue SynchronousQueue DelayQueue LinkedBlockingQueue
Offer \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {O(log(n))}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {O(log(n))}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {O(log(n))}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\)
Peek \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\)
Poll \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {O(log(n))}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {O(log(n))}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {O(log(n))}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\)
Remove \(\color{black} \fcolorbox{gold}{yellow} {O(n)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{black} \fcolorbox{gold}{yellow} {O(n)}\) \(\color{black} \fcolorbox{gold}{yellow} {O(n)}\) \(\color{black} \fcolorbox{gold}{yellow} {O(n)}\) \(\color{black} \fcolorbox{gold}{yellow} {O(n)}\) \(\color{black} \fcolorbox{gold}{yellow} {O(n)}\) \(\color{black} \fcolorbox{gold}{yellow} {O(n)}\) \(\color{black} \fcolorbox{gold}{yellow} {O(n)}\)
Size \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{black} \fcolorbox{gold}{yellow} {O(n)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\)
Operation collections.deque
Copy \(\color{black} \fcolorbox{gold}{yellow} {Θ(n)}\) → \(\color{black} \fcolorbox{gold}{yellow} {O(n)}\)
Append \(\color{white} \fcolorbox{limegreen}{forestgreen} {Θ(1)}\) → \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\)
Append left \(\color{white} \fcolorbox{limegreen}{forestgreen} {Θ(1)}\) → \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\)
Pop \(\color{white} \fcolorbox{limegreen}{forestgreen} {Θ(1)}\) → \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\)
Pop left \(\color{white} \fcolorbox{limegreen}{forestgreen} {Θ(1)}\) → \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\)
Extend \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {Θ(k)}\) → \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {O(k)}\)
Extend left \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {Θ(k)}\) → \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {O(k)}\)
Rotate \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {Θ(k)}\) → \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {O(k)}\)
Remove \(\color{black} \fcolorbox{gold}{yellow} {Θ(n)}\) → \(\color{black} \fcolorbox{gold}{yellow} {O(n)}\)
Get length \(\color{white} \fcolorbox{limegreen}{forestgreen} {Θ(1)}\) → \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\)

Queues are a type of data structure that follow the FIFO (First In First Out) principle.

Queue<Integer> queue = []
queue << 1
queue << 2
queue << 3

Queue<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);
queue.add(3);

val queue = LinkedList<Int>()
queue += 1
queue += 2
queue += 3

from collections import deque

queue = deque(1, 2, 3)

block-beta
  columns 2
  block:indices
    columns 1
    top("top") space:2 bottom("bottom")
  end
  block:nums
    columns 1
    v1["3"] v2["6"] v3["5"] v4["8"]
  end

  top --> v1
  bottom --> v4

style indices fill:transparent

Which one to use?

  • Use LinkedList when the insertion order matters.
  • Use PriorityQueue when the natural order matters.