prośba o wytłumaczenie działania stosu na wskaźnikach

Question

Hej, jestem po odcinku kursu C++ o strukturach danych ,powiem że stos na tablicach jest prosty ale... ,cóż sam P.Mirosław mówił żeby  poszukać lepszej implementacji tych struktur na wskaźnikach . Teraz zajmuje się pierwszą ,mianowicie stosem . Znalazłem jedną dość ciekawą implementacje w której użyta jest struktura . Problem jest jak już oczywiście wiecie taki że nie do końca rozumiem działanie tego programiku .  W komentarzach napisałem których rzeczy nie do końca rozumiem . Bardzo też proszę o cierpliwość i wyrozumiałość jeśli te rzeczy są banalnie proste a ja ich nie ogarniam ); . Z góry dziękuje za waszą pomoc :

#include <iostream>

using namespace std;

struct stos {
	string dane; //wartosc danego bloku (elementu) struktury
	stos *nast; //wskaznik na nastepny element
};

stos *wierzch = NULL; //poczatkowo nie ma jeszcze zadnych elementow ,w tym rowniec wrzcholka


///nie rozumiem do konca  funkcji na dole
void push(string nowy_element) { //w argumentach nowy element jaki chcemy dodac 
	stos *punkt; //czym jest ten punkt ? 
	punkt = wierzch;  //i czemu ma wartosc wierzcholka ? 
	wierzch = new stos;  //no dobra ,troche to rozumiem ,tworzymy stos...
	wierzch->dane = nowy_element; //wierzcholek miesci w sobie nowy element
	wierzch->nast = punkt; //czemu nastepny element stosu jest rowny wierzcholkwi skoro jezcze tam nic nie ma
}


string pop() { //mysle ze to zrozumiem po ogarnieciu funkcji push
	string x;
	stos *punkt;
	if(wierzch != NULL) {
		x = wierzch->dane;
		punkt = wierzch->nast;
		delete wierzch;
		wierzch = punkt;
	}
	return x;
}
bool empty() { //to ogarnia nawet moja mózgownica ;)
	if(wierzch == NULL)
		return true;
	else return false;
}

int main() { //tu jeszcze nic nie ma,najpierw chce zrozumiec zasade dzialania tego algorytmu
	return 0;
}

 

Answer 1

///nie rozumiem do konca  funkcji na dole
void push(string nowy_element) { //w argumentach nowy element jaki chcemy dodac 
    stos *punkt; //czym jest ten punkt ? 
    punkt = wierzch;  //i czemu ma wartosc wierzcholka ? 
    wierzch = new stos;  //no dobra ,troche to rozumiem ,tworzymy stos...
    wierzch->dane = nowy_element; //wierzcholek miesci w sobie nowy element
    wierzch->nast = punkt; //czemu nastepny element stosu jest rowny wierzcholkwi skoro jezcze tam nic nie ma
}

'wierzch' to wskaźnik na najwyższy element stosu - jak wiemy stos budowany jest od dołu, jest to tzw. LIFO czyli Last In First Out (ostatni który wchodzi jest pierwszym który wychodzi), czyli żeby dokopać się do najniższego elementu stosu musimy zrzucić każdy wyższy element.

Ta funkcja tworzy kopię wskaźnika na poprzedni najwyższy punkt stosu. Następnie 'wierzch' staje się kolejnym elementem (wyżej położonym na stosie niż 'punkt'). Ustawiamy jego dane na string 'nowy_element' oraz wskaźnik na element, który jest o jeden niżej czyli nasz poprzedni 'punkt'.

'wierzch' to nie skrót od "wierzchołek" tylko po prostu - wierzch stosu.
https://sjp.pwn.pl/szukaj/wierzch.html

Cała ta implementacja jest tak zła, że żal na to patrzeć ale już niech będzie.

Comments

Dzięki za odpowiedzi ,muszę sobie tylko  to wszystko poukładać w głowie . Jak będę miał jeszcze jakieś wątpliwości to wznowie temat więc jeszcze nie zamykam pytania . Nie wiem tylko komu dać naj 

---

