Download Reference Manual
The Developer's Library for D
About Wiki Forums Source Search Contact

Is there a Stack class?

Moderators: larsivi kris

Posted: 09/26/07 17:28:53

Is there a Stack class in Tango?

Author Message

Posted: 10/02/07 21:10:46

Not as such, but it's trivial to make one using arrays. I guess there's not one in the collection package since it would not not really match the API model there? Reset, push and pop are pretty much the only operations?

Posted: 10/17/07 11:11:01

I believe a growing stack like GrowBuffer?, but templated to build array of any type not just char[], would be useful. Yes, it only takes few lines to write one but when reused these lines grow... Mine looks like this (I think it doesn't work for non-class type, I haven't tested really):

class SimpleStack(T)
{
	this(int step=5){this.step=step<=0?1:step;}

	void push(T item)
	{
		if(pointer==stack.length) stack.length=stack.length+step;
		stack[pointer++]=item;
	}

	T unpush()
	{
		T ret=pop();
		if(stack.length) stack.length=stack.length-1;
		return ret;
	}

	T pop()
	{
		T ret=last();
		if(pointer>0) --pointer;
		return ret;
	}

	T last()
	{
		if(stack.length) return stack[pointer-1];
		else return T.init;
	}

	int length(){return pointer;}
	int size(){return stack.length;}
	T[] useful(){return stack[0..pointer];}
	void empty(){if(stack.length) delete stack;}

	private:
	int step;
	int pointer;
	T[] stack;
}

Posted: 10/17/07 16:27:23

I'm trying to figure out where to put something like this. The notion belongs in collection, but the model does not ...

Posted: 10/18/07 19:09:31

I use LinkSeq? to mimic a stack.

Here is a trivial stack class:

class Stack(T) : LinkSeq!(T)
{
  alias prepend push;
  alias take pop;
}

I use prepend instead of append because its O(1).

-Steve

Posted: 10/18/07 19:18:37

Nice :)