## Deques

### September 6, 2011

A normal linked list can be accessed only at its head. A double-ended queue, or deque (pronounced “deck”), can be accessed at either end. Like a normal list, a deque can be null. New elements can be added at either end, the element at either end of a non-null deque can be fetched, and the element at either end of a non-null deque can be deleted. Deques are a combination of stacks and queues.

Your task is to write a function library that implements deques; you should be sure that all operations are performed in constant time. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 14 Responses to “Deques”

In Racket:

```#lang racket

(require rackunit)
(require racket/mpair)

(struct deque (front rear) #:mutable #:transparent)

(define (empty-deque)
(deque '() '()))

(define (deque-empty? d)
(and (null? (deque-front d))
(null? (deque-rear d))))

(cond ((deque-empty? d)
(let ((x (mlist item)))
(set-deque-front! d x)
(set-deque-rear! d x)
d))
(else
(set-deque-front! d (mcons item (deque-front d)))
d)))

(cond ((deque-empty? d)
(else
(let ((last-node (deque-rear d)))
(set-mcdr! last-node (mcons item (mcdr last-node)))
(when (not (eq? last-node (deque-front d)))
(set-deque-rear! d (mcdr last-node)))
d))))

(define (deque-first d)
(mcar (deque-front d)))

(define (deque-last d)
(let ((rear (deque-rear d)))
(if (null? (mcdr rear))
(mcar rear)
(mcdr rear))))

(define (deque-delete-first! d)
(set-deque-front! d (mcdr (deque-front d)))
(when (null? (deque-front d))
(set-deque-rear! d '()))
d)

(define (deque-delete-last! d)
(cond ((null? (mcdr (deque-front d)))
(set-deque-front! d '())
(set-deque-rear! d '())
d)
(else
(set-mcdr! (deque-rear d) '())
d)))
```

Sometimes I wish I could delete my comments: my implementation doesn’t work at all (but soon I’ll be back :-) )

3. slabounty said

A ruby version …

```class Deque
def initialize
@a = []
end

@a.unshift item
end

@a << item
end

def get_front
@a.first
end

def get_back
@a.last
end

def remove_front
@a.shift
end

def remove_back
@a.pop
end

end
```

It cheats a bit by using the ruby array and its assorted functions … but easy.

4. fengshaun said

I’m practically just using normal haskell functions, wrapping them in a nice coat of Deque-ness! Kind of cheating, I know!

```data Deque a = Deque { deque :: [a] }
deriving (Show)

beg :: Deque a -> a
beg d = head . deque \$ d

end :: Deque a -> a
end d = last . deque \$ d

delBeg :: Deque a -> Deque a
delBeg d = Deque \$ tail . deque \$ d

delEnd :: Deque a -> Deque a
delEnd d = Deque \$ init . deque \$ d
```
5. fengshaun said

And of course I forgot the ‘add’ functions:

```addBeg :: a -> Deque a -> Deque a
addBeg i d = Deque \$ ((:) i) . deque \$ d

addEnd :: a -> Deque a -> Deque a
addEnd i d = Deque \$ (flip (++) \$ [i]) . deque \$ d
```
6. Axio said
```;; The "two stacks" implementation of dequeues
;; The code looks duplicated, but macros would make it harder to understandâ€¦
(define-structure dequeue s1 s2)

(define dq (make-dequeue '() '()))

(define (dequeue-push! d v)
(dequeue-s1-set! d (cons v (dequeue-s1 d))))

(define (dequeue-enqueue! d v)
(dequeue-s2-set! d (cons v (dequeue-s2 d))))

(define (dequeue-pop! d)
(let ((s1 (dequeue-s1 d))
(s2 (dequeue-s2 d)))
(if (null? s1)
(if (null? s2)
(error "empty queue")
(let ((tmp (reverse s2)))
(dequeue-s1-set! d (cdr tmp))
(dequeue-s2-set! d '())
(car tmp)))
(let ((tmp (car s1)))
(dequeue-s1-set! d (cdr s1))
tmp))))

(define (dequeue-dequeue! d)
(let ((s1 (dequeue-s1 d))
(s2 (dequeue-s2 d)))
(if (null? s2)
(if (null? s1)
(error "empty queue")
(let ((tmp (reverse s1)))
(dequeue-s2-set! d (cdr tmp))
(dequeue-s1-set! d '())
(car tmp)))
(let ((tmp (car s2)))
(dequeue-s2-set! d (cdr s2))
tmp))))

(define (test)
(dequeue-push! dq 3) ;;
(dequeue-push! dq 2) ;; 2 3
(dequeue-push! dq 1) ;; 1 2 3
(= 3 (dequeue-dequeue! dq)) ;; 1 2
(= 1 (dequeue-pop! dq)) ;; 2
(dequeue-enqueue! dq 3) ;; 2 3
(dequeue-enqueue! dq 4) ;; 2 3 4
(dequeue-enqueue! dq 5) ;; 2 3 4 5
(= 2 (dequeue-pop! dq)) ;; 3 4 5
(= 3 (dequeue-pop! dq)) ;; 4 5
(= 4 (dequeue-pop! dq)) ;; 5
(= 5 (dequeue-dequeue! dq))) ;; 0
```
7. JavaScript & NodeJS:

``````
/**
* Function library that implements deques; you should be sure that all
* operations are performed in constant time.
*
* @see http://programmingpraxis.com/2011/09/06/deques/
* @author rmariuzzo
*/
var Deque = function() {

// Internal array.
var array = [];

/**
* Return the first element.
*/
this.getFirst = function() {
return array[0];
};

/**
* Return the last element.
*/
this.getLast = function() {
return array[array.length-1];
};

/**
* Remove the first element.
*/
this.removeFirst = function() {
array = array.slice(1);
};

/**
* Remove the last element.
*/
this.removeLast = function() {
array.pop();
};

/**
* Add an element as the first element.
*/
var t = array;
array = [element];
for (var i = 0; i < t.length; i++) {
array.push(t[i]);
}
};

/**
* Add an element as the last element.
*/
array.push(element);
};

/**
* Return the internal array.
*/
this.array = function() {
return array;
};
};
``````

An implementation in Racket using doubly linked lists.

```#lang racket

(require rackunit)

(struct dlist (prev value next) #:mutable #:transparent)

(set-dlist-prev! dl (dlist #f value dl)))

(set-dlist-next! dl (dlist dl value #f)))

(struct deque (front back) #:mutable #:transparent)

(define (empty-deque? dq)
(null? (deque-front dq)))

(define (deque-first dq)
(dlist-value (deque-front dq)))

(define (deque-last dq)
(dlist-value (deque-back dq)))

(cond ((empty-deque? dq)
(let ((dl (dlist #f item #f)))
(set-deque-front! dq dl)
(set-deque-back! dq dl)
dq))
(else
(set-deque-front! dq (dlist-prev (deque-front dq)))
dq)))

(cond ((empty-deque? dq)
(else
(set-deque-back! dq (dlist-next (deque-back dq)))
dq)))

(define (deque-pop-front! dq)
(let ((dl (deque-front dq)))
(set-deque-front! dq (dlist-next dl))
(unless (deque-front dq)
(set-deque-back! dq #f))
dq))

(define (deque-pop-back! dq)
(let ((dl (deque-back dq)))
(set-deque-back! dq (dlist-prev dl))
(set-dlist-next! (dlist-prev dl) #f)
(unless (deque-back dq)
(set-deque-front! dq #f))
dq))

(define (list->deque lst)
(let* ((fst (dlist #f (car lst) #f))
(dq (deque fst fst)))
(for-each (Î» (x) (deque-add-back! dq x))
(cdr lst))
dq))

(define (deque->list dq)
(let loop ((dl (deque-front dq)))
(if dl
(cons (dlist-value dl)
(loop (dlist-next dl)))
'())))

(test-case
"Deque tests."

(check-equal? (deque->list (list->deque '(1 2 3 4 5)))
'(1 2 3 4 5))

(check-equal? (deque->list (deque-add-front! (list->deque '(1 2 3)) 'a))
'(a 1 2 3))

(check-equal? (deque->list (deque-add-back! (list->deque '(1 2 3)) 'b))
'(1 2 3 b))

(check-equal? (deque->list (deque-pop-front! (list->deque '(1 2 3))))
'(2 3))

(check-equal? (deque->list (deque-pop-back! (list->deque '(1 2 3))))
'(1 2)))
```
9. Axio said

With better amortisation: splitting a list in two when it is empty and accessed.

