Queues

From

Current revision as of 21:23, 9 April 2009

A queue is another basic data structure that is normally homogeneous data. It is similar to a stack except it operates using a FIFO (First In, First Out) ordering. A queue is another way of expressing a line. The standard operations on a queue are enqueue(), dequeue(), peek(), and isEmpty().

Similar to a stack, a queue can be implemented either by an array or a linked list. When implemented using an array, it is normally implemented as a circular list (circular array). Items are added at the rear and removed from the front—in the same manner as a list. And, just like a list, we need an isFull() operation when using an array.

Behavior of Queues

When using a linked list, items are added to the rear and removed from the front, so we need both front and rear pointers. Also note that similar to a stack, the operations on a queue are constant.

Implementation of Queues

Linked List Implementation

The basic linked list implementation uses a singly-linked list with a tail pointer to keep track of the back of the queue.

type Queue<item_type>
  data list:Singly Linked List<item_type>
  data tail:List Iterator<item_type>

  constructor()
    list := new Singly-Linked-List()
    tail := list.get-begin() # null
  end constructor

When you want to enqueue something, you simply add it to the back of the item pointed to by the tail pointer. So the previous tail is considered next compared to the item being added and the tail pointer points to the new item. If the list was empty, this doesn't work, since the tail iterator doesn't refer to anything

 method enqueue(new_item:item_type)
   if is-empty()
     list.prepend(new_item)
     tail := list.get-begin()
   else
     list.insert_after(new_item, tail)
     tail.move-next()
   end if
 end method

The front item on the queue is just the one referred to by the linked list's head pointer

  method front():item_type
    return list.get-begin().get-value()
  end method

When you want to dequeue something off the list, simply point the head pointer to the previous from head item. The old head item is the one you removed of the list. If the list is now empty, we have to fix the tail iterator.

  method dequeue()
    list.remove-first()
    if is-empty()
      tail := list.get-begin()
    end if
  end method

A check for emptiness is easy. Just check if the list is empty.

  method is-empty():Boolean
    return list.is-empty()
  end method

A check for full is simple. Linked lists are considered to be limitless in size.

  method is-full():Boolean
    return False
  end method

A check for the size is again passed through to the list.

  method get-size():Integer
    return list.get-size()
  end method
end type

Performance Analysis

In a linked list, accessing the first element is an O(1) operation because the list contains a pointer directly to it. Therefore, enqueue, front, and dequeue are a quick O(1) operations.

The checks for empty/fullness as done here are also O(1).

The performance of getSize() depends on the performance of the corresponding operation in the linked list implementation. It could be either O(n), or O(1), depending on what time/space tradeoff is made. Most of the time, users of a Queue do not use the getSize() operation, and so a bit of space can be saved by not optimizing it.

Priority Queue

A priority queue is a standard queue, but the elements have a priority. When an item is entered into the queue, it moves up in the queue until it encounters an item of equal or greater priority. This is its position in the queue.

When implementing a priority queue, it is often implemented as a linked list. If I am adding items to the back of the list, and removing items from the head of the list, a priority queue is best implemented as a doubly linked list. In this case, we would do the following.

Adding an item to a priority queue that is a doubly linked list:

Let Temp be a node pointer that points to a new list node. Assume a list node has a field called priority.

If Rear is null, the list is empty. So, set Front and Rear of the head node to the value of Temp.

If Rear is not null, there is at least one node in the list.

If Temp.priority <= Rear.priority, then add Temp to the end of the list
    Set Rear.next to Temp.
    Set Temp.previous to Rear
    Set Rear to Temp
Else 
    let P be a node pointer
    let P = Rear
EndIf

While P is not null and Temp.priority > P.priority
    Let P = P.previous

If P is not null, then P has stopped at a node whose priority is greater or equal to that of
Temp. Temp is to be inserted after the node pointed to by P.
    Let Temp.previous = P
    Let Temp.next = P.next
    Let P.next.previous = Temp
    Let P.next = Temp


If P is null, then the node pointed to by Temp goes at the head of the list.
    Let Front.previous = Temp
    Let Temp.next = Front
    Let Front = Temp

When using a singly linked list, it becomes a little more difficult:

If Front is null, the list is empty, so
Let Front = Temp

If Front is not null, the list has at least one node in it
    If Temp.priority > Front.priority, then Temp goes in the front of the list
        Set Temp.next to Front
        Set Front to Temp.
        Set Rear to Temp.
    Else
        let P = Front

        While P.next is not null and P.next.priority >= Temp.priority
            Let P = P.next
        EndWhile

        If P.next is null, then Temp goes at the end of the list
            Set P.next to Temp 
            Set Rear to Temp
        Else
            Temp goes after the node pointed to by P
            Set Temp.next to P.
        EndElse
    EndElse
EndIf

Deque

A deque is a double-ended queue. This means that we can add or remove items from either end. The operations we need are addToFront(), addToBack(), removeFront(), removeBack(), peekFront(), peekBack(), isFull(), isEmpty().

Related Links

• Queue (Wikipedia)
• Deque (Wikipedia)
• Priority queue (Wikipedia)
• Queueing theory (Wikipedia)
• Circular buffer (Wikipedia)