C, Programowanie, Struktury danych

Struktury danych: stos

stos w c

Cześć, oddaję w wasze ręce trzeci z kolei wpis na temat abstrakcyjnych struktur danych. Dzisiaj na warsztat wezmę stos i jego implementację w C. 

W celu lepszego zrozumienia kilku technicznych aspektów jak np. podwójny wskaźnik **, polecam zapoznać się z poprzednimi postami z serii: 

 Stos – koncepcja 

Stos podobnie do list jest strukturą liniową, tzn. taką, w której przy poruszaniu się w danym kierunku mamy tylko jedną możliwość. Różnią się za to sposobem dostępu do danych znajdujących się w strukturze. Listy umożliwiały operacje na dowolnych elementach, wchodzących w ich skład. Mogliśmy dopisywać elementy na początku listy, na końcu lub w środku. W ten sam sposób mogliśmy usuwać dane z listy. 

W stosie zastosowano inne rozwiązanie. Mianowicie operować można jedynie pierwszym elementem na naszym stosie, tzw. wierzchołkiem (ang. top). Aby dostać się do danego elementu stosu należy przejść przez wierzchołek właśnie. 

stos w c

 

Dodając nowy element na stos staje się on nowym wierzchołkiem. Natomiast usuwając element ze stosu, usuwamy właśnie dotychczasowy top naszego stosu, a jego rolę przejmuje element będący w danym momencie pod nim.  

Zobrazujmy to sobie za pomocą popularnych pankejków. Dostajemy taki stos i decydujemy, że będziemy go spożywać jak ludzie. W tym celu zawsze będziemy operować pierwszym z góry naleśnikiem – wierzchołkiem naszego stosu. Zjadając wierzchołek wywołujemy pop() na stosie – usuwamy element. Natomiast jeżeli zdecydujemy się na dodatkowego pankejka to położymy go na szczycie naleśnikowego stosu tym samym stanie się on nowym wierzchołkiem. Taka dokładka odpowiada funkcji push() – dodaniu elementu do stosu.  

Ze względu na rozwiązanie funkcji dodawaniu i usuwania elementów, stos nazywa się często kolejką LIFO (ang. Last in first out), gdyż jak sama nazwa mówi: element dodany jako ostatni usuwany jest w pierwszej kolejności. 

Ważne właściwości stosu

Z pojęciem stosu wiążą się dwa ważne terminy. Chodzi o popularny termin stack overflow oraz nieco mniej znany stack underflow. Pierwszy odnosi się do sytuacji, gdy próbujemy do stosu o określonej pojemności dodać jeszcze jeden element. Dochodzi wówczas do błędu przepełnienia stosu. Od tego pojęcia nazwę wzięło najsławniejsze z programistycznych miejsc w sieci – strona stackoverflow.com. 

Drugi termin opisuje sytuację, w której chcemy usunąć element z już pustego stosu. 

Zastosowanie stosu 

Stos jest jedną z najpowszechniej używanych struktur. Wykorzystywany jest na przykład przy: 

  • Obliczaniu wartości wyrażeń w notacjach prefiksowej (polskiej) i postfiksowej (polskiej odwrotnej), 
  • Zarządzaniu pamięcią programu – korzystamy ze stosu za każdym razem, gdy używamy tablic i wskaźników, 
  • Konwersji z kodu naturalnego binarnego na system dziesiętny. 

 

Stos – implementacja w C 

Stos w języku C można w łatwy sposób zaimplementować za pomocą listy powiązanej tak jak to robiliśmy w przypadku struktur list. Stos korzysta z następujących funkcji: 

  • push() – dodanie elementu na szczyt stosu, 
  • pop() – zdjęcie elementu ze stosu, 
  • empty() – sprawdzenie, czy stos jest pusty, 
  • size() – zliczenie elementów na stosie.

Stos w C nie różni się specjalnie od implementacji innych struktur liniowych. Jednakże chcąc uzyskać efekt stack overflow zdefiniujemy maksymalną liczbę elementów stosu. Upodobnimy wtedy nasz stos do tego w pamięci, która nie jest przecież nieskończona.

Dodatkowo uważam, że stos jest o wiele łatwiejszy do zaimplementowania, gdyż musimy rozpatrzeć tylko jeden przypadek przy dodawaniu i usuwaniu elementów. Użytkownik może dodać element tylko na wierzchołek stosu i basta.

 

 

Dodaj komentarz