Tags: #definition

k-queue sortable

Recall a queue (first in first out) data structure. A permutation is $k$-queue sortable if there is a way to sort it with $k$ queues.

Examples

• 1 3 4 2 is 2-queue sortable:
  • q1 push 1
  • q1 pop 1
  • q1 push 3
  • q1 push 4
  • q2 push 2
  • q2 pop 2
  • q1 pop 3
  • q1 pop 4

Properties

• A permutation is $(k-1)$-queue sortable if and only if it is $k,k-1,\dots ,1$-avoidant