Kurs maturalny z języka angielskiego!
kurs-maturalny-jezyk-angielski

PROGRAMOWANIE I ALGORYTMY

Zajęcia maturalne z informatyki
Olimpiada Informatyczna Juniorów
    Prowadzący: Marcin Kasprowicz
  • właściciel serwisu algorytm.edu.pl
  • wrzesień 2024 — start zajęć
  • czytaj więcej

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 - kolejka lifo

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:

Liczba elementów na stosie: 4
Element, który można usunąć: 99
Element, który można usunąć: 23
Stos jest pusty
Nie można usunąć elementu ze stosu, ponieważ jest on pusty

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:

Liczba elementów na stosie: 4
Element, który można usunąć: 99
Element, który można usunąć: 23
Stos jest pusty
Nie można usunąć elementu ze stosu, ponieważ jest on pusty

 

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