Programowanie w języku C/C++ » Artykuły

Własny stos

  • 2007-01-02 08:53
  • 7 komentarzy
  • 3165 odsłon
  • Oceń ten tekst jako pierwszy
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

marekbar218 2010-01-27 16:59

Polecam gotowy kod stosu z mojej strony http://napiszprogram.pl - należy kliknąć po lewej stronie na Stos

Ślepiec 2007-06-17 10:59

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;
}

Dryobates 2007-01-02 10:58

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.

Lolo 2005-04-25 12:22

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.

marcinEc 2004-12-05 23:22

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.

szprot_cool 2004-11-24 11:34

pomysł dobry ale lepiej jest zebrać to wszystko w klasę, np. class stos

krajekojoj 2005-03-01 16:41

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