Queue (abstract data type)

Queues may be implemented as a separate data type, or maybe considered a special case of a double-ended queue (deque) and not implemented separately. For example, Perl and Ruby allow pushing and popping an array from both ends, so one can use push and shift functions to enqueue and dequeue a list (or, in reverse, one can use unshift and pop),[2] although in some cases these operations are not efficient.

C++'s Standard Template Library provides a "queue" templated class which is restricted to only push/pop operations. Since J2SE5.0, Java's library contains a Queue interface that specifies queue operations; implementing classes include LinkedList and (since J2SE 1.6) ArrayDeque. PHP has an SplQueue class and third party libraries like beanstalk'd and Gearman.

A simple queue implemented in JavaScript:

class Queue {
    constructor() {
        this.items = [];
    }

    enqueue(element) {
        this.items.push(element);
    }

    dequeue() {
        return this.items.shift();
    }
}

This queue's data is stored in two singly-linked lists named ${\displaystyle f}$ and ${\displaystyle r}$. The list ${\displaystyle f}$ holds the front part of the queue. The list ${\displaystyle r}$ holds the remaining elements (a.k.a., the rear of the queue) in reverse order. It is easy to insert into the front of the queue by adding a node at the head of ${\displaystyle f}$. And, if ${\displaystyle r}$ is not empty, it is easy to remove from the end of the queue by removing the node at the head of ${\displaystyle r}$. When ${\displaystyle r}$ is empty, the list ${\displaystyle f}$ is reversed and assigned to ${\displaystyle r}$ and then the head of ${\displaystyle r}$ is removed.

The insert ("enqueue") always takes ${\displaystyle O(1)}$ time. The removal ("dequeue") takes ${\displaystyle O(1)}$ when the list ${\displaystyle r}$ is not empty. When ${\displaystyle r}$ is empty, the reverse takes ${\displaystyle O(n)}$ where ${\displaystyle n}$ is the number of elements in ${\displaystyle f}$. But, we can say it is ${\displaystyle O(1)}$ amortized time, because every element in ${\displaystyle f}$ had to be inserted and we can assign a constant cost for each element in the reverse to when it was inserted.

The real-time queue achieves ${\displaystyle O(1)}$ time for all operations, without amortization. This discussion will be technical, so recall that, for ${\displaystyle l}$ a list, ${\displaystyle |l|}$ denotes its length, that NIL represents an empty list and ${\displaystyle \operatorname {CONS} (h,t)}$ represents the list whose head is h and whose tail is t.

The data structure used to implement our queues consists of three singly-linked lists ${\displaystyle (f,r,s)}$ where f is the front of the queue, r is the rear of the queue in reverse order. The invariant of the structure is that s is the rear of f without its ${\displaystyle |r|}$ first elements, that is ${\displaystyle |s|=|f|-|r|}$. The tail of the queue ${\displaystyle (\operatorname {CONS} (x,f),r,s)}$ is then almost ${\displaystyle (f,r,s)}$ and inserting an element x to ${\displaystyle (f,r,s)}$ is almost ${\displaystyle (f,\operatorname {CONS} (x,r),s)}$. It is said almost, because in both of those results, ${\displaystyle |s|=|f|-|r|+1}$. An auxiliary function ${\displaystyle aux}$ must then be called for the invariant to be satisfied. Two cases must be considered, depending on whether ${\displaystyle s}$ is the empty list, in which case ${\displaystyle |r|=|f|+1}$, or not. The formal definition is ${\displaystyle \operatorname {aux} (f,r,\operatorname {Cons} (\_,s))=(f,r,s)}$ and ${\displaystyle \operatorname {aux} (f,r,{\text{NIL}})=(f',{\text{NIL}},f')}$ where ${\displaystyle f'}$ is f followed by r reversed.

Let us call ${\displaystyle \operatorname {reverse} (f,r)}$ the function which returns f followed by r reversed. Let us furthermore assume that ${\displaystyle |r|=|f|+1}$, since it is the case when this function is called. More precisely, we define a lazy function ${\displaystyle \operatorname {rotate} (f,r,a)}$ which takes as input three list such that ${\displaystyle |r|=|f|+1}$, and return the concatenation of f, of r reversed and of a. Then ${\displaystyle \operatorname {reverse} (f,r)=\operatorname {rotate} (f,r,{\text{NIL}})}$. The inductive definition of rotate is ${\displaystyle \operatorname {rotate} ({\text{NIL}},\operatorname {Cons} (y,{\text{NIL}}),a)=\operatorname {Cons} (y,a)}$ and ${\displaystyle \operatorname {rotate} (\operatorname {CONS} (x,f),\operatorname {CONS} (y,r),a)=\operatorname {Cons} (x,\operatorname {rotate} (f,r,\operatorname {CONS} (y,a)))}$. Its running time is ${\displaystyle O(r)}$, but, since lazy evaluation is used, the computation is delayed until the results is forced by the computation.

The list s in the data structure has two purposes. This list serves as a counter for ${\displaystyle |f|-|r|}$, indeed, ${\displaystyle |f|=|r|}$ if and only if s is the empty list. This counter allows us to ensure that the rear is never longer than the front list. Furthermore, using s, which is a tail of f, forces the computation of a part of the (lazy) list f during each tail and insert operation. Therefore, when ${\displaystyle |f|=|r|}$, the list f is totally forced. If it was not the case, the internal representation of f could be some append of append of... of append, and forcing would not be a constant time operation anymore.

•  This article incorporates public domain material from Paul E. Black. "Bounded queue". Dictionary of Algorithms and Data Structures. NIST.