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}. 400px|Graph-structured_stack_-_Borneq.png
Innym sposobem symulacji niedeterminizmu byłaby duplikacja stosu. Jest ona mniej wydajna, ponieważ wierzchołki nie są dzielone. W tym przykładzie jest 16 wierzchołków zamiast 9. Stacks_-_Borneq.dot.png|350px
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; }
Przypisy
Kategoria:Struktury danych Kategoria:Klasy grafów