Home

C# Collections: Introduction to Queues
   

Queues Fundamentals
 

Introduction

A queue is a list in which the first item added to the list will be the first one to be removed. This is referred to as first-in first-out (FIFO). To illustrate it, when people stand in line at one cashier of a supermarket, the first customer in line in front of the cashier will be the first to be served (and the first to leave the supermarket).

To create a collection class that supports queues, you have various options such as arrays or linked lists.

Creating an Array-Based Queue

To create a collection class that performs its operations as a queue, you can use a field that is an array. Here is an example of starting such a class:

interface IQueue<T>
{
}

public class Queue<T> : IQueue<T>
{
    private T[] items;
}

 (We are deriving our class from an interface but you don't have to. Also, we will create our class as a generic one but if you want to use a specific data type, you can. Here is an example:

public class Queue
{
    double[] items;
}

)

If you use an array, make sure you initialize it before using it. This can be done as follows:

public class Queue<T> : IQueue<T>
{
    private T[] items;

    public Queue()
    {
        items = new T[10];
    }
}

To monitor the size of the collection, you should create a property that produces an integral number to that effect. Here is an example:

interface IQueue<T>
{
    int Count { get; }
}

public class Queue<T> : IQueue<T>
{
    private int size;
    private T[] items;

    public Queue()
    {
        size = 0;
        items = new T[10];
    }

    public int Count
    {
        get
        {
            return size;
        }
    }
}

On the other hand, you can create a read-only method that checks whether the queue is currently empty or contains at least one item. If the number of items is 0, the list is empty. If the size is greater than 0, the list is not empty. Here is an example of the property:

using System;

interface IQueue<T>
{
    int Count { get; }
    bool IsEmpty { get; }
}

public class Queue<T> : IQueue<T>
{
    private int size;
    private T[] items;

    public Queue()
    {
        size = 0;
        items = new T[10];
    }

    public int Count
    {
        get
        {
            return size;
        }
    }

    public bool IsEmpty
    {
        get
        {
            return (size == 0);
        }
    }
}

public class Exercise
{
    public static int Main()
    {
        Queue<double> que = new Queue<double>();

        bool empty = que.IsEmpty;
        Console.WriteLine("The list is empty: {0}", empty);

        return 0;
    }
}

This would produce:

The list is empty: True
Press any key to continue . . .

Enqueing a Queue

When an item joins a queue, it is said to be added to the end of the queue. In an array, to enqueue an item, simply assign it to the size of the array. This size would represent the last index of the list. After adding the new item, if you are numbering the items in the collection, make sure you increment the count before exiting the methodHere is an example:

using System;

interface IQueue<T>
{
    int Count { get; }
    bool IsEmpty { get; }
    void Enqueue(T item);
}

public class Queue<T> : IQueue<T>
{
    private int size;
    private T[] items;

    public Queue()
    {
        size = 0;
        items = new T[10];
    }

    public int Count
    {
        get
        {
            return size;
        }
    }

    public bool IsEmpty
    {
        get
        {
            return (size == 0);
        }
    }

    public void Enqueue(T item)
    {
        items[size] = item;
        size++;
    }
}

public class Exercise
{
    public static int Main()
    {
        Queue<double> que = new Queue<double>();

        bool empty = que.IsEmpty;
        Console.WriteLine("The list is empty: {0}", empty);

        que.Enqueue(424.06);
        que.Enqueue(12500.58);
        que.Enqueue(28.0746);
        que.Enqueue(1046.88);

        empty = que.IsEmpty;
        Console.WriteLine("The list is empty: {0}", empty);

        return 0;
    }
}

This would produce:

The list is empty: True
The list is empty: False
Press any key to continue . . .

Peeking an Item of a Queue

As done for a stack, to get an item from a queue, you peek it. This is done on the item that starts the list, which is the item that was added last. Based on this, to peek an item, create a method that simply returns the item at index 0. If the list is empty, you should return the default value of the type of items that make up the list. Here is an example:

using System;

interface IQueue<T>
{
    int Count { get; }
    bool IsEmpty { get; }
    void Enqueue(T item);
    T Peek();
}

public class Queue<T> : IQueue<T>
{
    private int size;
    private T[] items;

    public Queue()
    {
        size = 0;
        items = new T[10];
    }

    public int Count
    {
        get
        {
            return size;
        }
    }

    public bool IsEmpty
    {
        get
        {
            return (size == 0);
        }
    }

