A stack with O(1) push, pop, and min

minstack.d

import std.array;

struct MinStack(T)
{
	private {
		Appender!(T[],T) items;
		Appender!(T[],T) mins;
	}

	auto pop() {
		if (items.data.length) {
			mins.shrinkTo(mins.data.length - 1);
			auto retval = items.data[$-1];
			items.shrinkTo(items.data.length - 1);
			return retval;
		} else {
			throw new Exception("stack is empty");
		}
	}

	auto push(T item) {
		items.put(item);
		if (mins.data.length && mins.data[$-1] < item) {
			mins.put(mins.data[$-1]);
		} else {
			mins.put(item);
		}
	}

	auto min() {
		if (mins.data.length) {
			return mins.data[$-1];
		} else {
			throw new Exception("stack is empty");
		}
	}
}

unittest
{
	MinStack!int minStack;
	minStack.push(3);
	assert(minStack.min() == 3);
	minStack.push(2);
	assert(minStack.min() == 2);

	minStack.push(5);
	minStack.push(1);
	assert(minStack.min() == 1);

	auto top = minStack.pop();
	assert(top == 1);
	assert(minStack.min() == 2);
	top = minStack.pop();
	assert(minStack.min() == 2);

	top = minStack.pop();
	assert(top == 2);
	assert(minStack.min() == 3);
}

void main() {
}