stack collection missing shift and unshift in C# 2.0

Question

Bizarrely the stack collection seems to be missing the rather basic shift and unshift methods* and I'm working in 2.0 so I can't just extend them.

Is there any reasonable technique or alternative collection class to get these methods available? I need push and pop as well.

Edit: looks like the collection I want is indeed a deque which is happily not native to C# :(

Can't use third party libraries at this time so I'll be going with the clunky LinkedList (I say clunky because reading and removing are two operations where shift would be one) but I think I'd recommend the PowerCollections approach to anyone who could use it. Or better yet, upgrading to extension methods.

sigh

---

* Apologies, I didn't realise these were uncommon terms, I thought I just didn't know where to find them in the API. For reference:

shift = remove first element

unshift = insert element at beginning of collection

Answer 1

I would say use a LinkedList<T>. It has methods for adding and removing from the front, as well as adding and removing from the back. I've never heard of shifting and unshifting, but I'm assuming that's what it means.

Answer 2

Never heard of shift/unshift in a stack. The Stack class does provide Pop, Peek, and Push though.

Answer 3

You are using the wrong class if you want a shift/unshift method. A stack is a Last-In First-Out (LIFO) data structure.

If you want shift/unshift without pop and push, use a Queue. If you want both, I recommend using Deque from the PowerCollections library

Answer 4

This is not exactly the best, but it comes close to being a Javascript array with shift/unshift and push/pop. Its does not hide the inner workings, and you can index any item you want. I has the basic functionality though.

 public class JSList<T> : List<T>
{
    public JSList() : base() {}

    /// <summary>
    /// this the add item to the start of the list
    /// </summary>
    /// <param name="v"></param>
    public void Shift(T v)
    {
        this.Insert(0, v);
    }

    /// <summary>
    /// remove item at the start of the list
    /// </summary>
    /// <returns></returns>
    public T Unshift()
    {
        var toreturn = default(T);
        if (this.Count > 0)
        {
            toreturn = this[0];
            this.RemoveAt(0);
        }
        return toreturn;
    }

    /// <summary>
    /// Adds object to end of the list
    /// </summary>
    /// <param name="v"></param>
    public void Push(T v)
    {
        this.Add(v);
    }

    /// <summary>
    /// removes an item at the end of the list
    /// </summary>
    /// <returns></returns>
    public T Pop()
    {
        var toreturn = default(T);
        if (this.Count > 0)
        {
            toreturn = this[this.Count - 1];
            this.RemoveAt(this.Count - 1);
        }
        return toreturn;
    }

    public T Peek()
    {
        return this[this.Count - 1];
    }
}

Answer 5

You can fake extension methods as long as you are using C# 3.0 targeting 2.0.

Can you describe what the shift/unshift operations are?

Answer 6

By definition Stack class represents a way of managing elements in a collection using the Last In First Out (LIFO) technique for adding and removing elements. LIFO simply means that the last element added to a collection will automatically be the first one removed.

The functionality you want from it is something custom, but easily can be achieved in following way

public class MyStack<T>:Stack<T>{
  public void Shift(T item){
     // load stack into internal ordered list
     // clear stack content
     // insert into internal list at desired location
     // populate stack with content from internal list
  }
  public void Unshift(T item){
     // load stack into internal ordered list
     // clear stack content
     // insert into internal list at desired location
     // populate stack with content from internal list
  }
}

and seems this it-s all :)

Answer 7

Shift ==> Stack.Pop
Unshift ==> Stack.Push

Unshift doesn't return the number of elements in the Stack, you have the Stack.Count property for that.

Also, there's Stack.Peek, to get the first element without removing it.

Stack<T> class