```(define-structure dequeue s1 s2 size1 size2)

(define dq (make-dequeue '() '() 0 0))

(define (dequeue-push! d v)
(dequeue-s1-set! d (cons v (dequeue-s1 d)))
(dequeue-size1-set! d (1+ (dequeue-size1 d))))

(define (dequeue-enqueue! d v)
(dequeue-s2-set! d (cons v (dequeue-s2 d)))
(dequeue-size2-set! d (1+ (dequeue-size2 d))))

;; assume the size is good
(define (split-at* pos l t)
(let loop ((pos pos) (front '()) (rear l))
(if (zero? pos)
(values (if t front (reverse front)) (reverse rear))
(loop (1- pos) (cons (car rear) front) (cdr rear)))))

(define (dequeue-pop! d)
(let ((s1 (dequeue-s1 d))
(s2 (dequeue-s2 d))
(size1 (dequeue-size1 d))
(size2 (dequeue-size2 d)))
(if (zero? size1)
(if (zero? size2)
(error "empty queue")
(let ((mid (ceiling (/ size2 2))))
(call-with-values
(lambda ()
(split-at* mid s2 #f))
(lambda (front rear)
(dequeue-s1-set! d (cdr rear) )
(dequeue-s2-set! d front)
(dequeue-size1-set! d (1- mid))
(dequeue-size2-set! d (- size2 mid))
(car rear)))))
(let ((tmp (car s1)))
(dequeue-s1-set! d (cdr s1))
(dequeue-size1-set! d (1- (dequeue-size1 d)))
tmp))))

(define (dequeue-dequeue! d)
(let ((s1 (dequeue-s1 d))
(s2 (dequeue-s2 d))
(size1 (dequeue-size1 d))
(size2 (dequeue-size2 d)))
(if (zero? size2)
(if (zero? size1)
(error "empty queue")
(let ((mid (floor (/ size1 2))))
(call-with-values
(lambda ()
(split-at* mid s1 #t))
(lambda (front rear)
(dequeue-s1-set! d (reverse front))
(dequeue-s2-set! d (reverse (cdr rear)))
(dequeue-size2-set! d (- size1 mid 1))
(dequeue-size1-set! d mid)
(car rear)))))
(let ((tmp (car s2)))
(dequeue-s2-set! d (cdr s2))
(dequeue-size2-set! d (1- (dequeue-size2 d)))
tmp))))
```
10. ijp said

I put a purely functional version up on github the other day https://github.com/ijp/pfds/blob/master/deques.sls

11. kawas said

Clojure: immutable, all operations in constant time thanks to clojure vector’s properties

```(defn deque-empty [] {:dqf [] :dqb []})

(defn dq-cons [e dq]
(let [{fq :dqf bq :dqb} dq] {:dqf (conj fq e), :dqb bq}))

(defn dq-snoc [e dq]
(let [{fq :dqf bq :dqb} dq] {:dqf fq, :dqb (conj bq e)}))

(let [{fq :dqf bq :dqb} dq]
(cond
(seq fq) (peek fq)
(seq bq) (nth bq 0)
:else    (throw (Exception. "empty deque")))))

(defn dq-last [dq]
(let [{fq :dqf bq :dqb} dq]
(cond
(seq bq) (peek bq)
(seq fq) (nth fq 0)
:else    (throw (Exception. "empty deque")))))

(defn dq-tail [dq]
(let [{fq :dqf bq :dqb} dq]
(cond
(seq fq) {:dqf (pop fq), :dqb bq}
(seq bq) {:dqf fq, :dqb (subvec bq 1)}
:else    dq)))

(defn dq-init [dq]
(let [{fq :dqf bq :dqb} dq]
(cond
(seq bq) {:dqf fq, :dqb (pop bq)}
(seq fq) {:dqf (subvec fq 1), :dqb bq}
:else    dq)))
```
12. Phil said

A Python implementation. Keep in mind that I’m a new Python programmer, so this should not be considered an optimal implementation :)

class deque:
def __init__(self):
self._data = []

self._data.insert(0, i)

self._data.append(i)

def remove_front(self):
return self._data.pop(0)

def remove_back(self):
return self._data.pop()

def front(self):
return self._data[0]

def back(self):
return self._data[-1]

def is_empty(self):
return len(self._data) == 0

def __str__(self):
return self._data.__str__()

13. Phil said

I can’t edit my post, so it would be nice if the previous post could be deleted. Here’s one that’s correctly formatted on pastbin.

source