Stos jest użyteczną rzeczą. Bez niego nie można napisać typowego Hello World (printf()/ostream pobiera parametr). Jest używany do komunikacji między procedurami, funkcjami oraz przechowywania zmiennych, i nawet porządkowania zbioru danych (np. szafa).
Często jeden stos nie wystarcza. Co można wtedy zrobić?
a) zmieniać sp/esp oraz ss
jest to prosty sposób, lecz nadaje się prawie tylko dla OS.
b) użyć stack.h z STL w C++
bardziej złożony sposób, wady: wymagana znajomość C++, oraz organicza program do tego języka (można napisać kompilator C++ do C, ale nie jest to proste).
c) napisać własny odpowiednik stack.h (i odpowiednich plików obiektowych)
jest to sposób, którego dotyczy ten artykuł.
Rozumiejąc działanie sp/esp, ss, push i pop można to napisać.
Przykładowy plik stack.h:
typedef struct
{
int* sp;
int* sbeg;
int* send;
}stack;
int sempty(stack* s);/*returns true if stack is empty*/
int pop(stack* s);/*pops from stack*/
void push(stack* s,int val);/*pushes at top of stack*/
size_t ssize(stack* s);/*returns number of elements*/
stack* sinit(size_t size);/*inits stack, returns NULL if error*/W protected mode sbeg i send występują w deskryptorze selektora ss.
Dlaczego struktura stack to wskaźniki do zmiennych int?
Stos działa tylko na najszybszych zmiennych, o rozmiarach zależnych od rmode/pmode. Dla każdego kompilatora C taka zmienna to int.
Funkcje nie są w tym przypadku złożone:
int sempty(stack* s)
{
if(s->sbeg==s->sp)
{
return 1;
}
else
return 0;
}
int pop(stack* s)
{
if(s->sp>s->sbeg)
{
s->sp-=sizeof(int);
return *(s->sp);
}
else
return 0;
}
void push(stack* s,int val)
{
if(s->sp<s->send)
{
*(s->sp)=val;
s->sp+=sizeof(int);
};
return;
}
size_t ssize(stack* s)
{
return (s->sp-s->sbeg)>>2;
}
stack* sinit(size_t size)
{
return malloc(size*sizeof(stack));
}Działają zgodnie z opisem, i nazwami.
Wiem, że temat jest stary (jak 8086 co najmniej...), ale może być użyteczny.
Po drobnych modyfikacjach ten kod może przydać się również do pisania kompilatora c++.
Zgadzam się z przemówcą, i gorąco namawiam do stosowania klasy stack z STL ( jak i całej STL wogóle ). No bo po co ponownie wymyślać koło...
pomysł dobry ale lepiej jest zebrać to wszystko w klasę, np. class stos
Czy stos jako struktura danych (STL) to stos procesora (x86)? Nie wydaje mi się. Przydałoby się trochę uporządkowania tych informacji, bo wrzucenie tego do jednego worka z nazwą stos jest bardzo mylące. Artykuł dotyczy symulacji stosu procesora, a nie stosu ogólnie.
Fajnie to wygląda, ale ja się tu zapytam - \"Po jakiego grzyba mordować się tu ze wskaźnikami?\". Nie lepiej stos sobie zrobić na zwykłej tablicy.
szprot_cool i krajekojoj - w czystym C nie ma klas i STL. Co prawda można zasymulować klasy z wykorzystaniem struct, ale pisząć w C podchodzimy do sprawy raczej nie w sposób obiektowy.
Natomiast zgadzam się z marcinEc, że wspominanie tutaj o stosie procesora, nie ma w ogóle sensu.
Lolo - masz rację albo użyć tablicy, albo listy jeżeli ma być "nieograniczonej" wielkości stos.
Wydaje mi się, że powinniśmy mieć w coyote niezależny artykuł Stos, a co najwyżej w poszczególnych działach różne sposoby implementacji i wykorzystania (uwzględniając te gotowe). Po co dublować, jak idea stosu jest jedna.
trochę inaczej zbudowany stos, chyba najbardziej klasyczny oparty na liście jednokierunkowej:
typedef struct CELL Stack;
struct CELL {
double value;
Stack prev;
};
double pop(Stack s){
if (s != NULL) {
Stack tmp=s;
free(s);
(s) = tmp->prev;
return tmp->value;
}
else return 0;
}
void push(Stack s, double val) {
Stack tmp = (Stack) malloc(sizeof(struct CELL));
tmp->value = val;
tmp->prev = s;
s = tmp;
}
void init(Stack s){
*s = NULL;
}
Polecam gotowy kod stosu z mojej strony http://napiszprogram.pl - należy kliknąć po lewej stronie na Stos