Własny stos

TKW

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++.

7 komentarzy

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