CS131: Queue

Que is a linear list data structure. The insert and remove operations are performed at the opposite ends of the list which are called the rear and the front respectively.

enqueue   ---->   |  3 |  4 |  2 |  <------ dequeue
              rear              front

Fig: Queue showing rear and front

A que can be implemented using a circular array or a linked list that maintains the rear and front item reference.

enqueue   -----+                       +------ dequeue
               |                       |    
               v  rear           front v
     +---->  |  |  3 |  4 |  2 | 7 | 10 |  |  | >-----+
     |                                                |
     +------------------------------------------------+

Fig: Circular list implementation using array

enqueue   -----+                       +------ dequeue
               |                       |    
               v  rear           front v
   [head]---> [3|*]-->[4|*]-->[2|*]-->[9|*]--->$

Fig: Linked list implementation

Operations

    public interface Queue
    {
        /// <summary>
        /// Inserts an item to the rear of the list of items.
        /// </summary>
        /// <param name="item">item to be inserted</param>
        void enqueue(object item);

        /// <summary>
        /// Removes an item from the front of the list of items and returns it.
        /// </summary>
        /// <returns>The removed item</returns>
        object dequeue();

        /// <summary>
        /// Returns the item in front of the list of items. The list is not altered in any way.
        /// </summary>
        /// <returns>The item at the front of the queue</returns>
        object front();

        /// <summary>
        /// Check if the queue is empty or not
        /// </summary>
        /// <returns>true if queue is empty, false otherwise</returns>
        bool empty();

        /// <summary>
        /// Checks if the queue is full or not
        /// </summary>
        /// <returns>true if queue is full, false otherwise</returns>
        bool full();

        /// <summary>
        /// Calculates the number of items in the queue
        /// </summary>
        /// <returns>Number of items in teh queue</returns>
        int size();
    }

Implementation

    public class Node
    {
        public Node next, previous;
        public object data;
    }


    public class LinkedListQueue : Queue
    {
        Node rear_item, front_item;
        int item_count;

        public LinkedListQueue()
        {
            rear_item = front_item = null;
            item_count = 0;
        }

        public void enqueue(object data)
        {
            SNode new_item = new SNode();
            new_item.data = data;
            new_item.next = null;
            new_item.previous = front_item;

            if (front_item != null)
            {
                front_item.next = new_item;
            }

            front_item = new_item;

            if (item_count == 0)
            {
                rear_item = new_item;
            }

            item_count++;
        }

        public object dequeue()
        {
            if (front_item == null)
            {
                return null;
            }

            object data = front_item.data;

            item_count--;

            if (item_count == 0)
            {
                rear_item = null;
                front_item = null;
            }
            else
            {
                front_item = front_item.previous;
                front_item.next = null;
            }

            return data;
        }

        public object front()
        {
            if (front_item == null)
            {
                return null;
            }

            return front_item.data;
        }

        public bool empty()
        {
            return (item_count == 0);
        }

        public bool full()
        {
            return false;
        }

        public int size()
        {
            return item_count;
        }

        public static void Test()
        {
            Queue queue = new LinkedListQueue();
            object data = 10;
            queue.enqueue(data);
            object item = queue.dequeue();
            TestEngine.AssertEquals(item, data, "Dequeue does not return expected data");
        }
    }    

Deque

A double ended queue where insertion and deletion are allowed on both end of the list.

Problem: Implement a deque