Queues

November 1, 2013

One of the basic data structures in computer science is the queue, in which items are inserted into the data structure and retrieved in the order in which they were inserted; the standard operations on a queue are enqueue, dequeue, and isEmpty.

Your task is to write functions to implement a queue. 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

5 Responses to “Queues”

  1. Implementation in SML.

    signature QUEUE = sig
        type 'a queue
    
        exception EmptyQ
    
        val empty: 'a queue
        val enqueue: 'a queue -> 'a -> 'a queue
        val dequeue: 'a queue -> 'a * 'a queue
        val isEmpty: 'a queue -> bool
    end
    
    structure ListQueue :> QUEUE = struct
        type 'a queue = 'a list * 'a list
    
        exception EmptyQ
    
        val empty = ([], [])
    
        fun enqueue (xs, ys) x = (x::xs, ys)
    
        fun dequeue ([], [])    = raise EmptyQ
          | dequeue (xs, [])    = dequeue ([], rev f)
          | dequeue (xs, y::ys) = (y, (xs, ys))
    
        fun isEmpty ([], []) = true
          | isEmpty _        = false
    end
    
  2. var Queue = function (items) {
        this.elements = items || [];
    };
    
    Queue.prototype.enqueue = function (item) {
        this.elements.push(item);
        return this;
    };
    
    Queue.prototype.dequeue = function () {
        return this.elements.shift();
    };
    
    Queue.prototype.isEmpty = function () {
        return this.elements.length === 0;
    };
    
    window.tasksQueue = new Queue(["Wake Up", "Shower"]);
    
    tasksQueue.enqueue("Dress")
        .enqueue("Have Breakfast")
        .enqueue("Go to work");
    
    while(!tasksQueue.isEmpty()) {
        console.log(tasksQueue.dequeue());
    }
    
  3. treeowl said

    Okasaki “banker’s queues” in Haskell:

    import Prelude hiding (head,tail)
    import qualified Prelude as P
    
    data Queue a = Q [a] {-# UNPACK #-} !Int [a] {-#UNPACK#-} !Int
    
    -- toList is faster than just removing items one at a time because it avoids all the queue rotations.
    toList :: Queue a -> [a]
    toList (Q fs _ rs _) = fs ++ reverse rs
    
    -- fromList is faster than just snocing items on one at a time because it
    -- avoids all the queue rotations. It also produces a queue in the optimal state, with everything in the front list.
    fromList :: [a] -> Queue a
    fromList l = Q l (length l) [] 0
    
    size (Q _ flen _ rlen) = flen+rlen
    
    emptyq = Q [] 0 [] 0
    
    head :: Queue a -> a
    head (Q [] _ _ _) = error "Cannot get the head of an empty queue."
    head (Q (h:_) _ _ _) = h
    
    tail :: Queue a -> Queue a
    tail (Q [] _ _ _) = error "Cannot get the tail of an empty queue."
    tail (Q (f:fs) flen rs rlen) = queue fs (flen-1) rs rlen
    
    snoc :: Queue a -> a -> Queue a
    snoc (Q fs flen rs rlen) x = queue fs flen (x:rs) (rlen+1)
    
    queue :: [a] -> Int -> [a] -> Int -> Queue a
    queue f flen r rlen
      | flen >= rlen = Q f flen r rlen
      | otherwise = Q (f++reverse r) (flen+rlen) [] 0
    
  4. treeowl said

    I forgot to mention above that if the size operation is not needed, it’s possible to save a bit of space by storing only the difference between the front and rear lengths, rather than the lengths themselves.

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 598 other followers

%d bloggers like this: