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.

About these ads

Pages: 1 2

14 Responses to “Deques”

  1. Adolfo said

    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))))
    
    (define (deque-add-front! d item)
      (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)))
    
    (define (deque-add-rear! d item)
      (cond ((deque-empty? d)
             (deque-add-front! d item))
            (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)))
    
  2. Adolfo said

    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
    
        def add_front(item)
            @a.unshift item
        end
    
        def add_back(item)
            @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.
         */
        this.addFirst = function(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.
         */
        this.addLast = function(element) {
            array.push(element);
        };
    
        /**
         * Return the internal array.
         */
        this.array = function() {
            return array;
        };
    };
    
  8. Adolfo said

    An implementation in Racket using doubly linked lists.

    #lang racket
    
    (require rackunit)
    
    (struct dlist (prev value next) #:mutable #:transparent)
    
    (define (dlist-add-before! dl value)
      (set-dlist-prev! dl (dlist #f value dl)))
    
    (define (dlist-add-after! dl value)
      (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)))
    
    (define (deque-add-front! dq item)
      (cond ((empty-deque? dq)
             (let ((dl (dlist #f item #f)))
               (set-deque-front! dq dl)
               (set-deque-back! dq dl)
               dq))
            (else
             (dlist-add-before! (deque-front dq) item)
             (set-deque-front! dq (dlist-prev (deque-front dq)))
             dq)))
    
    (define (deque-add-back! dq item)
      (cond ((empty-deque? dq)
             (deque-add-front! dq item))
            (else
             (dlist-add-after! (deque-back dq) item)
             (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)}))
    
    (defn dq-head [dq]
      (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 = []

    def add_front(self, i):
    self._data.insert(0, i)

    def add_back(self, 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 637 other followers

%d bloggers like this: