ok, sots i klejka w jednym. push() umieszcza na koncu, pop() pobiera z konca a get() z poczatku, ergo:
push+pop -> stos (FILO/LIFO)
push+get -> kolejka (FIFO/LILO)
typedef int atomtype;
struct stos{
atomtype* tab; // atomtype musisz sobie zdefiniować, ty potrzebujesz inta
int wykorzystane; // ilosc wykorzystanych pol w tablicy dynamicznej
int przydzielone; // ilosc rzeczywiscie przydzielonych pol tablicy dynamicznej
};
void push(stos& st,atomtype& atom){ // push - wrzuc atom na stos
// element samokontroli stosu
if(st.wykorzystane==st.przydzielone){ // brak wiecej przydzielonego miejsca
if(!st.przydzielone){ // jesli nic nie przydzielone
st.przydzielone=1; // to przydziel 1 komorke
}else st.przydzielone*=2; // w przeciwnym przypadku st.przydzielone=st.przydzielone*2
// w ten sposob przydzielomy kolejno 1,2,4,8,16,32,... czyli potegi 2 ilosc komorek
st.tab=(atomtype*)realloc(st.tab,st.przydzielone*sizeof(atomtype)); //przydziel nowy (podwojny) rozmiar pamieci
}
//memcpy(&st.tab[st.wykorzystane],atom,sizeof(atomtype));
st.tab[st.wykorzystane]=atom; // w tym wypadku to co wyzej, ale po ludzku
st.wykorzystane++;
}
int pop(stos& st,atomtype& atom){
if(!st.wykorzystane)return 0; // stos jest pusty zwroc FALSE
st.wykorzystane--; // st.wykorzystane=st.wykorzystane-1;
//memcpy(atom,&st.tab[st.wykorzystane],sizeof(atomtype));
atom=st.tab[st.wykorzystane]; // w tym wypadku to co wyzej, ale po ludzku
// element samokontroli stosu
if(st.wykorzystane<=st.przydzielone/2){ // jezeli jest wykorzystane pol lub mniej komorek przydzielonych dla stosu
st.przydzielone/=2; // st.przydzielone=st.przydzielone/2
st.tab=(atomtype*)realloc(st.tab,st.przydzielone*sizeof(atomtype)); // przydziel polowe tego co bylo
}
return 1; // gdy na stosie cos bylo, zwroc TRUE
}
int get(stos& st,atomtype& atom){
if(!st.wykorzystane)return 0; // stos jest pusty zwroc FALSE
st.wykorzystane--; // st.wykorzystane=st.wykorzystane-1;
//memcpy(atom,st.tab,sizeof(atomtype)); // st.tab == &st.tab[0]
atom=*st.tab; // *st.tab == st.tab[0]
int i=0; // roznica pomiedzy get i pop
while(i<st.wykorzystane){ // sprawdz czy nie powinno byc <=, ale raczej nie powinno
//memcpy(&st.tab[i],&st.tab[i+1],sizeof(atomtype));
st.tab[i]=st.tab[i+1];
i++;
}
// element samokontroli stosu
if(st.wykorzystane<=st.przydzielone/2){ // jezeli jest wykorzystane pol lub mniej komorek przydzielonych dla stosu
st.przydzielone/=2; // st.przydzielone=st.przydzielone/2
st.tab=(atomtype*)realloc(st.tab,st.przydzielone*sizeof(atomtype)); // przydziel polowe tego co bylo
}
return 1; // gdy na stosie cos bylo, zwroc TRUE
}
void stworzstos(stos& st,int iloscpoczatkowa){
// Stworz stos i przydizel na poczatek czesc komorek
st.przydzielone=iloscpoczatkowa;
st.wykorzystane=0; // swiezy stosik, nie ma praw miec czegokolwiek wykorzystanego
st.tab=(atomtype*)malloc(iloscpoczatkowa*sizeof(atomtype)); // przydziel tablicy pamiec: iloscpoczatkowa*rozmiar komorki
}
void zwolnijstos(stos& st){ // wyczyść stos ze wszystkiego
if(st.tab)free(st.tab); // czyszczenie resztek
st.tab=0; // st.tab=NULL;
st.przydzielone=0; // no i oczywiście wyzeruj
st.wykorzystane=0;
}
W tym kodzie nie ma kontroli, czy malloc/realloc nie zwrocił 0/NULL, potrzebna tylko w funkcjach stworzstos i push, gdzie moze nastapic dodanie ilosci pamieci, pop i get conajwyżej zwalniają część pamięci, więc tu o problemie nie ma mowy.
Uzycie:
stworzstos() -> push()/get()/pop() x N -> zwolnijstos()
Po zwolnijstos() można uzywać push()/pop()/get() od nowa, bez tworzenia, ale można też stworzyć stos od nowa przydzielając początkową ilośc komórek.
dla szybkości mozna wprowadzić mapowanie albo/i zwiekszenie indeksu poczatkowego zamiast przpisywania tablicy przy get, tak aby kolejne pushe mogly wstawiac wartości za pobrane getem, ale trzeba zmienic wtedy algorytm samokontroli i wprowadzic klilka prostych obliczen (+,%, pewnie cos jeszcze) do geta i popa.