--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/doodle/containers/stack.d	Mon Apr 12 14:01:54 2010 +0930
@@ -0,0 +1,97 @@
+module doodle.containers.stack;
+
+class Stack(T) {
+    this() {
+        _data.length = 1;
+    }
+
+    bool isEmpty() {
+        return _depth == 0;
+    }
+
+    void push(T t) {
+        if (_depth == _data.length) {
+            // Need it to grow
+            _data.length = 2 * _data.length;
+        }
+
+        _data[_depth] = t;
+        ++_depth;
+    }
+
+    T pop() {
+        assert(!isEmpty());
+        --_depth;
+        auto t = _data[_depth];
+        _data[_depth] = T.init;
+        return t;
+    }
+
+    T top() {
+        assert(!isEmpty());
+        return _data[_depth - 1];
+    }
+
+    void top(T t) {
+        assert(!isEmpty());
+        _data[_depth - 1] = t;
+    }
+
+    void clear() {
+        while (_depth > 0) {
+            --_depth;
+            _data[_depth] = T.init;
+        }
+    }
+
+    void shrink() {
+        size_t new_l = _data.length;
+        do new_l /= 2; while (new_l > _depth * 2);
+        _data.length = new_l;
+    }
+
+    void capacity(size_t l) {
+        if (l > _data.length) {
+            size_t new_l = _data.length;
+            do new_l *= 2; while (new_l < l);
+            _data.length = new_l;
+        }
+    }
+
+    private {
+        size_t capacity() {
+            return _data.length;
+        }
+
+        size_t depth() {
+            return _depth;
+        }
+
+        T[] _data;          //  capacity
+        size_t _depth;
+    }
+}
+unittest {
+    auto s = new Stack!(int);
+
+    assert(s.capacity() == 1);
+
+    assert(s.depth() == 0);
+    s.push(15);
+    assert(s.depth() == 1);
+    assert(s.top() == 15);
+    assert(s.pop() == 15);
+    assert(s.depth() == 0);
+    assert(s.isEmpty());
+
+    assert(s.capacity() == 1);
+    s.push(12);
+    assert(s.capacity() == 1);
+    s.push(13);
+    assert(s.capacity() == 2);
+    s.push(14);
+    assert(s.depth() == 3);
+    assert(s.capacity() == 4);
+    s.push(s.pop());
+    assert(s.capacity() == 4);
+}