Stos - kolejka lifo

powrót

Stos to struktura danych, którą możemy porównać do naleśników nakładanych na jedną stertę. W danej chwili możemy wykonać jedną z dwóch operacji:

• push(element) - dodanie elementu na wierzchołek stosu (tu naleśnika)
• pop() - zdjęcie elementu z wierzchołka stosu

W tej strukturze danych nie mamy bezpośredniego dostępu do elementu, który nie jest na szczycie. Aby dostać się do innego elementu niż wierzchołek, należy zdjąć wszystkie, które są nad nim.

Stos nazywany jest także kolejką lifo - last in first out - ostatni wrzucony na stos jest pierwszym do zdjęcia. Używany jest w wielu algorytmach, między innymi w algorytmie grafowym - przeszukiwanie w głąb - DFS.

Zostaną przedstawione dwie implementacje. Pierwsza statyczna - oparta na tablicy, druga dynamiczna - pamięć na kolejne elementy będzie dynamicznie przydzielana.

Zaimplementowane zostaną następujące funkcje:

• push(wartość) - dodanie elementu na stos
• pop() - usunięcie elementu ze stosu
• empty() - sprawdzenie, czy stos jest pusty
• size() - zwrócenie liczby elementów na stosie
• value() - zwrócenie ostatniego elementu na stosie

Wszystkie elementy omawianej struktury będą przechowywane w tablicy, której wielkość będzie z góry ustalona.

Zalety

• prostota implementacji
• bardzo szybkie działanie

Wady

• ograniczenie co do wielkości stosu
• usuwanie elementu nie oznacza fizycznego usunięcia z pamięci

#include<iostream>
//ta wartosć nie może pojawić się jako element stosu
#define ERROR 1000000000 
//maksymalna wielkosć stosu
#define MAX 1000
using namespace std;

int tab[MAX],  //tablica na stos
i = 0; //zmienna wskazująca komórkę tablicy, w której jest wierzchołek stosu

inline bool push(int element)
{
  if(i>=MAX) return 0; //gdy nie ma miejsca na stosie
  
  tab[i++] = element;
  return 1;
}

inline int pop()
{
  if(i==0) return ERROR; //gdy nie ma co usuwać
  
  --i;
  return 1; //udało się usunąć
}

inline bool empty()
{
  if(i==0) return 1; //gdy stos jest pusty
  
  return 0; //gdy są elementy na stosie
} 

inline unsigned int size()
{
  return i; //zwrócenie liczby elementów stosu
}

inline int value()
{
  if(i==0) return ERROR; //gdy stos jest pusty
  
  return tab[i-1];
}

int main()
{
  if(!push(12)) cout<<"Stos jest przepełniony!\n";
  if(!push(23)) cout<<"Stos jest przepełniony!\n";
  if(!push(43)) cout<<"Stos jest przepełniony!\n";
  if(!push(99)) cout<<"Stos jest przepełniony!\n";
  
  cout<<"Liczba elementów na stosie: "<<size()<<endl;
  cout<<"Element, który można usunąć: "<<value()<<endl;
  pop(); //usunięcie 99
  pop(); //usunięcie 43
  cout<<"Element, który można usunąć: "<<value()<<endl;
  pop(); //usunięcie 23
  pop(); //usunięcie 12
  if(empty()) 
    cout<<"Stos jest pusty\n";
  else
    cout<<"Na stosie znajdują się elementy, jest ich "<<size()<<endl;
  
  if(pop()==ERROR)
    cout<<"Nie można usunąć elementu ze stosu, ponieważ jest on pusty\n";
  
  return 0;
}

Out:

Rozwiązanie dynamiczne:

Zalety

• nie ogranicza nas wielkość stosu
• prostota implementacji
• elementy są usuwane fizycznie z pamięci

Wady

• nieco wolniejszy niż statyczna wersja

//wwww.algorytm.edu.pl
#include<iostream>
using namespace std;
 
class stos{
  public:
    stos(){i=0;f=1;el = NULL;}
    ~stos() //zwolnienie pamięci dla elementów stosu
    {
      while(el!=NULL)
    {
      pom = el->poprzedni;
      delete el;
      el = pom;
    }   
    }
    unsigned int size(){return i;}//liczba elementów w kolejce
    void push(int x)//dodanie elementu na szczyt stosu
    {
         if(f)//sprawdzamy, czy pierwszy raz dodajemy element
         {
        f=0;
        el = new wezel;
        el->element = x;
        el->poprzedni = NULL;
         }
         else
         {
           pom = new wezel;
           pom->element = x;
           pom->poprzedni = el;
           el = pom;
         }
         ++i; 
    }
    int pop()// usunięcie elementu z wierzchołka
    {
       if(el == NULL) return 0; //gdy stos jest pusty
       
       pom = el->poprzedni;
       delete el;
       el = pom;
       --i;
       
       return 1;
    }
    int value() //zwrócenie ostatniego elementu na stosie
    {
      if(!empty())
        return el->element;

      return ERROR;
    }
    bool empty()
    {
      return i==0?1:0;
    }
    const int ERROR = 1000000000; //ta wartosć nie może się pojawić na stosie
  private:
    bool f; //flaga okreslająca, czy w kolejce cos już się pojawiło
    struct wezel{
      int element; //wartosć elementu stosu
      wezel *poprzedni;  //wskaźnik na poprzedni element
    };
    unsigned int i; //zmienna przechowuje liczbę elementów na stosie
    wezel *el, //ostatni element na stosie
     *pom; //zmienna pomocnicza
};
 
int main()
{
  stos stack; //utworzenie stosu
 
   stack.push(12); //dodanie na stos 12
  stack.push(23); //dodanie na stos 23
  stack.push(43); //dodanie na stos 43
  stack.push(99); //dodanie na stos 99
  
  cout<<"Liczba elementów na stosie: "<<stack.size()<<endl;
  cout<<"Element, który można usunąć: "<<stack.value()<<endl;
  stack.pop(); //usunięcie 99
  stack.pop(); //usunięcie 43
  cout<<"Element, który można usunąć: "<<stack.value()<<endl;
  stack.pop(); //usunięcie 23
  stack.pop(); //usunięcie 12
  if(stack.empty()) 
    cout<<"Stos jest pusty\n";
  else
    cout<<"Na stosie znajdują się elementy, jest ich "<<stack.size()<<endl;
  
  if(!stack.pop())
    cout<<"Nie można usunąć elementu ze stosu, ponieważ jest on pusty\n";

  return 0;
}

Out:

Warto wspomnieć o STL-owym stosie, który jest szybki i przyjemny w korzystaniu. Stos opisany został tutaj.