Can I Limit the depth of a Generic Stack?

Question

Is there a built in way to limit the depth of a System.Collection.Generics.Stack? So that if you are at max capacity, pushing a new element would remove the bottom of the stack?

I know I can do it by converting to an array and rebuilding the stack, but I figured there's probably a method on it already.

EDIT: I wrote an extension method:

    public static void Trim<T> (this Stack<T> stack, int trimCount) 
    {
        if (stack.Count <= trimCount)
            return;

       stack = new 
            Stack<T>
            (
                stack
                    .ToArray()
                    .Take(trimCount)
            );           
    }

So, it returns a new stack upon trimming, but isn't immutability the functional way =)

The reason for this is that I'm storing undo steps for an app in a stack, and I only want to store a finite amount of steps.

Answer 1

I can't see a way. You can inherit from Stack<T>, but there doesn't appear to be anything useful to override.

The easy (if a bit tedious) way would be to wrap the Stack<T> in your own, say, LimitedStack<T>. Then implement the methods you want and pass through to an internal Stack<T>, while including your limiting logic in the Push method and wherever else you need it.

It's a pain to write all those pass-through members, especially if you're implementing all the same interfaces as Stack<T>...but on the other hand, you only have to do it once and then it's done.

Answer 2

I believe you're looking for a (possibly-modified) dequeue - the data structure that allows access from either end.

Answer 3

What you are looking for is called a dropout stack. AFAIK, the BCL does not contain one, although they are trivial to implement. Typically Undo and Redo functionality relies on such data structures.

They are basically an array, and when you push onto the stack the 'top' of the stack moves around the array. Eventually the top will wrap back to the beginning when the stack is full and replace the 'bottom' of the stack.

Google didn't provide much info on it. This is the best i could find:

(Warning PDF) http://courses.cs.vt.edu/~cs2704/spring04/projects/DropOutStack.pdf

Here's some boiler plate code, to get you started. I'll let you fill in the rest (sanity checking, count, indexer, etc.)

class DropOutStack<T>
{
 private T[] items;
 private int top = 0;
 public DropOutStack(int capacity)
 { 
  items = new T[capacity];
 }

 public void Push(T item)
 {
  items[top] = item;
  top = (top + 1) % items.Length;
 }
 public T Pop()
 {
  top = (items.Length + top - 1) % items.Length;
  return items[top];
 }
}

Answer 4

You're actually looking at something similar to circular list implementation. There's a LimitedQueue implementation done by PIEBALDconsult at CodeProject. It's similar to your requirement. You just need to wrap Stack instead of Queue as done by the author. Plus the author also implemented indexer, which is handy if you need to access anything else other than the top stack (to show undo list maybe).

EDIT: The author's implementation also raise an event when the last(first, depends on whether it's a queue or stack) is being removed, so that you can know when something is being thrown away.