    public void Enqueue(T item)
    {
        items[size] = item;
        size++;
    }

    public T Peek()
    {
        if (size == 0)
            return default(T);
        return items[0];
    }
}

public class Exercise
{
    public static int Main()
    {
        Queue<double> que = new Queue<double>();

        bool empty = que.IsEmpty;
        Console.WriteLine("The list is empty: {0}", empty);

        que.Enqueue(424.06);
        Console.WriteLine("Number: {0}", que.Peek());
        que.Enqueue(12500.58);
        Console.WriteLine("Number: {0}", que.Peek());
        que.Enqueue(28.0746);
        Console.WriteLine("Number: {0}", que.Peek());
        que.Enqueue(1046.88);
        Console.WriteLine("Number: {0}", que.Peek());

        empty = que.IsEmpty;
        Console.WriteLine("The list is empty: {0}", empty);

        return 0;
    }
}

This would produce:

The list is empty: True
Number: 424.06
Number: 424.06
Number: 424.06
Number: 424.06
The list is empty: False
Press any key to continue . . .

Dequeuing an Item

As mentioned already, when items are on a queue, the first to be enqueued will be the first to be removed. This operation is referred to as dequeueing. To dequeue (pronounce dek) an item, create a method and define it as follows:

  1. Get a reference to the lastly added item, which is the item at index = 0
  2. Starting from the end of the list, assign the item at an index to the item at the previous index. This would accomplish two things. The item that was lastly added would be lost. The last item and the item before it would have the same value, which would be the last useless
  3. Decrease the number of items since the last one is not needed anymore
  4. Return the reference you got in the first step

Here is an example of creating and using a peeking method:

using System;

interface IQueue<T>
{
    int Count { get; }
    bool IsEmpty { get; }
    void Enqueue(T item);
    T Peek();
    T Dequeue();
}

public class Queue<T> : IQueue<T>
{
    private int size;
    private T[] items;

    public Queue()
    {
        size = 0;
        items = new T[10];
    }

    public int Count
    {
        get
        {
            return size;
        }
    }

    public bool IsEmpty
    {
        get
        {
            return (size == 0);
        }
    }

    public void Enqueue(T item)
    {
        items[size] = item;
        size++;
    }

    public T Peek()
    {
        if (size == 0)
            return default(T);
        return items[0];
    }

    public T Dequeue()
    {
        T first = items[0];

        for (int i = 0; i < size; i++)
            items[i] = items[i + 1];
        size--;

        return first;
    }
}

public class Exercise
{
    public static int Main()
    {
        Queue<double> que = new Queue<double>();

        bool empty = que.IsEmpty;
        Console.WriteLine("The list is empty: {0}", empty);

        que.Enqueue(424.06);
        Console.WriteLine("Number: {0}", que.Dequeue());
        que.Enqueue(12500.58);
        Console.WriteLine("Number: {0}", que.Dequeue());
        que.Enqueue(28.0746);
        Console.WriteLine("Number: {0}", que.Dequeue());
        que.Enqueue(1046.88);
        Console.WriteLine("Number: {0}", que.Dequeue());

        empty = que.IsEmpty;
        Console.WriteLine("The list is empty: {0}", empty);

        return 0;
    }
}

This would produce:

The list is empty: True
Number: 424.06
Number: 12500.58
Number: 28.0746
Number: 1046.88
The list is empty: True
Press any key to continue . . .

Clearing a Queue

To remove all items of a queue, you can simply reset the count of items to 0. Here is an example:

interface IQueue<T>
{
    int Count { get; }
    bool IsEmpty { get; }
    void Enqueue(T item);
    T Peek();
    T Dequeue();
    void Clear();
}

public class Queue<T> : IQueue<T>
{
    private int size;
    private T[] items;

    public Queue()
    {
        size = 0;
        items = new T[10];
    }

    public int Count
    {
        get
        {
            return size;
        }
    }

    public bool IsEmpty
    {
        get
        {
            return (size == 0);
        }
    }

    public void Enqueue(T item)
    {
        items[size] = item;
        size++;
    }

    public T Peek()
    {
        if (size == 0)
            return default(T);
        return items[0];
    }

    public T Dequeue()
    {
        T first = items[0];

        for (int i = 0; i < size; i++)
            items[i] = items[i + 1];
        size--;

        return first;
    }

    public void Clear()
    {
        size = 0;
    }
}

Enumerating a Queue

