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:
Nie daj się zaskoczyć na maturze – zapisz się do listy mailingowej już teraz!
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.
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 |
//£ukasz Kosiñski - implementacja stosu #include <stdio.h> #include <stdlib.h> #include <conio.h> #include <windows.h> int max_size; typedef struct StackElement { int data; struct stackElement * next; } StackElement_type; int push(StackElement_type **top, int number); int pop(StackElement_type **top); void empty(StackElement_type *top); void show(StackElement_type *top); int size(StackElement_type *top); int main() { printf("Wprowadz maksymalny rozmiar stosu: "); scanf("%i", &max_size); Sleep(1000); if(max_size<=0) return 1; else { StackElement_type *top; top=NULL; int option=-1; int number=-1; while(option!=0) { system("cls"); printf("Aktualny stan stosu: "); show(top); printf("\n\nDrogi uzytkowniku! Co chcesz zrobic?\n"); printf("1. Polozyc element na stosie.\n"); printf("2. Zdjac element ze stosu.\n"); printf("3. Sprawdzic czy stos jest pusty.\n"); printf("4. Policzyc elementy na stosie.\n"); printf("0. Zakonczyc program.\n"); scanf("%i", &option); switch (option) { case 0: return 0; break; case 1: printf("Wpisz liczbe jaka chcesz dodac: "); scanf("%i", &number); push(&top, number); break; case 2: pop(&top); break; case 3: empty(top); Sleep(2000); break; case 4: printf("Liczba elementow na stosie: %i", size(top)); Sleep(2000); break; default: printf("Podaj wlasciwa opcje."); Sleep(2000); break; } } } return 0; } int push(StackElement_type **top, int number) { if(size(*top)==max_size) { printf("\nSTACK OVERFLOW!! Nie mozna dodac elementu do stosu."); Sleep(2000); return 1; } if(*top==NULL) { *top=(StackElement_type *) malloc (sizeof(StackElement_type)); (*top)->data=number; (*top)->next=NULL; }else { StackElement_type *newElement; newElement=(StackElement_type *)malloc(sizeof(StackElement_type)); newElement->data=number; newElement->next=*top; *top=newElement; } } int pop(StackElement_type **top) { if (*top==NULL) { printf("\nSTACK UNDERFLOW!! Nie ma czego zdjac ze stosu."); Sleep(2000); }else { StackElement_type * tmp=NULL; tmp=(*top)->next; free(*top); *top=tmp; } } void empty(StackElement_type *top) { (top==NULL) ? printf("Stack is empty :O") : printf("Stack is not empty :]"); } void show(StackElement_type *top) { printf("\n"); if(top==NULL) printf("List is empty"); else { StackElement_type *current=top; do { printf("%i", current->data); printf("\n"); current = current->next; }while (current != NULL); } } int size(StackElement_type *top) { int counter=0; StackElement_type *current=top; while(current!=NULL) { counter++; current=current->next; } return counter; } |
Jeżeli chcesz poznać inne struktury danych, zachęcam cię do przeczytania tej książki:
