Push a stack onto another stack

问题:

In C#, is there a way to push one Stack onto another Stack without iterating through the stack elements? If not, is there a better data structure I should be using? In Java you can do:

stack1.addAll(stack2)

I was hoping to find the C# analogue...

回答1:

0. Safe Solution - Extension Method

public static class Util {
        public static void AddAll<T>(this Stack<T> stack1, Stack<T> stack2) {
            T[] arr = new T[stack2.Count];
            stack2.CopyTo(arr, 0);

            for (int i = arr.Length - 1; i >= 0; i--) {
                stack1.Push(arr[i]);
            }
        }
    }

Probably the best is to create an extension method. Note that I am putting the first stack "on top" of the other stack so to speak by looping from arr.Length-1 to 0. So this code:

  Stack<int> x = new Stack<int>();
  x.Push(1);
  x.Push(2);

  Stack<int> y = new Stack<int>();
  y.Push(3);
  y.Push(4);          

  x.AddAll(y);

Will result in x being: 4,3,2,1. Which is what you would expect if you push 1,2,3,4. Of course, if you were to loop through your second stack and actually pop elements and then push those to the first stack, you would end up with 1,2,4,3. Again, modify the for loop as you see fit. Or you could add another parameter to specify which behavior you would like. I don't have Java handy, so I don't know what they do.

Having said that, you could do this, but I don't make any guarantees that it will continue to work. MS could always change the default behavior of how stack works when calling ToList. But, this is shorter, and on my machine with .NET 4.5 works the same as the extension method above:

1 Line Linq solution:

y.Reverse().ToList().ForEach(item => x.Push(item));

回答2:

In your question, wanting to do this "without iterating through the stack elements" basically means a LinkedList-based stack where you would just join the first and last elements to combine stacks in constant time.

However, unless you've a very specific reason for using LinkedList, it's likely a better idea to just iterate over an array-based (List-based) stack elements.

As far as a specific implementation goes, you should probably clarify whether you want the second stack to be added to the first in the same stack order or to be reversed into the first stack by being popped out.

回答3:

An addAll would just be a convenience method for a foreach loop that adds all of the items. There really isn't much you can do besides that:

foreach(var item in stack2)
    stack1.Push(item);

If you do it particularly frequently you can add an extension method for it, for your own convenience.

回答4:

This isn't meant to be done with the current .NET Stack implementation.

In order for the content of a Stack to be "grafted" onto the end of another Stack without iterating though its elements internal implementation details how the Stack class stores them in memory has to be known. Based on the principle of encapsulation this information is "officially" only know inside the Stack class itself. .NET's Stack does not expose methods to do this, so without using reflection there is no way to do it as the OP requested.

Conceivably you could use reflection to append to the internal array of one Stack the content of another Stack and also update the field that stores the stack length but this would be highly dependent on the implementation of the Stack class which could be changed in future versions of the framework without warning.

If you really need a Stack that can do this you could write your own Stack class from scratch or simply use another collection like ArrayList or LinkedList which have the method you want and add Push and Pop extension methods to them.