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

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

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

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.

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.

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.

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

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