witam jeszcze raz ,zacząłem zerkać na inne implementacje stosu bo ta rzeczywiście jest dziwna i różni się od innych rozwiązań, oto kod funkcji "push"  z innego programu . Mam tylko pytanie czy dobrze zrozumiałem jej działanie ... z góry dziękuje 

struct liczba {
	int wartosc;
	liczba *next;

};

void dodaj (liczba **root) {	
	int x; 
	cin>>x; //wpisujemy jakieś dane do stosu
	
	liczba *nowa=new liczba; //w tym momencie powstaje nam nowy element stosu (wiercholek)
	nowa->wartosc=x; //wspisujemy wartosc elementu
	nowa->next=*root;//nastepny element ma wartosc wskaznika root
	*root=nowa; //root wskazuje na nowy element ktry jeszcze ne powstal
}

 

---

Nie do końca jest tak jak napisałeś. W rzeczywistości działa to prawie tak samo jak wcześniej, teraz tylko pobiera wskaźnik do poprzednie najwyżej położonego elementu, a wcześniej widniał on jako zmienna globalna. Nie o to mi chodziło mówiąc, że implementacja jest zła. Ma ona całą masę niedopracowań i błędów, które później na etapie nauki powinieneś dostrzec. Póki co nie powinieneś się tym zajmować.

---

ok, pozostała jeszcze tylko ostatnia kwestia jaką tak średnio rozumiem ,mianowicie czemu zawsze następny element stosu jest kopią tego poprzedniego ?

wierzch->nast = punkt;

nie rozumiem po co taki zabieg ... (przecież można dać tam po prostu NULL) mam nadzieje że to już ostatnie moje pytanie i podziwiam za cierpliwość (;

---

To nie jest kopia poprzedniego obiektu tylko pobranie wskaźnika do niego. Kopiując wskaźnik nie kopiujesz obiektu tylko kopiujesz jego adres, żeby go nie utracić. W ten sposób szczytem stosu staje się jakiś nowy element (zdefiniowany przez = new <Typ>) ale wskaźnik na poprzedni element potrzebny jest, żeby go zapisać do wskaźnika "nast" w elemencie na szczycie. W efekcie otrzymujesz łańcuch elementów, który zaczyna się na szczycie stosu i idąc tak po wskaźnikach na niżej położone elementy (element "nast" struktury) dostajesz się na coraz to niższe poziomy aż dojdziesz do elementu, którego wskaźnik "nast" jest zerowy i oznacza to spód stosu. Musisz po prostu "dołączyć" do łańcucha kolejny element, którego wskaźnik "nast" wskaże na poprzedni najwyżej położony element (ten, który teraz został przykryty przez nowo dodany element). To można by było lepiej napisać tak:

void push(std::string dane)
{
   stos *nowySzczyt = new stos;
   stos->dane = dane;
   stos->nast = wierzch;

   wierzch = nowySzczyt;
}

Teraz lepiej to widać - najpierw tworzysz nowy element, który dorzucisz na szczyt stosu, ustawiasz mu jego dane oraz wskaźnik na *aktualny* szczyt stosu (jeszcze przed wrzuceniem nowego elementu) a następnie zastępujesz wskaźnik na 'wierzch' na nowy szczyt. Poprzedni szczyt teraz jest dostępny pod adresem przechowywanym w 'wierzch->nast'

---

dzięki za pomoc ,wreszcie wszystko układa mi się w całość .

Answer 2

Wierzchołek, jak sama nazwa wskazuje będzie to wierzchołek.

stos *punkt; 

punkt = wierzch;

funkcja push dodaje nowy element, który staje się wierzchołkiem, także punkt jest "starym wierzchołkiem". Więc w tym nowym wierzchołku, następny element wskazuje stary wierzchołek czyli punkt.

Funkcja pop zdejmuje wierzchołek i go wywala. Dlatego zanim go wywali musi zapisać wskazywany następny element przez wierzchołek

punkt = wierzch->nast;

 Po czym ten punkt staje sie wierzchołkiem.

Comments

Masz mały błąd:

funkcja pop dodaje nowy element

 

---

Masz rację, już poprawiłem