A deque is a data structure that can be used as both a queue and a stack. That is, there are two ends, the front and the back, and values can be pushed onto and popped off of both ends. These operations take O(1) amortized time and space in a normal usage pattern.

This vocabulary provides a deque implementation which is persistent and purely functional: old versions of deques are not modified by operations. Instead, each push and pop operation creates a new deque based off the old one.

The class of persistent deques:

deque

To create a deque:

<deque> ( -- deque )

sequence>deque ( sequence -- deque )

To test if a deque is empty:

deque-empty? ( deque -- ? )

To manipulate deques:

push-front ( deque item -- newdeque )

push-back ( deque item -- newdeque )

pop-front ( deque -- item newdeque )

pop-back ( deque -- item newdeque )

deque>sequence ( deque -- sequence )