Здравствуйте VladD2, Вы писали:

AVK>>Контейнер тут не при чем. Достаточно было сделать LinkedList а уж от него унаследовать Queue и Stack. Причем судя по ildasm практически один и тот же связаный список реализован в Queue и Stack раздельно. Причины этого мне не понятны.

VD>Как манимум Stack нмного эфективнее создавать на базе обычного массива.
Я на твоем месте попробовал бы и кинул сюда исходнички и результаты. Скорее всего ты прав. Впрочем попробуем:

using System;
using System.Collections;

class ArrayStack {
 private ArrayList al = new ArrayList();
 public void Push(object obj) {
  al.Add(obj);
 }
 public object Pop() {
  object obj = al[al.Count-1];
  al.RemoveAt(al.Count-1);
  return obj;
 }
}

public class Test {
 private const int ITER_COUNT = 1000000;

 public static void Main() {
  ArrayStack ars = new ArrayStack();
  int st = Environment.TickCount;
  for(int i = 0; i < ITER_COUNT; i++) {
   ars.Push(new object());
  }
  for(int i = 0; i < ITER_COUNT; i++) {
   ars.Push(new object());
   ars.Pop();
  }
  for(int i = 0; i < ITER_COUNT; i++) {
   ars.Pop();
  }
  Console.WriteLine(Environment.TickCount-st);

  Stack s = new Stack();
  st = Environment.TickCount;
  for(int i = 0; i < ITER_COUNT; i++) {
   s.Push(new object());
  }
  for(int i = 0; i < ITER_COUNT; i++) {
   s.Push(new object());
   s.Pop();
  }
  for(int i = 0; i < ITER_COUNT; i++) {
   s.Pop();
  }
  Console.WriteLine(Environment.TickCount-st);

  Queue q = new Queue();
  st = Environment.TickCount;
  for(int i = 0; i < ITER_COUNT; i++) {
   q.Enqueue(new object());
  }
  for(int i = 0; i < ITER_COUNT; i++) {
   q.Enqueue(new object());
   q.Dequeue();
  }
  for(int i = 0; i < ITER_COUNT; i++) {
   q.Dequeue();
  }
  Console.WriteLine(Environment.TickCount-st);
 }
}

Смысл теста такой — сначала забиваем стек, затем работаем на его вершине и затем опустошаем. Очередь приведена в качестве стека на основе связаного списка. Понятно что забирает элементы она с другого конца, но для связаного списка конец с которого мы будем выдергивать элементы на скорость влияния не оказывает.

И результат
407
515
688

Что ж
1) Массивы действительно быстрее связаного списка. Впрочем это и понятно. В случае выдергивания элементов с конца нет необходимости передвижки всех элементов, а доступ к массиву быстрее.
2) Похоже что дотнетовкий список реализован на основе массивов
3) А вот почему самопальный стек на основе ArrayList оказался быстрее — для меня загадка.