Stos o strukturze grafowej

Stos o strukturze grafowej jest skierowanym grafem acyklicznym, gdzie każda skierowana ścieżka reprezentuje stos. Struktura ta jest ważną częścią algorytmu Tomity (GLR) gdzie zastępuje zwykły stos automatu ze stosem jak również GLL Johnstone'a. To pozwala algorytmowi wybierać z powrotami z większą wydajnością.

W następującym diagramie są cztery stosy: {7,3,1,0}, {7,4,1,0}, {7,5,2,0}, and {8,6,2,0}.

Innym sposobem symulacji niedeterminizmu była by duplikacja stosu. Jest ona mniej wydajna ponieważ wierzchołki nie są dzielone. W tym przykładzie jest 16 wierzchołków zamiast 9.

Aby zwiększyć wydajność takich operacji jak dodawanie do grafu, powinna istnieć tablica poziomów takiego jak maksymalny rozmiar stosu gdzie w każdym poziomie byłaby tablica węzłów. Dodatkowo przydaje się węzeł "root" oznaczający pusty stos.

Operacje

Dodawanie do węzła

GSSnode* GSS::add(GSSnode* prev, int elem)
{
	int prevlevel = prev->level;
	assert(levels.size()>= prevlevel+1);
	int level = prevlevel + 1;
	if (levels.size() == level)
	{
		levels.resize(level + 1);
	}
	GSSnode* node = findElemAtLevel(level, elem);
	if (node == nullptr)
	{
		node = new GSSnode();
		root->elem = elem;
		root->level = level;
		levels[level].push_back(root);
	}
	node->add(prev);
	return node;
}

Często występuje tylko operacja dodawania bez usuwania węzłów z GSS. Gdyby była potrzebna, to wykonuje się:

void GSS::remove(GSSnode* node)
{
	if (levels.size() > node->level + 1)
		if (findPrevAtLevel(node->level + 1, node)) throw Exception("can remove only from top");
	for (int i = 0; i < levels[node->level].size(); i++)
		if (levels[node->level][i] == node)
		{
			levels[node->level].erase(levels[node->level].begin() + i);
			break;
		}
	delete node;
}