By default, if you have created a queue class, it doesn't allow you to use a foreach loop. If you this feature, create a GetEnumerator() method that returns IEnumerator. In the method, start from the beginning of the list, use a while loop to yield return the current item and increment the count each time. Here is an example:

using System;
using System.Collections.Generic;

interface IQueue<T>
{
    int Count { get; }
    bool IsEmpty { get; }
    void Enqueue(T item);
    T Peek();
    T Dequeue();
    void Clear();
    IEnumerator<T> GetEnumerator();
}

public class Queue<T> : IQueue<T>
{
    private int size;
    private T[] items;

    public Queue()
    {
        size = 0;
        items = new T[10];
    }

    public int Count
    {
        get
        {
            return size;
        }
    }

    public bool IsEmpty
    {
        get
        {
            return (size == 0);
        }
    }

    public void Enqueue(T item)
    {
        items[size] = item;
        size++;
    }

    public T Peek()
    {
        if (size == 0)
            return default(T);
        return items[0];
    }

    public T Dequeue()
    {
        T first = items[0];

        for (int i = 0; i < size; i++)
            items[i] = items[i + 1];
        size--;

        return first;
    }

    public void Clear()
    {
        size = 0;
    }

    public IEnumerator<T> GetEnumerator()
    {
        int counter = 0;

        while (counter < size)
        {
            yield return items[counter];
            counter++;
        }
    }
}

public class Exercise
{
    public static int Main()
    {
        int i = 1;
        Queue<double> que = new Queue<double>();

        que.Enqueue(2748.42);
        que.Enqueue(115.842);
        que.Enqueue(42408.02);
        que.Enqueue(2048.42);

        foreach (double d in que)
            Console.WriteLine("Value {0}: {1}", i++, d);

        return 0;
    }
}

This would produce:

Value 1: 2748.42
Value 2: 115.842
Value 3: 42408.02
Value 4: 2048.42
Press any key to continue . . .

Checking the Presence of an Item

Once a queue is established, you may want to find out whether it contains a certain value. To do this, you can create a Contains method that looks for an item passed as argument. If the item exists in the collection, the method returns true. Otherwise it returns false. Here is an example:

using System;
using System.Collections.Generic;

interface IQueue<T>
{
    int Count { get; }
    bool IsEmpty { get; }
    void Enqueue(T item);
    T Peek();
    bool Contains(T item);
    T Dequeue();
    void Clear();
    IEnumerator<T> GetEnumerator();
}

public class Queue<T> : IQueue<T>
{
    private int size;
    private T[] items;

    public Queue()
    {
        size = 0;
        items = new T[10];
    }

    public int Count
    {
        get
        {
            return size;
        }
    }

    public bool IsEmpty
    {
        get
        {
            return (size == 0);
        }
    }

    public void Enqueue(T item)
    {
        items[size] = item;
        size++;
    }

    public T Peek()
    {
        if (size == 0)
            return default(T);
        return items[0];
    }

    public bool Contains(T item)
    {
        foreach (T value in items)
            if (value.Equals(item))
                return true;

        return false;
    }

    public T Dequeue()
    {
        T first = items[0];

        for (int i = 0; i < size; i++)
            items[i] = items[i + 1];
        size--;

        return first;
    }

    public void Clear()
    {
        size = 0;
    }

    public IEnumerator<T> GetEnumerator()
    {
        int counter = 0;

        while (counter < size)
        {
            yield return items[counter];
            counter++;
        }
    }

}

public class Exercise
{
    public static int Main()
    {
        int i = 1;
        Queue<double> que = new Queue<double>();

        que.Enqueue(2748.42);
        que.Enqueue(115.842);
        que.Enqueue(42408.02);
        que.Enqueue(2048.42);

        foreach (double d in que)
            Console.WriteLine("Value {0}: {1}", i++, d);

        if (que.Contains(115.842) == true)
            Console.WriteLine("\nThe list contains 115.842\n");
        else
            Console.WriteLine("\nThe list doesn't have 115.842\n");

        if (que.Contains(1195.842) == true)
            Console.WriteLine("\nThe list contains 1195.842\n");
        else
            Console.WriteLine("\nThe list doesn't have 1195.842\n");

        return 0;
    }
}

This would produce:

Value 1: 2748.42
Value 2: 115.842
Value 3: 42408.02
Value 4: 2048.42

The list contains 115.842
The list doesn't have 1195.842

Press any key to continue . . .

 

 
 
Home Copyright © 2010-2016, FunctionX