This program implements a queue that supports the following operations:

  • bool IsEmpty() - Determines if the queue is empty.
  • void Insert(T item) - Adds a new element to the queue (an enqueue operation).
  • T Delete(int k) - Deletes and returns the kth least recently inserted item.

It provides two implementations of the queue:

ListGeneralizedQueue - uses a linked list:

  • Finding the kth element may be slow as it requires traversing the list.
  • Deletion is fast as it only requires re-assigning a reference.

ArrayGeneralizedQueue - uses an array:

  • Finding the kth element is very fast as it is accessed by an index.
  • Deletion may be slow as it requires shifting elements in order to fill up a gap left after the removed element.
using System;

namespace ConsoleTest
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("*** GeneralizedQueue as a LinkedList ***\n");

            ListGeneralizedQueue  q1 = new ListGeneralizedQueue();

            Console.WriteLine("Insert a few items:");
            q1.Insert("A");
            q1.Insert("B");
            q1.Insert("C");
            q1.Insert("D");
            q1.Insert("E");
            q1.ShowItems();

            Console.WriteLine("Remove 3rd element {0}:", q1.Delete(2)); // k=2 for the 3rd element
            q1.ShowItems();

            Console.WriteLine("Remove 4th element {0}:", q1.Delete(3)); // k=3 for the 4rd element
            q1.ShowItems();

            Console.WriteLine("Remove 1st element {0}:", q1.Delete(0)); // k=0 for the 1st element
            q1.ShowItems();

            Console.WriteLine("Remove 2nd element {0}:", q1.Delete(1)); // k=1 for the 2nd element
            q1.ShowItems();

            Console.WriteLine("Remove 1st element {0}:", q1.Delete(0)); // k=0 for the 1st element
            q1.ShowItems();


            Console.WriteLine("*** GeneralizedQueue as an Array ***\n");

            ArrayGeneralizedQueue q2 = new ArrayGeneralizedQueue(5);

            Console.WriteLine("Insert a few items:");
            q2.Insert("A");
            q2.Insert("B");
            q2.Insert("C");
            q2.Insert("D");
            q2.Insert("E");
            q2.ShowItems();

            Console.WriteLine("Remove 3rd element {0}:", q2.Delete(2)); // k=2 for the 3rd element
            q2.ShowItems();

            Console.WriteLine("Remove 4th element {0}:", q2.Delete(3)); // k=3 for the 4rd element
            q2.ShowItems();

            Console.WriteLine("Remove 1st element {0}:", q2.Delete(0)); // k=0 for the 1st element
            q2.ShowItems();

            Console.WriteLine("Remove 2nd element {0}:", q2.Delete(1)); // k=1 for the 2nd element
            q2.ShowItems();

            Console.WriteLine("Remove 1st element {0}:", q2.Delete(0)); // k=0 for the 1st element
            q2.ShowItems();

            Console.ReadKey();
        }

        class ListGeneralizedQueue
        {
            private Node first; // link to least recently added node
            private Node last;  // link to most recently added node
            private int N;      // queue size

            public bool IsEmpty { get { return first == null; } } // the same as N == 0
            public int Size { get { return N; } }

            // This is a standard Enqueue operation.
            public void Insert(T item)
            {
                // Add item to the end of the list.
                Node oldLast = last;
                last = new Node();
                last.Item = item;
                last.Next = null;

                if (IsEmpty)
                    first = last;
                else
                    oldLast.Next = last;

                ++N;
            }

            // Delete and return the k-th least recently inserted item.
            public T Delete(int k)
            {
                T item = default(T);

                // Is the list empty?
                if (first == null)
                    return item;

                // Does the list have only one element?
                if (first.Next == null)
                {
                    item = first.Item;
                    first = null; // remove the only element in the list
                    last = null;
                    return item;
                }

                // Do we need to remove the first element?
                if (k == 0)
                {
                    item = first.Item;
                    first = first.Next; // remove the first element
                    return item;
                }

                // Determine the element immediately before the k-th element.
                Node node = first;
                int n = 0;
                while (node.Next.Next != null && n < k - 1)
                {
                    node = node.Next;
                    ++n;
                }

                if (n == k - 1) // check if the requested element exists
                {
                    item = node.Next.Item;

                    // k-1 is node
                    // k is node.Next; this is the element we want to remove
                    // k+1 is node.Next.Next
                    node.Next = node.Next.Next; // remove the k-th element

                    // If this is the last element, keep it as last.
                    if (node.Next == null)
                        last = node;
                }

                return item;
            }

            public void ShowItems()
            {
                for (Node node = first; node != null; node = node.Next)
                {
                    Console.Write("{0} ", node.Item.ToString());
                }
                Console.WriteLine();
                Console.WriteLine("First = {0}->{1}", (first != null ? first.Item.ToString() : "null"), (first != null && first.Next != null ? first.Next.Item.ToString() : "null"));
                Console.WriteLine("Last  = {0}->{1}", (last != null ? last.Item.ToString() : "null"), (last != null && last.Next != null ? last.Next.Item.ToString() : "null")); // last.Next should always be null
                Console.WriteLine();
            }

            // Nested class to define nodes of linked list.
            private class Node
            {
                public T Item { get; set; }
                public Node Next { get; set; }

                public override string ToString() { return (Item == null ? "null" : Item.ToString()); }
            }
        }

        class ArrayGeneralizedQueue
        {
            private T[] a; // queue entries
            private int N; // queue size

            public bool IsEmpty { get { return N == 0; } }
            public int Size { get { return N; } }

            public ArrayGeneralizedQueue(int capacity)
            {
                a = new T[capacity];
            }

            // Add an item.
            public void Insert(T item)
            {
                // Check if the array is too small and if there is no room, double its size.
                if (N == a.Length)
                    Resize(2 * a.Length);

                // Add the item to the end of queue.
                a[N++] = item; // set a[N]=item and then increment N
            }

            // Delete and return the k-th least recently inserted item.
            public T Delete(int k)
            {
                // Is the index out of range?
                if (k > N - 1)
                    return default(T);

                T item = a[k];

                // Shift all the elements left.
                for (int i = k; i < N - 1; ++i)
                    a[i] = a[i + 1];

                a[N - 1] = default(T); // a[N-1] is an orphan; avoid loitering by overwriting the orphaned reference

                --N;

                // Half the array size if it is too large.
                if (N > 0 && N == a.Length / 4)
                    Resize(a.Length / 2);

                return item;
            }

            public void ShowItems()
            {
                for (int i = 0; i < N; ++i)
                {
                    Console.Write("{0} ", a[i].ToString());
                }
                Console.WriteLine();
                Console.WriteLine("First = {0}", (a[0] != null ? a[0].ToString() : "null"));
                Console.WriteLine("Last  = {0}", (N > 0 && a[N - 1] != null ? a[N - 1].ToString() : "null"));
                Console.WriteLine();
            }

            // Move an array of size N <= newSize to a new array of the newSize.
            private void Resize(int newSize)
            {
                T[] tmp = new T[newSize];
                for (int i = 0; i < N; ++i)
                    tmp[i] = a[i];
                a = tmp;
            }
        }
    }
}

Output:

*** GeneralizedQueue as a LinkedList ***

Insert a few items:
A B C D E
First = A->B
Last  = E->null

Remove 3rd element C:
A B D E
First = A->B
Last  = E->null

Remove 4th element E:
A B D
First = A->B
Last  = D->null

Remove 1st element A:
B D
First = B->D
Last  = D->null

Remove 2nd element D:
B
First = B->null
Last  = B->null

Remove 1st element B:

First = null->null
Last  = null->null

*** GeneralizedQueue as an Array ***

Insert a few items:
A B C D E
First = A
Last  = E

Remove 3rd element C:
A B D E
First = A
Last  = E

Remove 4th element E:
A B D
First = A
Last  = D

Remove 1st element A:
B D
First = B
Last  = D

Remove 2nd element D:
B
First = B
Last  = B

Remove 1st element B:

First = null
Last  = null